Planaariverkko

Planaariverkko on graafi, joka voidaan piirtää tasolle siten, ettei reunat leikkaa toisiaan paitsi solmukohtauksissa. Graafi voi koostua useammasta erillisestä komponentista, eikä sen tarvitse olla yhtenäinen.

Piirto jakaa tason alueisiin, joita kutsutaan kasvoiksi. Yhdistetyn planar graafin Eulerin kaava on V − E + F = 2; jos grafi koostuu c komponentista, sama pätee muodossa V − E + F = c + 1.

Kuratowskin teoreeman mukaan graafi on planaari, jos ja vain jos sillä ei ole subgraafia, joka on homeomorfisesti sama kuin K5 tai K3,3. Faryn teoreeman mukaan jokainen planaari graafi voidaan piirtää suorareunaisena siten, että reunat eivät leikkaa toisiaan.

Maximaalinen planariverkko on planariverkko, johon ei voi lisätä mitään muuta reunaa ilman että planariteetti menetetään. Tällaisissa grafiikassa pätee esimerkiksi E = 3V − 6, kun V ≥ 3.

Sovellukset ja käyttöalueet: planaareja verkkoja käytetään runsaasti piirilevyjen suunnittelussa, sähkö- ja liikenneverkkojen kartoituksessa sekä karttojen ja paikkatiedon esittämisessä, joissa reunojen ja alueiden asettelu on olennaista. Planaarisuuden tunteminen auttaa sekä teorian että käytännön algoritmien kehitystä ja toteutusta.

---