Planeaarisuutta

Planeaarisuus on käsite, jota käytetään erityisesti grafiteoriassa ja geometriassa. Se kuvaa kykyä esittää objekti tai rakenne tasolla siten, ettei viivoja tai kaaria tarvitse leikata toisiaan. Grafiikassa planeaarisuus tarkoittaa, että graafi voidaan piirtää tasolle siten, ettei reunat leikkaa toisiaan.

Graafien planeaarisuus ja tärkeät tulokset. Yhdistetyn graafin planeaarisuus korreloi Eulerin kaavan kanssa: v − e + f = 2, missä v on solmujen määrä, e reunojen määrä ja f kasvot (tasossa ulkonevat alueet). Tämä johtaa yleiseen rajaan e ≤ 3v − 6 silloin, kun v ≥ 3. Mikäli grafissa ei ole kolmiulotteisia kasveja (girthe, lyhyin kierto on vähintään 4), voidaan raja vielä tiivistää e ≤ 2v − 4. Tärkeä karakteristinen ominaisuus on Kuratowskin lause, jonka mukaan finiittinen graafi on planaarinen, jos ja vain jos siinä ei esiinny K5:n tai K3,3:n muunnostettua (jaksoitunutta) alijoukkoa.

Kuratowskin lausahdus ja Fary’n teoreema. Kuratowskin lauseellinen muoto antaa käytännön keinoja epäplanaarisuuden todentamiseen. Fary’n teoreema väittää, että jokainen planaarinen graafi voidaan piirtää suoraviivaisilla reunalla ilman kaarien risteämiä, mikä takaisee, että planaariset grafit ovat piirrettävissä standardin piirustusmetodin avulla.

Sovellukset ja menetelmät. Planeaarisuutta tutkitaan sekä teoreettisesti että algoritmisesti. On olemassa lineaariaikaisia algoritmeja planaarisuuden testaamiseen (esim. Hopcroft–Tarjanin ja siihen liittyvät menetelmät). Käytännön sovelluksia ovat karttojen ja piirustusten optimointi, piirilevyjen suunnittelu sekä monien verkko- ja tietokoneohjelmistojen visuaalinen esittäminen.