Forbidden Graph Characterizations
Outerplanar graphs have a forbidden graph characterization analogous to Kuratowski's theorem and Wagner's theorem for planar graphs: a graph is outerplanar if and only if it does not contain a subdivision of the complete graph K4 or the complete bipartite graph K2,3. Alternatively, a graph is outerplanar if and only if it does not contain K4 or K2,3 as a minor, a graph obtained from it by deleting and contracting edges.
A triangle-free graph is outerplanar if and only if it does not contain a subdivision of K2,3.
Read more about this topic: Outerplanar Graph
Famous quotes containing the words forbidden and/or graph:
“That’s metaphysics, my dear fellow. It’s forbidden me by my doctor, my stomach won’t take it.”
—Boris Pasternak (1890–1960)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)