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:
“Panoramas are not what they used to be.
Claude has been dead a long time
And apostrophes are forbidden on the funicular.
Marx has ruined Nature,
For the moment.”
—Wallace Stevens (1879–1955)
“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)