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:
“I do not find fault with equality for drawing men into the pursuit of forbidden pleasures, but for absorbing them entirely in the search for the pleasures that are permitted.”
—Alexis de Tocqueville (1805–1859)
“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)