Document

**Published in:** LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Given a spanning tree T of a 3-connected planar graph G, the co-tree of T is the spanning tree of the dual graph G^* given by the duals of the edges that are not in T. Grünbaum conjectured in 1970 that there is such a spanning tree T such that T and its co-tree both have maximum degree at most 3.
In 2014, Biedl proved that there is a spanning tree T such that T and its co-tree have maximum degree at most 5. Using structural insights into Schnyder woods, Schmidt and the author recently improved this bound on the maximum degree to 4. In this paper, we prove that in a 4-connected planar graph there exists a spanning tree T of maximum degree at most 3 such its co-tree has maximum degree at most 4. This almost solves Grünbaum’s conjecture for 4-connected graphs.

Christian Ortlieb. Toward Grünbaum’s Conjecture for 4-Connected Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ortlieb:LIPIcs.MFCS.2024.77, author = {Ortlieb, Christian}, title = {{Toward Gr\"{u}nbaum’s Conjecture for 4-Connected Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {77:1--77:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.77}, URN = {urn:nbn:de:0030-drops-206339}, doi = {10.4230/LIPIcs.MFCS.2024.77}, annote = {Keywords: 4-connected planar graph, spanning tree, maximum degree, Schnyder wood, Gr\"{u}nbaum} }

Document

**Published in:** LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Given a spanning tree T of a planar graph G, the co-tree of T is the spanning tree of the dual graph G^* with edge set (E(G)-E(T))^*. Grünbaum conjectured in 1970 that every planar 3-connected graph G contains a spanning tree T such that both T and its co-tree have maximum degree at most 3.
While Grünbaum’s conjecture remains open, Biedl proved that there is a spanning tree T such that T and its co-tree have maximum degree at most 5. By using new structural insights into Schnyder woods, we prove that there is a spanning tree T such that T and its co-tree have maximum degree at most 4. This tree can be computed in linear time.

Christian Ortlieb and Jens M. Schmidt. Toward Grünbaum’s Conjecture. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ortlieb_et_al:LIPIcs.SWAT.2024.37, author = {Ortlieb, Christian and Schmidt, Jens M.}, title = {{Toward Gr\"{u}nbaum’s Conjecture}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {37:1--37:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.37}, URN = {urn:nbn:de:0030-drops-200777}, doi = {10.4230/LIPIcs.SWAT.2024.37}, annote = {Keywords: Planar graph, spanning tree, maximum degree, Schnyder wood} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail