DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.77

Toward Grünbaum’s Conjecture for 4-Connected Graphs

Authors: Christian Ortlieb

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

Abstract

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.

Cite as

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

DOI: 10.4230/LIPIcs.SWAT.2024.37

Toward Grünbaum’s Conjecture

Authors: Christian Ortlieb and Jens M. Schmidt

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

Abstract

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.

Cite as

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}
}

Search Results

Documents authored by Ortlieb, Christian

Toward Grünbaum’s Conjecture for 4-Connected Graphs

Abstract

Cite as

Toward Grünbaum’s Conjecture

Abstract

Cite as

Thanks for your feedback!

Could not send message