The most celebrated result
about the planarity of graphs is Kuratowski's theorem. We say that
two graphs G and G' are isomorphic modulo vertices of degree 2 if
G is isomorphic to a graph G" obtained from G' by the addition or deletion
of vertices with just two edges incident:
 Pontryagin-Kuratowski's theorem Let G be a finite graph. Then G is planar iff it contains no subgraph isomorphic modulo vertices of degree 2 to K5 or K3,3. The transformations described are a subdivision and a contraction of a graph edge. A subdivision of a graph G is a graph obtained from G by a finite number of the operations of the following form: introduce a new vertex x and replace an edge vw by two edges vx and xw, i.e. insert a vertex x in the middle of an existing edge vw. An elementary contraction of a graph is the operation of replacing two adjacent vertices by a single vertex: the new vertex is joined to every other vertex which was joined to one or both original two vertices. A contraction of G is any graph that can be obtained from G by a finite sequence of elementary contractions. The same operations, subdivision and contraction, can be applied on any line segment AB in Â3 replacing it by two line segments AC and CB or vice versa. In the language of contraction, Pontryagin-Kuratowski's theorem can be formulated as: A graph G is planar iff it contains no subgraph which has K5 or K3,3 as a contraction. In considering KLs, a
special contraction, contraction of both edges of a bigon, will play an
important role. We will call such a contraction a
bigon collapse.
|
