An induced subgraph is formed by selecting vertices from a graph and retaining every original edge whose endpoints both remain selected. Removing a vertex therefore removes that vertex and all incident edges, while preserving all edges among the surviving vertices. section 15.2.3
In recursive planarity testing, induced subgraphs provide one decomposition branch: remove each vertex in turn, then test the resulting graph. This contrasts with spanning subgraphs, which remove edges while retaining the vertex set. section 15.2.3
Removing vertices recursively
Given 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}. Each result keeps exactly the original edges whose endpoints remain. section 15.2.3
Use induced subgraphs in recursive graph algorithms by:
- Selecting a vertex to remove. section 15.2.3
- Constructing the induced subgraph on the remaining vertices. section 15.2.3
- Applying the recursive test and stopping early when a base case or non-planarity condition is reached. section 15.2.3
- Caching results so each distinct subgraph is examined at most once. section 15.2.4
