###### Options

# Certifying 3-connectivity in linear time

Publikationstyp

Conference Paper

Publikationsdatum

2012-12-01

Sprache

English

Author

TORE-URI

First published in

Number in series

7391 LNCS

Issue

PART 1

Start Page

786

End Page

797

Citation

International Colloquium on Automata, Languages, and Programming (ICALP 2012)

Publisher DOI

Scopus ID

One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and based on the following fact: Every 3-vertex-connected graph G 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 K 4 such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grünbaum yields a similar sequence using removals of 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|). Based on this result, we give a 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 the last years. The 3-connectivity test is conceptually different from well-known linear-time tests of 3-connectivity; it uses a certificate that is easy to verify in time O(|E|). We also provide an optimal certifying test of 3-edge-connectivity.