Rovinný graf

Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží.

Rovinné nakreslení

Oblouk je podmnožina roviny tvaru $\sigma (\langle 0,1\rangle )$ , kde $\sigma :[0,1]\rightarrow \mathbb {R} ^{2}$ je nějaké spojité a prosté (až na koncové body) zobrazení intervalu $\langle 0,1\rangle$ do roviny. Body $\sigma (0)$ a $\sigma (1)$ se nazývají koncové body oblouku.

Rovinné nakreslení je pak zobrazení $b$ , které každému vrcholu $v$ přiřazuje bod roviny $b(v)$ a hraně ${i,j}$ přiřadí oblouk s koncovými body $\sigma (0)=b(i)$ a $\sigma (1)=b(j)$ . Zobrazení je prosté (různým vrcholům odpovídají různé body roviny) a žádný bod $b(v)$ není nekoncovým bodem žádného oblouku. Graf spolu s takovýmto zobrazením nazveme topologický graf.

Topologický graf je rovinný, pokud libovolné dva oblouky odpovídající hranám $e$ a $f$ ( $e\neq f$ ) mají společné nejvýše koncové body.

Stěna grafu

Nechť $A\subseteq \mathbb {R} ^{2}\setminus X$ (kde $X$ je množina všech bodů a všech oblouků nakreslení grafu). Nazveme ji souvislou, pokud pro $\forall x,y\in A$ platí, že existuje oblouk $o$ s koncovými body $x$ a $y$ takový, že $o\subseteq A$ . Oblouky příslušné hranám nějakého topologického grafu pak podle této relace souvislosti rozdělují rovinu na třídy ekvivalence, které se nazývají stěny grafu.

Charakterizace rovinných grafů

Kuratowského věta

Graf G je rovinný právě tehdy, není-li žádný jeho podgraf izomorfní s nějakým dělením grafu $K_{5}$ nebo $K_{3,3}$ . ( $K_{5}$ označuje úplný graf na pěti vrcholech, $K_{3,3}$ pak úplný bipartitní graf.)

Eulerův vzorec

Pro rovinné grafy také platí následující vzorec, je to ovšem pouze implikace: Je-li $G=(V,E)$ souvislý rovinný graf, pak $|V|-|E|+s=2$ , kde $s$ je počet stěn nějakého rovinného nakreslení tohoto grafu.

Maximální počet hran

Je-li $G=(V,E)$ rovinný graf, pak platí, že $|E|\leq 3|V|-6$ . Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. $K_{3}$ , úplný graf na 3 vrcholech), pak $|E|\leq 2|V|-4$ .