Planaarisuuden

Planaarisuus (planarity) on käsite graafiteoriassa, joka kuvaa, voiko graafi esittää tasolla siten, ettei sen kaaret leikkaa toisiaan. Tällainen piirros eli planar embedding mahdollistaa graafin esittämisen ilman risteäviä kaaria; graafia, joka täyttää tämän ehdon, sanotaan planariksi.

Kuratowskin teoreema sanoo, että graafi on planar, jos ja vain jos se ei sisällä kotiomorfista kopioa graafeista K5 tai K3,3. Wagnerin teoreema antaa vastaavan, mutta puhuen siitä, ettei graafilla ole K5- tai K3,3-minooria. Näiden teoreemien kiinteät ehdot ovat keskeisiä planarisuuden tunnistuksessa.

Eulerin kaava planeerille graafille, jossa V on solmujen määrä, E kaarien määrä ja F kasien määrä, on V − E + F = 2. Tämä johtaa johtopäätöksiin E ≤ 3V − 6 (V ≥ 3). Jos graafi ei sisällä kolmiopisteitä, E ≤ 2V − 4.

Esimerkkejä: Puut ovat planar; täydellinen graafi K4 on planar; K5 ja K3,3 eivät ole planar.

Sovellukset ja testaus: Planaarisuudella on keskeinen rooli graafien visualisoinnissa, piirisuunnittelussa ja verkkojen esittämisessä. Lineaariaikaisia planaarisuustestejä on kehitetty, esim. Hopcroft–Tarjanin ja Boyer–Myrvoldin menetelmät. Planaarisuus kuuluu myös minor-teorian keskeisiin ominaisuuksiin, mikä vaikuttaa muun muassa graafien ominaisuusarvioihin ja sovelluksiin.