Construction sequences and certifying 3-connectivity

Publikationstyp
Journal Article
Date Issued
2012
Sprache
English
Author(s)
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7591
Journal
Algorithmica  
Volume
62
Start Page
192
End Page
208
Citation
Algorithmica (2012)
Publisher DOI
10.1007/s00453-010-9450-9
Publisher
Springer
Tutte proved that every 3-vertex-connected graph G on more than 4 vertices 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 K₄ can be computed in O(|V|²) time by extending Barnette's and Grünbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.
DDC Class
510: Mathematik