A subgraph is formed by selecting part of a graph: a subset of its vertices, a subset of its edges, or both. Removing a vertex also removes its incident edges, while removing an edge preserves its endpoints. This gives a practical way to reduce a graph into smaller cases while preserving enough structure for analysis. section 15.2.4
Two useful subgraph families appear when counting the cases considered by a planarity algorithm:
- An induced subgraph is determined by choosing a subset of vertices; the selected vertices retain the edges connecting them. section 15.2.4
- A spanning subgraph is determined by choosing a subset of edges while considering the graph's vertices. section 15.2.4
- Planarity can be disproved when a graph contains K5, K3,3, or a subdivision of either as a subgraph. section 15.1.1
Subgraphs also provide the recursive states of a planarity test. The algorithm removes each possible vertex and edge, tests the resulting subgraph, and caches the result so that the same state is examined only once. With n vertices and m edges, the possible induced and spanning cases number 2^n and 2^m; the combined search space is bounded by 2^(n+m), still too large for graphs beyond roughly 20 vertices without stronger pruning. section 15.2.4
Recursive planarity testing
For a graph with vertices {1, 2, 3}, removing vertex 1 produces the subgraph on {2, 3}; removing vertex 2 produces the subgraph on {1, 3}; removing vertex 3 produces the subgraph on {1, 2}. A cached recursive implementation stores each result and returns it when the same subgraph reappears. section 15.2.4
Listing 15.7 Planarity testing with cache
function isPlanar(graph, cache={})
if graph in cache then return (cache[graph], cache) #1
if |graph.vertices| < 5 then return (true, cache)
if violatesEulerConstraints(graph) then #2
cache[graph] ← false
return (false, cache)
if isComplete(graph) or isNonPlanarCompleteBipartite(graph) then #3
cache[graph] ← false
return (false, cache)
for v in graph.vertices do #4
subG ← graph.remove(v)
(planar, cache) ← isPlanar(subG, cache) #5
if not planar then
cache[graph] ← false
return (false, cache)
for e in graph.edges do #6
subG ← graph.remove(e)
(planar, cache) ← isPlanar(subG, cache)
if not planar then
cache[graph] ← false
return (false, cache)
cache[graph] ← true #7
return (true, cache)
Inspect the cached planarity-testing pseudocode to see subgraphs used as recursive states, cache keys, and early rejection cases. section 15.2.4
