Construction Sequences and Certifying 3-connectivity |
| |
Authors: | Jens M Schmidt |
| |
Affiliation: | 1. Dept. of Computer Science, Freie Universit?t Berlin, Berlin, Germany
|
| |
Abstract: | Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grünbaum 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 K 4 can be computed in O(|V|2) time by extending Barnette’s and Grünbaum’s theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|