Planarność

Podstawowe zagadnienia

Najprościej mówiąc grafem planarnym jest graf, którego można narysować na płaszczyźnie, tak aby żadne dwie krawędzie nie przecinały się poza wierzchołkiem, z którym obie są incydentne. Każdy taki rysunek grafu planarnego nieposiadający przecięć nazywamy rysunkiem płaskim. Czasami rysunek płaski grafu planarnego będziemy nazywać grafem płaskim.

Ciekawym faktem jest to, iż rysunek płaski dowolnego grafu planarnego może zostać wykonany tak, by każda krawędź była odcinkiem linii prostej. Zostało to udowodnione niezależnie przez K. Wagnera i L. Fary'ego.

Nie wszystkie grafy są planarne. Przykładem mogą być $K_5$ albo $K_{3,3}$. Grafem planarnym nie jest również graf, którego podgraf jest nieplanarny. W takich grafach liczbą przecięć grafu nazywamy minimalną liczbę przecięć krawędzi, które muszą wystąpić, podczas rysowania grafu. Na przykład grafy $K_5$ i $K_{3,3}$ mają liczbę przecięć równą $1$. Liczbę przecięć grafu $G$ oznaczamy symbolem $\mathrm{cr}(G)$.

Zanim przejdziemy do własności grafów planarnych, poinniśmy poznać nowe definicje, których poznanie znacznie ułatwi zrozumienie niektórych twierdzeń. Grafy $H$ i $H'$ nazywamy homeomorficznymi, jeśli można je otrzymać z pewnego grafu $G$, poprzez wykonanie skończonej liczby operacji dodania wierzchołków drugiego stopnia na krawędzi.

Graf $G$ nazwiemy ściągalnym do grafu $H$, jeśli można otrzymać $H$, ściągając odpowiednie krawędzie $G$. Na przykład graf Petrsena jest grafem ściągalnym do $K_5$.

Istnieje kilka warunków koniecznych do tego, aby dany graf był planarny. Słynne twierdzenie Kuratowskiego bierze pod uwagę pojęcie homeomorficzności grafów.

• Dany graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homemorficznego z grafem $K_5$ lub z grafem $K_{3,3}$ (Kuratowski, 1930).

Inne twierdzenie wykorzystuje definicję grafu ściągalnego:

• Dany graf jest planarny wytedy i tylko wtedy, gdy nie zawiera podgrafu ściągalnego do $K_5$ lub $K_{3,3}$.

Jak można zauważyć, każdy graf nieplanarny musi mieć coś wspólnego z grafami $K_5$ lub z $K_{3,3}$. Są to pewnego rodzaju atomy świata grafów nieplanarnych.

Twierdzenie Eulera

Jeśli graf $G$ jest grafem planarnym, to każdy rysunek płaski $G$ dzieli zbiór punktów płaszczyzny, nieleżących na $G$ na obszary które nazywamy ścianami. Dokładnie jeden z tych obszarów jest nazywany ścianą nieskończoną.

Ilość ścian w danym grafie planarnym jest niezależna od sposobu narysowania grafu na powierzchni i można ją obliczyć korzystając z twierdzenia Eulera:

• Niech $G$ będzie rysunkiem płaskim spójnego grafu planarnego i niech $G$ ma $n$ wierzchołków, $m$ krawędzi i $f$ ścian. Wtedy: $$n-m+f=2$$ (Euler, 1750).

Bardziej ogólna forma twierdzenia uwzględnia grafy niespójne:

• Niech $G$ będzie rysunkiem płaskim grafu planarnego i niech $G$ ma $n$ wierzchołków, $m$ krawędzi $f$ ścian i $k$ składowych. Wtedy: $$n-m+f=k+1.$$

Ponadto jeśli przyjmiemy, że $G$ jest spójnym, planarnym grafem prostym mającym $n$ wierzchołków (pod warunkiem, że $n \ge 3$) i $m$ krawędzi to prawdziwa jest nierówność: $$m \le 3n - 6.$$ Następnie, jeśli przyjmiemy, że $G$ nie zawiera trójkątów, to także: $$m \le 2n - 4.$$ Inna własność bezpośrednio wynikająca z Twierdzenia Eulera mówi o tym, że każdy planarny graf prosty zawiera wierzchołek stopnia co najwyżej $5$.

Grafy dualne

Graf dualny geometrycznie do grafu płaskiego $G$ to graf płaski $G^*$ skonstruowany według następujących kroków:

1. Węwnątrz każdej ściany $f$ grafu $G$ wybieramy punkt $v^*$ - punkty te będą wierzchołkami $G^*$,
2. Następnie dla każdej krawędzi $e$ grafu $G$ prowadzimy linię $e^*$, przecinającą tylko $e$ i łączącą wierzchołki ścian $f$ oddzielonych od siebie krawędzią $e$ - powstałe linie będą tworzyły zbiór krwędzi grafu $G^*$.

Niech $G$ będzie spójnym grafem płaskim, który posiada $n$ wierchołków, $m$ krawędzi i $f$ ścian, a niech $G^*$ będzie geometrycznie dualny do $G$ i ma $n^*$ wierzchołków, $m^*$ krawędzi i $f^*$ ścian, wtedy występują zależności: $$n^* = f \qquad m^* = m \qquad f^* = n.$$