dualer Graph

Ein Planarer Graph teilt die 2D-Ebene in mehrere Flächen. Im dualen Graphen stellt jede dieser Flächen ein Knoten dar. Immer wenn sich zwei Flächen berühren, muss an dieser Stelle eine neue Kanten im dualen Graphen sein.

Wenn der Graph zusammenhängend ist, dann ist der duale Graph vom dualen Graph wieder der ursprüngliche Graph.

Das Prinzip der Dualität spielt eine wichtige Rolle in der Optimierung um untere Schranken für Optimierungsprobleme zu finden.