7. Planare Graphen

Für jeden Graphen stellt sich die Frage nach einer „guten“ Darstellung durch ein Ecken-Kanten-Diagramm. Die „Güte“ ist, wie wir bereits gesehen haben, abhängig davon, welche Struktureigenschaften wir betonen und anschaulich darstellen möchten: Kreise werden wir in der Regel als Kreise zeichnen, bipartite Graphen mit gegenüberliegenden Eckenmengen, Bäume oft in gestufter Form. Eine aus geometrischer Sicht besonders ausgezeichnete Qualität ist die Überschneidungsfreiheit der Kanten, und in diesem Kapitel stehen die Graphen, die sich überschneidungsfrei zeichnen lassen, im Mittelpunkt. Viele wichtige Beispiele für solche Graphen entstehen dabei durch räumliche Polyeder.