Geometric Thickness for the General Graphs

Authors(4) :-G. Ram Kumar, K. Prabhakaran, G. Saravanan, A. S.Vibith

In this method the user gives a graph as input which is then processed. After processing the input graph is determined whether it is a planar graph or not. If the input graph is planar then a planar embedding of the given input graph is shown as the output having only one color. If the input graph is non planar then n layers of the given input graph is displayed where each layer is of different colors. Then each layer is also called as the Geometric-Thickness. The geometric thickness ?(G) of a graph G is the smallest integer t such that there exist a straight-line drawing of G and a partition of its straight-line edges into t subsets, where each subset induces a planar drawing. Over a decade ago, Hutchinson, Shermer, and Vince proved that any n-vertex graph with geometric thickness two can have at most 6n ? 18 edges, and for every n ? 8 they constructed a geometric thickness two graph with 6n ? 20 edge, but we taken the 6n-18 edges. And also we do the NP-hardness of coloring graphs of geometric thickness.

Authors and Affiliations

G. Ram Kumar
Kingston Engineering College, Vellore, Tamil Nadu, India
K. Prabhakaran
Kingston Engineering College, Vellore, Tamil Nadu, India
G. Saravanan
Kingston Engineering College, Vellore, Tamil Nadu, India
A. S.Vibith
Kingston Engineering College, Vellore, Tamil Nadu, India

Graph,Embedding,Graph Thickness

  1. Durocher, E. Gethner, D. Mondal, Thickness and colorability of geometric graphs, in: Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, in: LNCS, vol. 8165, Springer, 2013, pp. 237–248.
  2. T. Tutte, The thickness of a graph, Indag. Math. 25 (1963) 567–577.
  3. B. Alekseev, V.S. Gonchakov, Thickness of arbitrary complete graphs, Math. USSR Sb. 30 (2) (1976) 187–202.
  4. W. Beineke, F. Harary, J.W. Moon, On the thickness of the complete bipartite graph, Math. Proc. Camb. Philos. Soc. 60 (1964) 1–6.
  5. B. Dillencourt, D. Eppstein, D.S. Hirschberg, Geometric thickness of complete graphs, J. Graph Algorithms Appl. 4(3) (2000) 5–17.
  6. Mans?eld, Determining the thickness of a graph is NP-hard, Math. Proc. Camb. Philos. Soc. 93 (1983) 9–23.
  7. Mutzel, T. Odenthal, M. Scharbrodt, The thickness of graphs: a survey, Graphs Comb. 14 (1998) 59–73.
  8. Eppstein, Separating thickness from geometric thickness, Contemp. Math. 342 (2004) 75–86.
  9. P. Hutchinson, T.C. Shermer, A. Vince, On representations of some thickness-two graphs, Comput. Geom.: Theory Appl. 13 (3) (1999) 161–171.
  10. Barát, J. Matoušek, D.R. Wood, Bounded-degree graphs have arbitrarily large geometric thickness, Electron. J. Comb. 13 (1) (2006) 1–14.
  11. A. Duncan, D. Eppstein, S.G. Kobourov, The geometric thickness of low degree graphs, in: Proceedings of the International Symposium on Computa-tional Geometry, ACM, 2004, pp. 340–346.
  12. Dujmovic, D.R. Wood, Graph treewidth and geometric thickness parameters, Discrete Comput. Geom. 37 (4) (2007) 641–670.
  13. A. Duncan, On graph thickness, geometric thickness, and separator theorems, Comput. Geom.: Theory Appl. 44 (2) (2011) 95–99.

Publication Details

Published in : Volume 3 | Issue 2 | March-April 2017
Date of Publication : 2017-04-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 378-381
Manuscript Number : IJSRSET1732114
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

G. Ram Kumar, K. Prabhakaran, G. Saravanan, A. S.Vibith, " Geometric Thickness for the General Graphs, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 3, Issue 2, pp.378-381, March-April-2017.
Journal URL : http://ijsrset.com/IJSRSET1732114

Follow Us

Contact Us