Options
Contractions, removals, and certifying 3-connectivity in line AR time
Publikationstyp
Journal Article
Date Issued
2013-07-18
Sprache
English
Author(s)
TORE-URI
Journal
Volume
42
Issue
2
Start Page
494
End Page
535
Citation
SIAM Journal on Computing (2013)
Publisher DOI
Scopus ID
Publisher
SIAM
One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(|V|2) to O(|E|). This result has a number of consequences; an important one is a new linear-time test of 3-connectivity that is certifying; finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(|E|). We show how to extend the results to an optimal certifying test of 3-edge-connectivity. © 2013 Society for Industrial and Applied Mathematics.
Subjects
3-connected graph
Certifying algorithm
Construction sequence
Inductive characterization
Nested subdivisions
DDC Class
510: Mathematik