Construction sequences and certifying 3-Connectedness
Schmidt, Jens M. ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleConstruction sequences and certifying 3-Connectedness
AuthorSchmidt, Jens M.
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages12 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; [20]09,01
Keywordsconstruction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm
Classification (DDC)005 Computer programming, programs, data
AbstractGiven 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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication2009
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-11-20 : 12:46:57
Last changed2015-02-27 : 08:25:18
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000004356