planarisuuden
Planaarisuus tarkoittaa sitä, että graafi voidaan piirtää tasolle siten, ettei sen reunat leikkaa toisiaan, ellei niillä ole yhteisiä päätepisteitä. Tällainen piirtäminen tunnetaan planaarisena sijoituksena, ja graafi, joka täyttää tämän ehdon, on planaarinen. Planaarisuus voidaan tulkita myös siten, että graafi voidaan sijoittaa pallon pinnalle reunojen leikkaantumatta.
Käytännön ja teoreettisenanalyysin kannalta keskeisiä tuloksia ovat Kuratowskin teoreema ja Wagnerin teoreema: Kuratowskin teoreeman mukaan graafi
Planaarisuuden testaamiseen on kehitetty tehokkaita algoritmeja, kuten Hopcroft–Tarjanin lineaarin aikainen menetelmä. Whitney’n teoreeman mukaan kolmiokytkentäisen planarisen
Sovellukset: planarisuus on keskeinen karttojen maalaus- ja piirilevy-ongelmissa sekä graafien visuaalisessa esittämisessä verkostoissa. Kaikki planar graafit