IJSRSET calls volunteers interested to contribute towards the scientific development in the field of Science, Engineering and Technology

Home > IJSRSET1732114                                                     

Geometric Thickness for the General Graphs


G. Ram Kumar, K. Prabhakaran, G. Saravanan, A. S.Vibith
  • Abstract
  • Authors
  • Keywords
  • References
  • Details
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.

G. Ram Kumar, K. Prabhakaran, G. Saravanan, A. S.Vibith

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 Print ISSN Online ISSN
2017-04-30 2395-1990 2394-4099
Page(s) Manuscript Number   Publisher
378-381 IJSRSET1732114   Technoscience Academy

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.
URL : http://ijsrset.com/IJSRSET1732114.php