Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-25T04:02:32.114Z Has data issue: false hasContentIssue false
  • English
  • Français

The Non-Biplanar Character of the Complete 9-Graph

Published online by Cambridge University Press:  20 November 2018

W. T. Tutte
W. T. Tutte*
Affiliation:
University of Waterloo
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let us define a planar partition of a graph G as a pair {H1, H2} of subgraphs of G with the following properties

  1. (i) Each of H1 and H2 includes all the vertices of G.

  2. (ii) Each edge of G belongs to just one of H1 and H2.

  3. (iii) H1 and H2 are planar graphs.

It is not required that H1 and H2 are connected. Moreover either of these graphs may have isolated vertices, incident with none of its edges.

We describe a graph having a planar partition as biplanar.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 6 , Issue 3 , 01 September 1963 , pp. 319 - 330
Copyright
Copyright © Canadian Mathematical Society 1963

References

1. Dirac, G. A. and Schuster, S., A theorem of Kuratowski, Proc. of the Nederl. Ak. W., 57(1954), 343-348.Google Scholar
2. Battle, J., Harary, F. and Kodama, Y., Every planar graph with nine points has a non-planar complement, Bull. Amer. Math. Soc, 68(1962), 569-571.Google Scholar
3. Kuratowski, C., Sur le problème des courbes gauches en Topologie, Fundam. Math., 15(1930), 271-283.Google Scholar
4. Tutte, W. T., A census of planar triangulations, Can. J. Math. 14 (1962), 21-38.Google Scholar