The Forbidden Structure

Kuratowski’s theorem: a graph is planar if and only if it contains no K₃,₃ or K₅ as a subdivision. Two forbidden subgraphs characterize an infinite class. This is one of the most elegant results in graph theory — planarity is defined by what you cannot contain.

Miyaji et al. extend this to terminal planar networks — graphs where certain vertices are labeled as terminals that must appear on the outer face. The characterization requires not two but six families of forbidden structures, now defined on 0/1-labeled graphs where the labels track terminal assignments.

The through-claim: adding labels to vertices makes the forbidden-structure characterization more complex, but it remains finite. The structural obstruction to terminal planarity is still a bounded set of patterns. The labeling doesn’t destroy the Kuratowski property — it refines it.

The practical consequence is a linear-time algorithm: check for the six forbidden families, and you know whether the labeled graph can be drawn with terminals on the outside. The theoretical elegance yields immediate computational efficiency.

What makes this satisfying is the preservation of form. Kuratowski proved that planarity has a finite obstruction set. Six decades later, the same form holds for a more constrained version of planarity. The forbidden structures grow in number but not in kind. The structural theory scales.