Planarni grafovi

Planarni grafovi su oni grafovi koji se mogu nacrtati u ravni tako da im se grane ne seku. Preciznije, zahteva se da je graf mogućno predstaviti u ravni tako da zajednička tačka dve grane može biti samo čvor koji predstavlja zajedničku krajnju tačku tih grana. Ako je planaran graf predstavljen na opisan način u ravni, on deli ravan na više konačnih zatvorenih oblasti i jednu beskonačnu oblast.

Svaka konačna oblast se naziva okce ili ćelija. Ako je graf povezan i ne sadrži artikulacione čvorove, granična linija okca predstavlja konturu grafa. Ponekad se pod okcem podrazumeva, umesto oblasti, upravo ova granična kontura.

Ojlerova teorema o planarnim grafovima kaže da za svaki planaran graf važi n+f=m+2, gde je n broj čvorova, m broj grana, a f broj oblasti grafa. Ruski naučnici Kuratovski i Potrjagin kažu da je graf planaran ako ne sadrži kao potpodelu K_3,3 ili K₅.

Takođe, graf je planaran ako važi 3*|V| - |E| ≥ 6, gde je |V| broj čvorova, a |E| broj grana.