2026-07-23T15:49:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17894 2024-03-06T11:00:38Z ddc:004 open_access

On the Geometric Thickness of 2-Degenerate Graphs Jain, Rahul Ricci, Marco Rollin, Jonathan Schulz, André Degeneracy geometric thickness geometric arboricity 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rahul Jain and Marco Ricci and Jonathan Rollin and André Schulz 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.44 urn:nbn:de:0030-drops-178946 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.44 eng https://creativecommons.org/licenses/by/4.0/legalcode