A biconnected component is a maximal graph substructure that remains connected after removing any single vertex. Equivalently, every pair of vertices has two paths that share no internal vertex or edge. Decomposing a graph into these components lets planarity testing handle smaller subgraphs independently. section 15.2.2
Use biconnected components to structure graph algorithms:
- Separate a graph into biconnected components before testing planarity; the original graph is planar exactly when every component is planar. section 15.2.2
- Find the components with a modified depth-first search; this is more involved than finding ordinary connected components. section 15.2.3
- Run the chosen planarity test independently on each resulting component and reject the graph when any component is nonplanar. section 15.2.3
Listing 15.1 Planarity testing template algorithm
function planarityTesting(graph, isPlanar) #1
components ← biconnectedComponents(graph) #2
for G in components do #3
if not isPlanar(G) then #4
return false
return true #5
The template shows the operational pattern: compute biconnected components, test each one, and return false as soon as a component fails. section 15.2.3
