Planárnost

Planárnost (planarity) v matematice popisuje vlastnost grafu, zda lze graf nakreslit na rovině tak, aby se hrany nekřížily kromě jejich koncových vrcholů. Takové zobrazení se nazývá planární kresba nebo embedování. Planárnost lze také chápat prostřednictvím zobrazení na povrchu koule; graf je planární, pokud má bezkřížové zobrazení na kouli, které odpovídá zobrazení na rovině po stereografickém promítnutí.

Pro jednoduché grafy (bez smyček a vícenásobných hran) platí Eulerova formule pro spojité grafy: v - e + f = 2, kde v je počet vrcholů, e počet hran a f počet tváří. Obecně pro graf se c komponentami platí v - e + f = c + 1. Z této rovnice vyplývají omezení, například e ≤ 3v - 6 pro v ≥ 3. Grafy dosahující rovnosti se nazývají maximálně planární a jsou triangulovatelné, přičemž každá tvář je trojúhelník.

Kuratowského věta říká, že finitení graf je planární právě tehdy, pokud neobsahuje podgraf, který je homeomorfně ekvivalentní k K5 nebo K3,3. Jinými slovy, absence těchto dvou speciálních subgrafů zaručuje planárnost; naopak jejich existence znamená neplanárnost. Fáryho teorém doplňuje, že každý jednoduchý planární graf lze nakreslit jen s přímými hranami.

Z praxe vyplývá existence lineárně časových algoritmů pro rozpoznání planárnosti; nejznámější jsou Hopcroftova a Tarjanova metoda a modernější Boyer–Myrvoldův algoritmus. Planárnost hraje klíčovou roli při návrhu sítí a obvodů, v geoinformatice, vizualizaci sítí a při generování plochých sítí v počítačové grafice.

Související pojmy: graf, embedding, Eulerova formule, triangulace, K5, K3,3, Fáryho teorém, plánární kresba.