Finding triconnected components of graphs

DOI10.1080/03081088308817513zbMath0514.05039OpenAlexW2086301589WikidataQ126250257 ScholiaQ126250257MaRDI QIDQ3659812

Kiem-Phong Vo

Publication date: 1983

Published in: Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03081088308817513

zbMATH Keywords

depth first searchtriconnected component

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items (11)

Searching forK_3,3in linear time ⋮ Ranking and unranking planar embeddings ⋮ On finding optimal and near-optimal lineal spanning trees ⋮ Determining when a graphic matroid is transversal in linear time ⋮ A matrix analysis of carrier posets of biconnected graphs ⋮ Construction sequences and certifying 3-connectivity ⋮ Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge ⋮ Polynomial-time Classification of Skew-symmetrizable Matrices with a Positive Definite Quasi-Cartan Companion ⋮ Certifying 3-edge-connectivity ⋮ Tractable minor-free generalization of planar zero-field Ising models ⋮ An approach to the subgraph homeomorphism problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A structural characterization of planar combinatorial graphs
• Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
• Embedding Graphs in the Plane—Algorithmic Aspects
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Network Flow and Testing Graph Connectivity
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Finding triconnected components of graphs