Construction sequences and certifying 3-Connectedness
Construction sequences and certifying 3-Connectedness
Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Gruenbaum 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 the K_4 can be computed in O(|V|^2) time by extending Barnette and Gruenbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.
to be published in STACS 2010
- Freie Universität Berlin Germany
- Schloss Dagstuhl – Leibniz Center for Informatics Germany
- Leibniz Association Germany
FOS: Computer and information sciences, 3-connectedness, certifying algorithm, 3-connected graph, Discrete Mathematics (cs.DM), Tutte contraction, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], G.2.2, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::005 Computerprogrammierung, Programme, Daten, Computer Science - Data Structures and Algorithms, Algorithms and data structures, Data Structures and Algorithms (cs.DS), inductive characterization, F.2.2; G.2.2, 000, Construction sequence, construction sequence, 005, 3-connected, 004, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], F.2.2, removable edges, Computer Science - Discrete Mathematics, nested subdivisions, ddc: ddc:004
FOS: Computer and information sciences, 3-connectedness, certifying algorithm, 3-connected graph, Discrete Mathematics (cs.DM), Tutte contraction, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], G.2.2, 000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::005 Computerprogrammierung, Programme, Daten, Computer Science - Data Structures and Algorithms, Algorithms and data structures, Data Structures and Algorithms (cs.DS), inductive characterization, F.2.2; G.2.2, 000, Construction sequence, construction sequence, 005, 3-connected, 004, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], F.2.2, removable edges, Computer Science - Discrete Mathematics, nested subdivisions, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!