×

A combinatorial condition for planar graphs. (English) JFM 63.0548.01

Verf. kennzeichnet die Graphen, die (singularitätenfrei) in die Ebene eingebettet werden können, folgendermaßen: Dann und nur dann ist ein Graph planar, wenn er eine solche Basis der Kreise besitzt (“zweifache Basis”), daß keine seiner Strecken in mehr als zwei Kreisen der Basis auftritt. (Kreis \(=\) einfach geschlossener Streckenzug; Basis \(\mod 2\) genommen.) Zum Beweis kann man sich auf nicht-separable Graphen beschränken. Für einen nicht-separablen Graphen – in die Ebene eingebettet -liefern offenbar die Grenzen der beschränkten Gebiete eine zweifache Basis der Kreise, und umgekehrt zeigt Verf., daß jeder derartigen Basis eine Einbettung des Graphen in die Ebene entspricht, bei der die Basiskreise Grenzen der beschränkten Gebiete werden; das geschieht durch einen Induktionsschluß nach der Nullität des Graphen.
Schließlich zeigt Verf. auf kombinatorischem Wege, daß sein Kriterium mit der von Whitney (Trans. Amer. math. Soc. 34 (1932), 339-362; JFM 58.0608.*) gefundenen Bedingung der Existenz des (kombinatorisch) dualen Graphen gleichwertig ist. Der Übergang von der Existenz einer zweifachen Basis der Kreise zum dualen Graphen erfolgt z. B. dadurch, daß man jedem Kreis der Basis eine Ecke, zwei Kreisen, die eine Strecke gemeinsam haben, die Verbindung der entsprechenden Ecken zuordnet.

Citations:

JFM 58.0608.*
PDFBibTeX XMLCite
Full Text: EuDML