Embedding On A Surface
It is evident that subdividing a graph preserves planarity. Kuratowski's theorem states that
- a finite graph is planar if and only if it contains no subgraph homeomorphic to K5 (complete graph on five vertices) or K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three).
In fact, a graph homeomorphic to K5 or K3,3 is called a Kuratowski subgraph.
A generalization, flowing from the Robertson–Seymour theorem, asserts that for each integer g, there is a finite obstruction set of graphs such that a graph H is embeddable on a surface of genus g if and only if H contains no homeomorphic copy of any of the . For example, contains the Kuratowski subgraphs.
Read more about this topic: Homeomorphism (graph Theory)
Famous quotes containing the word surface:
“I have passed down the river before sunrise on a summer morning, between fields of lilies still shut in sleep; and when, at length, the flakes of sunlight from over the bank fell on the surface of the water, whole fields of white blossoms seemed to flash open before me, as I floated along, like the unfolding of a banner, so sensible is this flower to the influence of the sun’s rays.”
—Henry David Thoreau (1817–1862)