Namespaces
Variants
Actions

Kuratowski graph

From Encyclopedia of Mathematics
Jump to: navigation, search


2010 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
How to Cite This Entry:
Kuratowski graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Kuratowski_graph&oldid=37069
This article was adapted from an original article by B.A. Efimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article