Veröffentlichung
- Titel:
- On the Geometric Thickness of 2-Degenerate Graphs
- AutorInnen:
-
Rahul Jain
Marco Ricci
Jonathan Rollin
André Schulz - Kategorie:
- Konferenzbandbeiträge
- erschienen in:
- 39th International Symposium on Computational Geometry, SoCG 2023, pp. 44:1-44:15, Dallas, Texas, USA, June 12-15, 2023
- 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].
- Download:
- DOI
- BibTeX-Eintrag:
@InProceedings{jain_et_al:LIPIcs.SoCG.2023.44, author = {Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr\'{e}}, title = {{On the Geometric Thickness of 2-Degenerate Graphs}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {44:1--44:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17894}, URN = {urn:nbn:de:0030-drops-178946}, doi = {10.4230/LIPIcs.SoCG.2023.44}, annote = {Keywords: Degeneracy, geometric thickness, geometric arboricity} }