Neplanárny graf

Neplanárny graf alebo nerovinný graf je graf, ktorý nie je rovinný graf.

Pre neplanárny graf možno nakresliť diagram grafu len tak, že niektoré hrany sa krížia v nekoncových bodoch.

Miery neplanárnosti grafu
Pre každý graf G možno určiť nesledujúce miery neplanárnosti grafu
priesečníkové číslo grafu 
hrúbku grafu 
jemnosť grafu 
rod grafu

Priesečníkové číslo grafu
Priesečníkové číslo grafu G je minimálny počet dvojíc hrán, ktoré sa krížia (pretínajú) pri ľubovoľnom nakreslení diagramu grafu G.

Hrúbka grafu
Hrúbka grafu G je minimálny počet jeho planárnych podgrafov zjednotením ktorých dostávame graf G.

Jemnosť grafu
Jemnosť grafu G je maximálny počet hranovo disjunktných neplanárnych podgrafov grafu G

Tieto miery sú kombinatorické miery neplanárnosti grafov. Existuje ešte jedna miera, ktorá má čisto geometrickú interpretáciu.

Rod grafu
Rod grafu je minimálny počet premostení, ktoré treba pridať ku guli, aby sa na jej povrchu dal nakresliť diagram príslušného grafu bez pretínania sa hrán. Planárne grafy majú rod 0, rod 1 majú grafy, ktorých diagramy môžeme nakresliť na anuloid (“pneumatiku”).

Kategória:Teória grafov