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 on planarinen, jos ja vain jos se ei sisällä homeomorfisesti K5:n tai K3,3:n alikomponentteja. Wagnerin teoreema antaa vastaavan minori-kokonaisuuden: graafi on planarinen, jos siinä ei ole K5:n tai K3,3:n minoria. Eulerin kaavan mukaan yhdistetyn planarisen graafin tapauksessa V − E + F = 2, jossa V on solmujen määrä, E reunoja ja F kasvojen määrä. Tämän seurauksena E ≤ 3V − 6, kun V ≥ 3; lisäksi tiukemmat rajat pätevät, jos graafissa ei ole kolmiokolmia.

Planaarisuuden testaamiseen on kehitetty tehokkaita algoritmeja, kuten Hopcroft–Tarjanin lineaarin aikainen menetelmä. Whitney’n teoreeman mukaan kolmiokytkentäisen planarisen graafin planaarinen sijoitus on yksikertainen, kun otetaan huomioon automorfia.

Sovellukset: planarisuus on keskeinen karttojen maalaus- ja piirilevy-ongelmissa sekä graafien visuaalisessa esittämisessä verkostoissa. Kaikki planar graafit ovat 4-värisiä, mikä on neljän väriteoreeman seuraus.