A spanning subgraph keeps every vertex of an original graph while retaining only a subset of its edges. Removing one edge at a time therefore produces spanning subgraphs, unlike removing a vertex, which produces an induced subgraph. section 15.2.3
In recursive planarity testing, spanning subgraphs represent the branch obtained by deleting each possible edge. The algorithm tests these smaller graphs recursively alongside graphs formed by deleting vertices. section 15.2.3
For a graph G=(V,E), spanning-subgraph generation follows this pattern:
- Keep V unchanged. section 15.2.3
- Remove an edge e from E to form (V, E−{e}). section 15.2.3
- Repeat recursively, stopping when a planarity test reaches a base case or detects a non-planar structure. section 15.2.3
Counting the search space
A graph with m edges has 2^m spanning subgraphs because each edge can independently be retained or removed. Recursive edge-deletion algorithms can therefore encounter exponentially many possibilities. section 15.2.4
(V’,E’)=({2,3}, E-{1}), ({1,3}, E-{2}), ({1,2}, E-{3})
Shows the three spanning subgraphs produced by removing one of three edges while preserving the full vertex set. section 15.2.4
