1 Search Results for "Goetze, Miriam"

Document
DOI: 10.4230/LIPIcs.ESA.2022.62
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

Authors: Miriam Goetze, Paul Jungeblut, and Torsten Ueckerdt

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an n-vertex planar graph, augments this graph in 𝒪(n²) steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized (Anti)factor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.
Cite as

Miriam Goetze, Paul Jungeblut, and Torsten Ueckerdt. Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goetze_et_al:LIPIcs.ESA.2022.62,
  author =	{Goetze, Miriam and Jungeblut, Paul and Ueckerdt, Torsten},
  title =	{{Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.62},
  URN =		{urn:nbn:de:0030-drops-170007},
  doi =		{10.4230/LIPIcs.ESA.2022.62},
  annote =	{Keywords: edge colorings, planar graphs, cubic graphs, generalized factors, SPQR-tree}
}
  • Refine by Author
  • 1 Goetze, Miriam
  • 1 Jungeblut, Paul
  • 1 Ueckerdt, Torsten

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 SPQR-tree
  • 1 cubic graphs
  • 1 edge colorings
  • 1 generalized factors
  • 1 planar graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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