Planarität und Zeichnen erklärt
Eine Landkarte, ein Verteilnetz und eine Leiterplatte haben etwas gemeinsam: Man möchte sie ohne Überkreuzung zeichnen. Ob das geht, ist eine Eigenschaft des Netzes, nicht der Zeichnung, und ein planares Netz hat viel mehr Struktur als ein beliebiges: Vier Farben genügen, wenige Knoten teilen es in zwei Hälften, ein Fluss ist ein kürzester Weg im Dualgraphen, und perfekte Paarungen lassen sich zählen. Diese Linie nimmt die Frage neunmal in die Hand: Was gewinnt man, wenn ein Netz planar ist, wie belegt man es, und wie zeichnet man ein Netz so, dass man es lesen kann?
Die Stücke bauen auf der Wurzel auf: erst Planarität erkennen und belegen, dann färben, trennen, zeichnen (auch geschichtet), den Dualgraphen nutzen, Schichten zerlegen und zählen, am Ende fast planare Netze planarisieren. Gerechnet wird auf zufälligen Karten (Delaunay-Triangulierungen), Gittern, Lehrbuch-Graphen und einem Auszug der Straßenkarte von Toronto (OpenStreetMap, ODbL); echte Verteil- oder Leiterplattennetze gehören nicht dazu.
In short: Interactive demos on planar graphs: planarity testing with embedding and Kuratowski witness, colouring, planar separators, graph drawing and layered drawing, the dual graph for maximum flow, the Baker technique, counting perfect matchings, and planarization of near-planar networks.
Hintergrund zum Thema: Netzwerkdesign.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Die neun Stücke im Überblick
Die Linie hat eine Wurzel und fünf Stränge. Wer ein Netz auf Planarität prüft, kann danach färben, in zwei Hälften trennen, zeichnen, einen Fluss als kürzesten Weg im Dualgraphen rechnen oder perfekte Paarungen zählen. Zwei Stränge gehen weiter: Aus den Trennmengen wird die Baker-Technik, aus dem Zeichnen das geschichtete Zeichnen.
Das letzte Stück ist ein Zusammenfluss: Fast planare Netze zu planarisieren braucht die Wurzel (die Toronto-Karte ist nicht planar), das Zeichnen (Kreuzungen zählen) und den Dualgraphen (eine Kante über den kürzesten Dualweg einsetzen).
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Der gestrichelte Doppelpfeil ist ein Kontrast (Fluss gegen Dualweg), gepunktete Pfeile übernehmen nur eine Idee, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Graphen und Netzwerke — Die Graphfärbung färbt beliebige Graphen mit Greedy, DSATUR und exakt; die Demo zum Färben planarer Graphen dieser Linie misst, dass auf Karten schon bei 100 Standorten DSATUR die vier Farben des Vierfarbensatzes meist nicht mehr findet.
- Härte und Struktur — Kleine Trennmengen erklären, warum Gitter und Straßennetze eine kleine Baumweite haben (Baumweite): die Separator-Demo misst es. Die Baker-Technik rechnet die Reste nach dem Entfernen jeder k-ten Schicht mit der Programmierung auf der Zerlegung.
- Netzwerkfluss — Im planaren Netz ist der kleinste Schnitt ein kürzester Weg im Dualgraphen. Die Dualgraph-Demo stellt diesen Weg neben Dinic und zeigt, bei welchen Kapazitäten der Dualweg gewinnt und wann ein einziger Dinic-Durchlauf reicht.
- Spannbäume — Die Delaunay-Triangulierung des euklidischen Spannbaums liefert den Demos dieser Linie die planaren Karten. Wie bei den zufälligen Spannbäumen zählt die Demo zu Kasteleyn mit einer Determinante, statt zu probieren, und zieht gleichverteilt aus den Zählungen.
- Ordnung und Abhängigkeit — Das geschichtete Zeichnen in der Sugiyama-Demo zeichnet Abhängigkeitspläne so, dass jede Beziehung nach unten zeigt; enthält der Plan einen Kreis, bricht es ihn zuerst, wie es das Auflösen der Kreise dieser Nachbarlinie mit wenigen gestrichenen Beziehungen tut.
- Kürzeste Wege — Der Auszug der Straßenkarte von Toronto stammt aus dem Datensatz der Breitensuche im Straßennetz. Die verschachtelte Zerlegung aus Trennmengen, die die Separator-Demo als Eliminationsordnung misst, ist auch das Verfahren hinter der Ordnung der Customizable Contraction Hierarchies.
- Schnitte und Zusammenhang — Die Bisektion der Linie „Schnitte und Zusammenhang“ teilt ein beliebiges Netz mit Tauschen und Verschieben in zwei gleich große Hälften; die Separator-Demo dieser Linie nutzt dafür die Planarität. Das mehrstufige Teilen misst, wann sich das Vergröbern lohnt.
- Netzmodelle — Die Demo zu räumlichen Netzen legt Modelle auf dieselben Standorte wie die Straßenkarte aus dem Zeichnen und Planarisieren: Die Karte hat 125 Streckenkreuzungen, ein geometrischer Zufallsgraph 5 336, und kein Modell trifft nach den Schwellen der Demo mehr als 2 von 4 Kennzahlen.
Planarität erkennen und belegen
Verfolgen Sie, wie man einem Netz ansieht, ob es sich ohne Überkreuzung zeichnen lässt, und wie man die Antwort belegt: bei „ja“ mit einer Einbettung, bei „nein“ mit einer Unterteilung von K5 oder K3,3. Die Demo schickt Zufallsnetze und die Straßenkarte von Toronto durch den Test. Der Haken: Die Karte ist nicht planar, aber 52 Kanten genügen; warum, verraten die Daten nicht.
Demo starten →Planare Graphen färben
Sehen Sie, wie viele Farben eine Karte braucht: Der Vierfarbensatz garantiert vier, doch die einfachen Verfahren finden sie nicht mehr, sobald die Karte wächst. Bei 100 Standorten endet DSATUR nur noch in 5 % der Karten bei vier Farben; Kempe-Ketten holen die Vier meist zurück. Der Haken: Auf Zufallskarten wird die Kette des Fünffarben-Beweises in 0 von 60 Läufen gebraucht.
Demo starten →Planare Separatoren
Verfolgen Sie, warum sich Karten und Straßennetze mit wenigen Knoten in zwei Hälften teilen lassen: Es genügt etwa die Wurzel der Knotenzahl, bei Zufallsnetzen ein fester Anteil. Die Demo vergleicht drei Schnitte und prüft, was das für die Baumweite heißt. Der Haken: Die verschachtelte Zerlegung gewinnt trotz Garantie meist nicht; bei Toronto Breite 73 gegen 57 mit der Mindestgrad-Regel.
Demo starten →Graphen zeichnen
Sehen Sie, dass kein Zeichenverfahren alles kann: Federmodell und Stress-Minimierung sind lesbar, aber auf keiner der 30 Karten kreuzungsfrei; Tutte und Gitterzeichnung garantieren es, taugen aber nur für manche Netze. Die Demo lässt Sie die Netztypen wechseln. Der Haken: Bei der Zwiebel verliert Tutte etwa den Faktor 5 an Auflösung je Stufe.
Demo starten →Geschichtetes Zeichnen
Verfolgen Sie, wie ein Abhängigkeitsplan so gezeichnet wird, dass jede Beziehung nach unten zeigt: Kreise brechen, Aufgaben in Schichten legen, lange Kanten durch Hilfsknoten teilen, Kreuzungen zählen und mit dem exakten Optimum vergleichen. Der Haken: Der Schwerpunkt mit einem Start liegt auf mehrschichtigen Plänen das 1,3- bis 2,0-Fache über dem Optimum, und das Federmodell kreuzt weniger.
Demo starten →Der Dualgraph
Sehen Sie, wie sich der größte Fluss in einem planaren Netz als kürzester Weg im Dualgraphen berechnen lässt: Der Weg ist zugleich der kleinste Schnitt. Auf einem Gitter mit 100 × 100 Knoten und Kapazitäten bis 9 durchsucht er 177,9-mal weniger Kanten als Dinic. Der Haken: Bei gleichen Kapazitäten reicht Dinic ein Durchlauf und ist schneller, und die Einbettung zu suchen kostet mehr als der ganze Fluss.
Demo starten →Schichten zerlegen
Verfolgen Sie, wie man in einem planaren Netz eine große unabhängige Menge näherungsweise findet: jede k-te Schicht streichen, die Reste auf der Zerlegung exakt rechnen, die beste Verschiebung nehmen. Die Technik sichert einen Anteil des Optimums zu, der mit k wächst. Der Haken: Die Praxis liegt weit darüber (93,6 % bei k = 6 auf 400 Standorten), doch die einfache Lokalsuche erreicht 99,2 % und ist schneller.
Demo starten →Zählen auf planaren Graphen
Sehen Sie, wie man zählt, auf wie viele Arten Dominosteine ein Schachbrett füllen, ohne eine einzige Pflasterung zu suchen: Eine Determinante, die nur für planare Graphen stimmt, liefert für ein Schachbrett mit acht mal acht Feldern die Zahl 12 988 816. Der Haken: Die Profil-Programmierung ist bei schmalen Gittern schneller, und am K3,3 sieht man, warum nicht planare Graphen scheitern.
Demo starten →Fast planare Netze
Verfolgen Sie, wie ein fast planares Netz planarisiert wird: ein planares Gerüst bilden, jede übrige Kante über den kürzesten Dualweg einsetzen, jede Kreuzung zum Hilfsknoten machen. Auf Karten mit 100 Standorten braucht das ab 5 Zusatzkanten etwa halb so viele Kreuzungen wie gerade Strecken. Der Haken: Die Reihenfolge des Greedy entscheidet; bei 5 Zusatzkanten entfernt er zufällig 31 Kanten, kürzeste zuerst nur 5.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle neun Stücke, entlang der Frage, was man über das Netz wissen will: ob es sich ohne Kreuzung zeichnen lässt, wie viele Farben, wie man es teilt, wie man es zeichnet, wie groß der kleinste Schnitt ist, wie man eine große unabhängige Menge findet, wie viele Paarungen es gibt oder wie viele Kreuzungen ein fast planares Netz braucht.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Antworten gelten für die erzeugten Karten, Gitter und den Toronto-Auszug der Demos, nicht für jedes Netz. Ein Zeichenverfahren, das immer lesbar und immer kreuzungsfrei ist, gibt es nicht (Stück 4), und die Kreuzungen der Planarisierung sind eine Obergrenze der Kreuzungszahl, kein Optimum (Stück 9).
Weitere Linien in diesem Bereich
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
Spannbäume
Wie verbindet man alle Standorte mit möglichst wenig Leitung? Elf Stücke vom billigsten Baum über Richtung, Kapazität und Zwischenknoten bis zum Zufallsbaum.
Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Matching-Algorithmen
Wer wird womit gepaart? 13 Verfahren von der billigsten Kante zuerst bis zum Nierentausch unter medizinischen Zwängen, jedes mit seiner gemessenen Grenze.
Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Ordnung und Abhängigkeit
Ist ein Plan einhaltbar? Neun Stücke über Kreise, kritische Pfade, Ketten und Reihenfolgen: was Abhängigkeiten zwischen Aufgaben bedeuten und wo die Rechnung teuer wird.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.