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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Albroscheit, S.: Ein Algorithmus zur Konstruktion gegebener 3-zusammenhängender Graphen (in German). Diploma thesis, Freie Universität Berlin (2006)
Barnette, D.W., Grünbaum, B.: On Steinitz’s theorem concerning convex 3-polytopes and on some properties of 3-connected graphs. In: Many Facets of Graph Theory. Lecture Notes in Mathematics, pp. 27–40. Springer, Berlin (1969)
Blum, M., Kannan, S.: Designing programs that check their work. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC’89), New York, pp. 86–97 (1989)
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704–714 (1976)
Halin, R.: Zur Theorie der n-fach zusammenhängenden Graphen. Abh. Math. Semin. Univ. Hamb. 33(3), 133–164 (1969)
Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135–158 (1973)
Kelmans, A.K.: Graph expansion and reduction. In: Algebraic Methods in Graph Theory, Szeged, Hungary, vol. 1, pp. 317–343 (1978)
Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.P.: Certifying algorithms for recognizing interval graphs and permutation graphs. SIAM J. Comput. 36(2), 326–353 (2006). Preliminary version in SODA 2003, pp. 158–167
Mehlhorn, K., Näher, S.: From algorithms to working programs: On the use of program checking in LEDA. In: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS’98), pp. 84–93 (1998)
Mehlhorn, K., Näher, S., Seel, M., Seidel, R., Schilz, T., Schirra, S., Uhrig, C.: Checking geometric programs or verification of geometric structures. Comput. Geom. Theory Appl. 12(1–2), 85–103 (1999)
Menger, K.: Zur allgemeinen Kurventheorie. Fund. Math. 10, 96–115 (1927)
Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7(1–6), 583–596 (1992)
Schmidt, J.M.: Construction sequences and certifying 3-connectedness. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10), Nancy, France, pp. 633–644 (2010)
Thomassen, C.: Kuratowski’s theorem. J. Graph Theory 5(3), 225–241 (1981)
Thomassen, C.: Reflections on graph theory. J. Graph Theory 10(3), 309–324 (2006)
Titov, V.K.: A constructive description of some classes of graphs. Ph.D. Thesis, Moscow (1975)
Tutte, W.T.: A theory of 3-connected graphs. Indag. Math. 23, 441–455 (1961)
Tutte, W.T.: Connectivity in graphs. In: Mathematical Expositions, vol. 15. University of Toronto Press, Toronto (1966)
Vo, K.-P.: Finding triconnected components of graphs. Linear Multilinear Algebra 13, 143–165 (1983)
Vo, K.-P.: Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs. Linear Multilinear Algebra 13, 119–141 (1983)
West, D.B.: Introduction to Graph Theory. Prentice Hall, New York (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the Deutsche Forschungsgemeinschaft within the research training group “Methods for Discrete Structures” (GRK 1408) and is an extended version of [13].
Rights and permissions
About this article
Cite this article
Schmidt, J.M. Construction Sequences and Certifying 3-connectivity. Algorithmica 62, 192–208 (2012). https://doi.org/10.1007/s00453-010-9450-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9450-9