Kuratowski graph

2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]

A certain one-dimensional figure in three-dimensional space. A Kuratowski graph of the first type consists of the edges of a tetrahedron and one other segment joining the midpoints of two non-intersecting edges. A Kuratowski graph of the second type is the complete graph spanned by the vertices of a tetrahedron and a point in its interior. A graph $G$ is planar (cf. Graph, planar) if and only if it does not contain a Kuratowski graph of the first or second type (the Kuratowski–Pontryagin theorem).

References

[1]	C. Kuratowski, "Sur le problème des courbes gauches en topologie" Fund. Math. , 15 (1930) pp. 271–283
[2]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9

Comments

The first Kuratowski graph above is the complete bipartite graph $K_{3,3}$, and the second is the complete graph on 5 vertices, $K_5$.

The Kuratowski–Pontryagin theorem is also referred to as the Kuratowski theorem.

Results on the imbeddability of graphs into other Riemann surfaces, in particular into the projective plane or the torus, are contained in [a1], [a2]. Graph imbedding theorems are important in the design of chips, cf., e.g., [a3].

References

[a1]	R. Bodendieck, K. Wagner, "A characterization of the minimal basis of the torus" Combinatorica , 6 (1986) pp. 245–260
[a2]	J.Ch. Boland, "Embedding of graphs into orientable surfaces" Indag. Math. , 70 (1967) pp. 33–44
[a3]	J. Houg, K. Mehlkorn, A.L. Rosenberg, "Cost track-offs in graph embeddings, with applications" J. Assoc. Comp. Machinery , 30 (1983) pp. 709–728