Document Open Access Logo

On the Geometric Thickness of 2-Degenerate Graphs

Authors Rahul Jain , Marco Ricci , Jonathan Rollin , André Schulz

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.44.pdf
  • Filesize: 1.27 MB
  • 15 pages

Document Identifiers

Author Details

Rahul Jain
  • FernUniversität in Hagen, Germany
Marco Ricci
  • FernUniversität in Hagen, Germany
Jonathan Rollin
  • FernUniversität in Hagen, Germany
André Schulz
  • FernUniversität in Hagen, Germany

Cite AsGet BibTex

Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the Geometric Thickness of 2-Degenerate Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.44

Abstract

A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Degeneracy
  • geometric thickness
  • geometric arboricity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Eyal Ackerman, Jacob Fox, János Pach, and Andrew Suk. On grids in topological graphs. Computational Geometry, 47(7):710-723, 2014. URL: https://doi.org/10.1016/j.comgeo.2014.02.003.
  2. János Barát, Jiří Matoušek, and David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness. The Electronic Journal of Combinatorics, 13:R3, 2006. URL: https://doi.org/10.37236/1029.
  3. Fan R. K. Chung, Frank T. Leighton, and Arnold L. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic Discrete Methods, 8(1):33-58, 1987. URL: https://doi.org/10.1137/0608002.
  4. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Computing Surveys, 52:1-37, January 2020. URL: https://doi.org/10.1145/3301281.
  5. Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg. Geometric thickness of complete graphs. Journal of Graph Algorithms & Applications, 4(3):5-17, 2000. https://arxiv.org/abs/math/9910185, URL: https://doi.org/10.7155/jgaa.00023.
  6. Vida Dujmović and David R. Wood. Graph treewidth and geometric thickness parameters. Discrete & Computational Geometry, 37:641-670, 2007. https://arxiv.org/abs/math/0503553, URL: https://doi.org/10.1007/s00454-007-1318-7.
  7. Christian A. Duncan. On graph thickness, geometric thickness, and separator theorems. Computational Geometry, 44:95-99, February 2011. URL: https://doi.org/10.1016/j.comgeo.2010.09.005.
  8. Christian A. Duncan, David Eppstein, and Stephen G. Kobourov. The geometric thickness of low degree graphs. In SCG '04: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 340-346, New York, NY, USA, June 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/997817.997868.
  9. Stephane Durocher, Ellen Gethner, and Debajyoti Mondal. Thickness and colorability of geometric graphs. Computational Geometry, 56:1-18, 2016. URL: https://doi.org/10.1016/j.comgeo.2016.03.003.
  10. David Eppstein. Separating geometric thickness from book thickness. Preprint, 2001. URL: https://arxiv.org/abs/math/0109195.
  11. David Eppstein. Separating thickness from geometric thickness. In János Pach, editor, Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics. American Mathematical Society, 2004. URL: https://arxiv.org/abs/math/0204252.
  12. Lebrecht Henneberg. Die Graphische Statik der Starren Körper. In Felix Klein and Conrad Müller, editors, Encyklopädie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen: Vierter Band: Mechanik, pages 345-434, Wiesbaden, Germany, 1908. B. G. Teubner Verlag. URL: https://doi.org/10.1007/978-3-663-16021-2_5.
  13. Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach, and Gábor Tardos. Two extensions of the Erdős-Szekeres problem. Journal of the European Mathematical Society, 22(12):3981-3995, 2020. URL: https://doi.org/10.4171/JEMS/1000.
  14. Seok-Hee Hong and Takeshi Tokuyama, editors. Beyond Planar Graphs. Communications of NII Shonan Meetings. Springer, 2020. URL: https://doi.org/10.1007/978-981-15-6533-5.
  15. Joan P. Hutchinson, Thomas C. Shermer, and Andrew Vince. On representations of some thickness-two graphs. Computational Geometry, 13(3):161-171, 1999. URL: https://doi.org/10.1016/S0925-7721(99)00018-8.
  16. Rahul Jain, Marco Ricci, Jonathan Rollin, and André Schulz. On the geometric thickness of 2-degenerate graphs. Preprint, 2023. URL: https://arxiv.org/abs/2302.14721.
  17. Paul C. Kainen. Thickness and coarseness of graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 39:88-95, 1973. URL: https://doi.org/10.1007/BF02992822.
  18. Anthony Mansfield. Determining the thickness of graphs is NP-hard. Mathematical Proceedings of the Cambridge Philosophical Society, 93(1):9-23, 1983. URL: https://doi.org/10.1017/S030500410006028X.
  19. Petra Mutzel, Thomas Odenthal, and Mark Scharbodt. The thickness of graphs: A survey. Graphs and Combinatorics, 14:59-73, 1998. URL: https://doi.org/10.1007/PL00007219.
  20. Crispin St.J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 36:445-450, 1961. URL: https://doi.org/10.1112/jlms/s1-36.1.445.
  21. Crispin St.J. A. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 39:12, 1964. URL: https://doi.org/10.1112/jlms/s1-39.1.12.
  22. János Pach and Rephael Wenger. Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics, 17(4):717-728, 2001. URL: https://doi.org/10.1007/PL00007258.
  23. Sergey Pupyrev. Linear Graph Layouts. Accessed: 2022-11-30. URL: https://spupyrev.github.io/linearlayouts.html.
  24. Walter Schnyder. Embedding planar graphs on the grid. In SODA '90: Proceedings of the first annual ACM-SIAM Symposium on Discrete Algorithms, pages 138-148. Society for Industrial and Applied Mathematics, January 1990. URL: https://doi.org/10.5555/320176.320191.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact