Graf často kreslíme do roviny (na papír). Vrcholy kreslíme jako “puntíky” a hrany jako čáry, které je spojují. Obrázku říkáme nakreslení grafu do roviny. Graf je rovinný, pokud lze nakreslit na papír bez křížení hran. Nakreslení do roviny bez křížení hran se říká rovinné nakreslední grafu. Jako příklad rovinných grafů uveďme graf sousedících států Jižní Ameriky, graf silniční sítě bez mostů a tunelů.

Pokud dostaneme nakreslení grafu, které není rovinné, tak to ještě neznamená, že graf není rovinný. Každý graf má řadu špatných nakreslení. Pro rovinnost stačí, aby existovalo jedno nakreslení bez křížení hran. Někdy můžeme křížící se hranu překreslit jako na následujícím obrázku.

Teď vezme do ruky nůžky a papír, na kterém je nakreslen graf, rozstříháme obrázek podél nakreslených hran. Stěny rovinného grafu jsou souvislé kusy roviny, na které se rovina rozpadne. Například graf na předchozím obrázku vpravo má $4$ stěny ($3$ vnitřní a $1$ vnější). Pozor, stěna je definována pouze pro rovinné nakreslení.

Věta (Eulerova formule): V rovinném grafu $G=(V,E)$ platí

  1. $|V|+|S|= |E|+2$.
  2. $|E| \leq 3|V|-6$.

Stejná formule platí o pro konvexní mnohostěny (krychle, osmistěn, \dots). Není divu, vždyť moucha sedící na stěně skleněného mnohostěnu vidí vrcholy a hrany jako rovinný graf (rozmyslete si, proč je graf rovinný).

Druhé tvrzení věty je důsledkem prvního. Má velký význam pro odhad časové složitosti algoritmů pracujích na rovinných grafech. Ukazuje totiž, že rovinný graf nemůže mít příliš mnoho hran. Počet hran je $m \leq 3n-6
= \OO(n)$.

Řada problémů se dá v rovinných grafech řešit rychleji nebo jednodušeji než v obecných grafech. Příkladem je barvení vrcholů grafu co nejmenším počtem barev tak, aby každé dva vrcholy spojené hranou měli různou barvu. V obecných grafech je to velmi těžké.1

Věta (o $4$ barvách): Vrcholy rovinného grafu lze obarvit $4$ barvami tak, aby žádná hrana nespojovala dva vrcholy stejné barvy.

Věta o $4$ barvách je jednou z prvních vět, která byla dokázána s pomocí počítače.2 Zkuste najít příklad rovinného grafu, jehož obarvení potřebuje alespoň $4$ barvy.

O rovinném nakreslení grafu. Podívejte se na graf na obrázku. Je to rovinný graf?

Jak poznat, jestli je graf rovinný? Rovinné grafy jsou poměrně krásně charakterizovány následující větou.

Věta (Kuratowski): Graf $G$ je rovinný právě tehdy když neobsahuje dělení $K_5$ nebo dělení $K_{3,3}$ jako podgraf.

Dělení $K_5$ je graf, který vznikne z $K_5$ tak, že některé jeho hrany podrozdělíme. Podrozdělení hrany $uv\in E$ je nahrazení hrany $uv$ cestou $uPv$, kde cesta $P$ obsahuje samé nově přidané vrcholy (kromě $u$ a $v$).

Kuratowského věta se dá použít v teoretických důkazech nebo pro nalezení “certifikátu” nerovinnosti grafu (když se někdo zeptá, proč graf není rovinný, tak mu ukážete dělení $K_5$ nebo $K_{3,3}$, které je podgrafem). Algoritmicky je věta téměř nepoužitelná.

Jak najít rovinné nakreslení grafu? Existuje několik algoritmů, které nám naleznou rovinné nakreslení grafu a nebo odpoví, že graf není rovinný. Ačkoliv je jejich časová složitost jen $\OO(n)$, jsou poměrně komplikované (jejich docela dobrý přehled naleznete v anglické Wikipedii pod heslem “planarity testing”). Pokud nevyžadujeme dobrou časovou složitost, tak nám poměrně dobře poslouží následující heuristika.

Pružinková heuristika: Heuristika využívá fyzikálních zákonů. Model, který si vytvoříme, odsimulujeme na počítači. Po určitém množtví kroků (iterací) dostaneme řešení, které sice není přesné, ale je mu velmi blízko.

Začneme s libovolným nakreslením grafu. Hrany grafu nahradíme pružinkami a do vrcholů umístíme náboje, které se vzájemně odpuzují. Potom necháme síly působit (odpudivé síly mezi vrcholy proti přitažlivým sílám pružinek). Působení sil realizujeme tak, že v několika iteracích pro každý vrchol spočítáme, kam se pohne. Skončíme, až nalezneme “téměř” rovnovážný stav.3 Odpudivé síly rozprostřou graf do co největší plochy, ale pružiny drží vrcholy spojené hranou blízko u sebe. Díky tomu dostaneme rovinné nakreslení (pokud je graf rovinný).

Věta (Fáry): Každý rovinný graf $G$ se dá nakreslit do roviny tak, aby vrcholy odpovídaly bodům a hrany odpovídaly rovným úsečkám.

Rovinné nakreslení grafu má řadu aplikací. Například při návrhu jednovstvých tištěných spojů, anglicky VLSI designs.