Namespaces
Variants
Actions

Difference between revisions of "Kuratowski graph"

From Encyclopedia of Mathematics
Jump to: navigation, search
(links)
m (+ category)
 
(One intermediate revision by one other user not shown)
Line 14: Line 14:
  
 
====Comments====
 
====Comments====
The first Kuratowski graph above is the complete bipartite graph $K_{3,3}$ (cd [[Graph, bipartite]], and the second is the complete graph on 5 vertices, $K_5$.
+
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.
Line 26: Line 26:
 
<TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Houg,  K. Mehlkorn,  A.L. Rosenberg,  "Cost track-offs in graph embeddings, with applications"  ''J. Assoc. Comp. Machinery'' , '''30'''  (1983)  pp. 709–728</TD></TR>
 
<TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Houg,  K. Mehlkorn,  A.L. Rosenberg,  "Cost track-offs in graph embeddings, with applications"  ''J. Assoc. Comp. Machinery'' , '''30'''  (1983)  pp. 709–728</TD></TR>
 
</table>
 
</table>
 +
[[Category:Graph theory]]

Latest revision as of 20:09, 15 March 2023


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