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
upraviť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
upraviť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
upraviťHrúbka grafu G je minimálny počet jeho planárnych podgrafov zjednotením ktorých dostávame graf G.
Jemnosť grafu
upraviť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
upraviť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”).