Planarer Graph

Ein planarer Graph lässt sich so darstellen, dass sich in 2 Dimensionen keine Kanten kreuzen.

Wenn man einen Graphen in planare Form bringen kann, dann sieht er etwas übersichtlicher aus. Außerdem ist dieses Prinzip wichtig in der Elektrik, da man Leitungen normalerweise nicht kreuzen kann.

Einen planaren Graphen kann man in einen dualen Graphen umwandeln.

$n-m+f=2$ Proof by induciton over the number of faces.

For simple planar graph with $n\ge 3$: $m\le 3n-6$