×

A structural characterization of planar combinatorial graphs. (English) JFM 63.0549.01

Whitneys nicht separable (oder zyklisch zusammenhängende) Graphen (Trans. Amer. math. Soc. 34 (1932), 339-362; JFM 58.0608.*), die keine trennende Ecke mehr enthalten, werden durch trennende Eckenpaare in feinere Bestandteile aufgespalten. \(G\) sei nicht-separabel. Ist \(G = H + H'\) (\(H\) und \(H'\) echte Teilgraphen von \(G\)) und der Durchschnitt \(H \cap H' = h_1 + h_2\) (\(h_1\) und \(h_2\) zwei Ecken von \(G\)) und ist dabei weder \(H\) noch \(H'\) eine Kette (einfacher Streckenzug) zwischen \(h_1\) und \(h_2\), so liegt eine “Spaltung” (split) von \(G\) vor. (Ohne die Nebenbedingung, daß keine Kette auftritt, redet Verf. von “semisplit”.) Sind \(X \subset H'\) und \(X' \subset H\) Ketten zwischen \(h_1\) und \(h_2\), so heißen \(H + X\), \(H' + X'\) die “Blöcke” der Spaltung. (Auf die spezielle Wahl der Ketten kommt es nicht an, Unterteilungen sind unwesentlich.) Läßt der zyklisch zusammenhängende Graph \(G\) keine Spaltung zu, so heißt \(G\) “dreifach zusammenhängend” abgesehen von folgenden Ausnahmen: \(G\) ist ein Kreis (einfach geschlossener Streckenzug) oder ein “Verzweigungsgraph” (branch graph) der Ordnung \(n(>2)\), gebildet aus zwei durch \(n\) paarweise fremde Ketten verbundenen Ecken. Bei fortgesetzter Spaltung gelangt man schließlich zu einem System von unspaltbaren Graphen und Verzweigungsgraphen; die dreifach zusammenhängenden unter ihnen heißen “Atome” von \(G\). Die Atome lassen sich invariant als maximale dreifach zusammenhängende Teilgraphen kennzeichnen, woraus sich die Eindeutigkeit (bis auf Homöomorphie) der Zerspaltung in Atome ergibt.
Hat man einen dreifach zusammenhängenden Graphen \(G\) auf die Kugelfläche gelegt, so sind die Gebietsgrenzen die einzigen \(G\) nicht zerlegenden Kreise von \(G\); jede Strecke von \(G\) kommt in genau zwei solchen Kreisen vor, und wenn man einen Kreis wegläßt, bilden die übrigen eine Basis der Kreise von \(G\) (vgl. auch das vorangehende Referat). Hat umgekehrt die Gesamtheit der den dreifach zusammenhängenden Graphen \(G\) nicht zerlegenden Kreise diese beiden Eigenschaften, so läßt sich \(G\) in die Sphäre einbetten, und dabei werden die \(G\) nicht zerlegenden Kreise Gebietsgrenzen. Das liefert ein brauchbares Kriterium für die Möglichkeit der Einbettung und zeigt, daß sich \(G\) – wenn überhaupt – im wesentlichen nur auf eine Weise auf die Kugel legen läßt.
Die Benutzung der Blöcke \(H + X\), \(H' + X'\) (anstatt der Bestandteile \(H\), \(H'\)) hat zur Folge, daß sich die Einbettungen der Blöcke eines gespaltenen Graphen \(G\) in die Sphäre zu einer Einbettung von \(G\) zusammensetzen lassen. Da die Einbettung der Atome (wenn sie möglich ist) im wesentlichen eindeutig ist und die Einbettungsmöglichkeiten der Verzweigungsgraphen leicht zu übersehen sind, ergibt sich eine Abzählung der topologisch verschiedenen Einbettungen von \(G\).

Citations:

JFM 58.0608.*
PDFBibTeX XMLCite
Full Text: DOI