License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.676
URN: urn:nbn:de:0030-drops-49502
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4950/
Go to the corresponding LIPIcs Volume Portal

Schmid, Andreas ; Schmidt, Jens M.

Computing 2-Walks in Polynomial Time

pdf-format:
50.pdf (1 MB)

Abstract

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions.

We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

BibTeX - Entry

@InProceedings{schmid_et_al:LIPIcs:2015:4950,
  author =	{Andreas Schmid and Jens M. Schmidt},
  title =	{{Computing 2-Walks in Polynomial Time}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{676--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4950},
  URN =		{urn:nbn:de:0030-drops-49502},
  doi =		{10.4230/LIPIcs.STACS.2015.676},
  annote =	{Keywords: algorithms and data structures, 2-walks, 3-connected planar graphs, Tutte paths, 3-trees}
}

Keywords: algorithms and data structures, 2-walks, 3-connected planar graphs, Tutte paths, 3-trees
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI