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.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.