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:
“There’s a theory, one I find persuasive, that the quest for knowledge is, at bottom, the search for the answer to the question: “Where was I before I was born.” In the beginning was ... what? Perhaps, in the beginning, there was a curious room, a room like this one, crammed with wonders; and now the room and all it contains are forbidden you, although it was made just for you, had been prepared for you since time began, and you will spend all your life trying to remember it.”
—Angela Carter (1940–1992)
“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)