Schmidt, Jens M.
Construction Sequences and Certifying 3Connectedness
Abstract
Given two $3$connected graphs $G$ and $H$, a \emph{construction sequence} constructs $G$ from $H$ (e.\,g. from the $K_4$) with three basic operations, called the \emph{BarnetteGr\"unbaum operations}. These operations are known to be able to construct all $3$connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in $G$ and showing under some minor assumptions that there is still a construction sequence to $G$ when we start from an \emph{arbitrary prescribed} $H$subdivision. This leads to the first algorithm that computes a construction sequence in time $O(V(G)^2)$. As an application, we develop a certificate for the $3$connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on $3$connectedness is designed.%Finding certifying algorithms is a major goal for problems where the efficient solutions known are complicated.
Tutte proved that every $3$connected graph on more than $4$ nodes has a \emph{contractible edge}. Barnette and Gr\"unbaum proved the existence of a \emph{removable edge} in the same setting. We show that the sequence of contractions and the sequence of removals from $G$ to the $K_4$ can be computed in $O(V^2)$ time by extending Barnette and Gr\"unbaum's theorem. As an application, we derive a certificate for the $3$connectedness of graphs that can be easily computed and verified.
BibTeX  Entry
@InProceedings{schmidt:LIPIcs:2010:2491,
author = {Jens M. Schmidt},
title = {{Construction Sequences and Certifying 3Connectedness}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {633644},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2491},
URN = {urn:nbn:de:0030drops24918},
doi = {10.4230/LIPIcs.STACS.2010.2491},
annote = {Keywords: Construction sequence, 3connected graph, nested subdivisions, inductive characterization, 3connectedness, certifying algorithm}
}
2010
Keywords: 

Construction sequence, 3connected graph, nested subdivisions, inductive characterization, 3connectedness, certifying algorithm 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

2010 