Options
Construction sequences and certifying 3-connectedness
Publikationstyp
Conference Paper
Date Issued
2010-03
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
5
Start Page
633
End Page
644
Citation
27th International Symposium on Theoretical Aspects of Computer Science (2010) 5: 633-644 (2010)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grünbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to the K4 can be computed in O(|V|2) time by extending Barnette and Grünbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.
Subjects
3-connected
Algorithms and data structures
Certifying algorithm
Construction sequence
Removable edges
Tutte contraction