ABSTRACT
We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design.
- Aggarwal, Klawe, and Shor. Multilayer grid embeddings for VLSI. Algorithmica, 6:129--151, 1991.Google ScholarDigital Library
- J. Akiyama. A status on the linear arboricity. In N. Saito and T. Nishizeki, editors, 17th Symposium of Research Institute of Electrical Communication on Graph Theory and Algorithms, volume 108 of LNCS, pages 38--44, 1980. Google ScholarDigital Library
- J. Akiyama, G. Exoo, and F. Harary. Covering and packing in graphs. III. Cyclic and acyclic invariants. Math. Slovaca, 30(4):405--417, 1980.Google Scholar
- J. Akiyama, G. Exoo, and F. Harary. Covering and packing in graphs. IV. Linear arboricity. Networks, 11(1):69--72, 1981.Google ScholarCross Ref
- N. Alon. The linear arboricity of graphs. Israel J. Math., 62(3):311--325, 1988.Google ScholarCross Ref
- N. Alon, V. J. Teague, and N. C. Wormald. Linear arboricity and linear k-arboricity of regular graphs. Graphs Combin., 17(1):11--16, 2001.Google ScholarCross Ref
- F. Bernhart and P. C. Kainen. The book thickness of a graph. J. Combin. Theory, Ser. B 27:320--331, 1979.Google ScholarCross Ref
- P. Bose, A. M. Dean, J. P. Hutchinson, and T. C. Shermer. On rectangle visibility graphs. In S. C. North, editor, Proc. Int. Symp. Graph Drawing, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 25--44. Springer, 1997. Google Scholar
- P. Brass, E. Cenek, C. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. Kobourov, A. Lubiw, and J. Mitchell. On simultaneous planar graph embeddings. In 8th Workshop on Algorithms and Data Structures (WADS), volume 2748 of LNCS, pages 243--255, 2003.Google ScholarCross Ref
- C. Collberg, S. G. Kobourov, J. Nagra, J. Pitts, and K. Wampler. A system for graph-based visualization of the evolution of software. In ACM Symposium on Software Visualization (SoftVis), pages 77--86, 2003. Google ScholarDigital Library
- H. S. M. Coxeter. My graph. Proc. London Math. Soc., 46:117--136, 1983.Google ScholarCross Ref
- M. B. Dillencourt, D. Eppstein, and D. S. Hirschberg. Geometric thickness of complete graphs. Journal of Graph Algorithms and Applications, 4(3):5--17, 2000.Google ScholarCross Ref
- D. Eppstein. Separating geometric thickness from book thickness. arXiv:math/0109195, http://arXiv.org/abs/math/0109195, Sept. 24 2001.Google Scholar
- D. Eppstein. Separating thickness from geometric thickness. In Proc. 10th Int. Symp. Graph Drawing, GD, pages 150--161, 2002. Google ScholarDigital Library
- C. Erten, S. G. Kobourov, A. Navabia, and V. Le. Simultaneous graph drawing: Layout algorithms and visualization schemes. In Proc. 11th Int. Symp. Graph Drawing, GD'03, volume 2912 of Lecture Notes in Computer Science, LNCS, pages 437--449. Springer-Verlag, 2004.Google ScholarCross Ref
- P. C. Kainen. Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg, 39:88--95, 1973.Google ScholarCross Ref
- P. Mutzel, T. Odenthal, and M. Scharbrodt. The thickness of graphs: a survey. Graphs Combin., 14(1):59--73, 1998.Google ScholarCross Ref
- J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. In S. H. Whitesides, editor, Proc. 6th Int. Symp. Graph Drawing, GD, volume 1547 of Lecture Notes in Computer Science, LNCS, pages 263--274. Springer-Verlag, 13-15 Aug. 1998. Google Scholar
- D. B. West. Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ, 1996.Google Scholar
- D. R. Wood. Geometric thickness in a grid. Discrete Mathematics, 273:221--234, 2003.Google ScholarDigital Library
Index Terms
- The geometric thickness of low degree graphs
Recommendations
On graph thickness, geometric thickness, and separator theorems
We investigate the relationship between geometric thickness, thickness, outerthickness, and arboricity of graphs. In particular, we prove that all graphs with arboricity two or outerthickness two have geometric thickness O(logn). The technique used can ...
On the Planar Split Thickness of Graphs
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at ...
Remarks on the thickness and outerthickness of a graph
The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. The thickness of complete bipartite graphs K"m","n is known for almost all values of m and n. In this paper, we solve the thickness of complete ...
Comments