Total views : 282

### Slope Number on Complete Graphs

#### Affiliations

• Sathyabama University, Chennai - 600119, Tamil Nadu, India

#### Abstract

Objective: A straight line drawing is a mapping of an edge into a straight line segment. The minimum number of distinct slopes used in a straight line drawing of a graph G is called the slope number of the graph G. In this paper the slope number of complete graph is studied elaborately. Methods: This optimization problem is NP-Hard for any arbitrary graph. A canonical way of drawing of a complete graph is an existing one. In present paper, we consider the edges of a complete graph are straight line segments in order to obtain the number of slopes. Findings: This paper interprets the characterization of slopes in complete graph according to an odd and even number of edges and investigated in detail. Moreover, the slope number of a complete graph is compared with the chromatic number of complete graph and the results are observed. Applications/Improvement: Slope number is one of the quality measures of graph drawing. It is used to find out different layout methods for the same graph.

#### Keywords

Chromatic Number, Complete Bipartite Graph, Complete Graph, Slope Number, Straight Line Drawing.

#### Full Text:

|  (PDF views: 247)

#### References

• Wade GA, Chu JH.Drawability of complete graphs using a minimal slope set. The Computer Journal.1994; 37(2):139–42.
• Jamison RE. Few slopes without collinearity. Discrete Mathematics. 1986; 60:199–206.
• Ambrus G, Barat J,Hajnal P. The slope parameter of graphs.ActaScientiarumMathematicarum, (Szeged).2006;72(3–4):875–89.
• Mukkamala P, Palvolgyi D. Drawing cubic graphs with four basic slopes, van Kreveld M, Speckmann B, editors. Graph drawing, Springer-verlag: Berlin Heidelberg; 2012. p. 254–65.
• Pach J, Palvolgyi D. Bounded degree graphs can have arbitrarily large slope numbers.The Electronic Journal of Combinatorics. 2006; 13:1–4.
• Barat J, Matousek J, WoodR. Bounded-degree graphs have arbitrarily large geometric thickness. Electronic Journal of Combinatorics. 2006; 13(1):1–14.
• Keszegh B, Pach J,Palvolgyi D, Toth G. Drawing cubic graphs with atmost five slopes.Computational Geometry: Theory and Applications. 2008;40(2):138–47.
• Battista D,Eader P,Tamassia R,Tollis IG. Graph drawing: algorithms for the visualization of graphs, Prentice Hall; 1998.
• Ferbur K,Jurgensen H. A programme for the drawing of lattices. Leech J,editor. Computational problems in Abstract Algebra, Pergamon, Oxford; 1970. p. 83–7.
• Fertin G, Raspand A, Reed B. Star colouring of graph. Journal of Graph theory. 2004; 47(3):163–82
• Ramya N. On star chromatic number number of P3(n). Indian Journal of Science and Technology. 2014; 7(S5):7–8.DOI: 10.17485/ijst/2014/v7iS5/50209.

### Refbacks

• There are currently no refbacks.