Namespaces
Variants
Actions

Difference between revisions of "Kuratowski graph"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k056/k056020/k0560201.png" /> is planar (cf. [[Graph, planar|Graph, planar]]) if and only if it does not contain a Kuratowski graph of the first or second type (the Kuratowski–Pontryagin theorem).
+
{{TEX|done}}
 +
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|Graph, planar]]) if and only if it does not contain a Kuratowski graph of the first or second type (the Kuratowski–Pontryagin theorem).
  
 
====References====
 
====References====
Line 7: Line 8:
  
 
====Comments====
 
====Comments====
The first Kuratowski graph above is the complete bipartite graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k056/k056020/k0560202.png" />, and the second is the complete graph on 5 vertices, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/k/k056/k056020/k0560203.png" />.
+
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.
 
The Kuratowski–Pontryagin theorem is also referred to as the Kuratowski theorem.

Revision as of 16:44, 22 June 2014

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=13376
This article was adapted from an original article by B.A. Efimov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article