Construction Sequences and Certifying 3-Connectedness

Jens M. Schmidt— 2009

Given two 3-connected graphs G and H, a construction sequence constructs G from H (e. g. from the K4) with three basic operations, called the Barnette-Grünbaum 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 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.

TitelConstruction Sequences and Certifying 3-Connectedness
VerfasserJens M. Schmidt
VerlagFreie Universität Berlin, Institut für Informatik
OrtTakustraße 9, 14195 Berlin
Themaconstruction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm
RechteInst.f. Informatik, FU Berlin