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.ICALP.2019.23
URN: urn:nbn:de:0030-drops-105991
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10599/
Go to the corresponding LIPIcs Volume Portal

Biedl, Therese ; Kindermann, Philipp

Finding Tutte Paths in Linear Time

pdf-format:
LIPIcs-ICALP-2019-23.pdf (0.9 MB)

Abstract

It is well-known that every planar graph has a Tutte path, i.e., a path P such that any component of G-P has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of G-P have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.

BibTeX - Entry

@InProceedings{biedl_et_al:LIPIcs:2019:10599,
  author =	{Therese Biedl and Philipp Kindermann},
  title =	{{Finding Tutte Paths in Linear Time}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10599},
  URN =		{urn:nbn:de:0030-drops-105991},
  doi =		{10.4230/LIPIcs.ICALP.2019.23},
  annote =	{Keywords: planar graph, Tutte path, Hamiltonian path, 2-walk, linear time}
}

Keywords: planar graph, Tutte path, Hamiltonian path, 2-walk, linear time
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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