Geometric Thickness for the General Graphs
Keywords:
Graph,Embedding,Graph ThicknessAbstract
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.
References
- 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.
- T. Tutte, The thickness of a graph, Indag. Math. 25 (1963) 567–577.
- B. Alekseev, V.S. Gonchakov, Thickness of arbitrary complete graphs, Math. USSR Sb. 30 (2) (1976) 187–202.
- W. Beineke, F. Harary, J.W. Moon, On the thickness of the complete bipartite graph, Math. Proc. Camb. Philos. Soc. 60 (1964) 1–6.
- B. Dillencourt, D. Eppstein, D.S. Hirschberg, Geometric thickness of complete graphs, J. Graph Algorithms Appl. 4(3) (2000) 5–17.
- Mans?eld, Determining the thickness of a graph is NP-hard, Math. Proc. Camb. Philos. Soc. 93 (1983) 9–23.
- Mutzel, T. Odenthal, M. Scharbrodt, The thickness of graphs: a survey, Graphs Comb. 14 (1998) 59–73.
- Eppstein, Separating thickness from geometric thickness, Contemp. Math. 342 (2004) 75–86.
- P. Hutchinson, T.C. Shermer, A. Vince, On representations of some thickness-two graphs, Comput. Geom.: Theory Appl. 13 (3) (1999) 161–171.
- Barát, J. Matoušek, D.R. Wood, Bounded-degree graphs have arbitrarily large geometric thickness, Electron. J. Comb. 13 (1) (2006) 1–14.
- 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.
- Dujmovic, D.R. Wood, Graph treewidth and geometric thickness parameters, Discrete Comput. Geom. 37 (4) (2007) 641–670.
- A. Duncan, On graph thickness, geometric thickness, and separator theorems, Comput. Geom.: Theory Appl. 44 (2) (2011) 95–99.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRSET
This work is licensed under a Creative Commons Attribution 4.0 International License.