planaarisuustestejä

Planaarisuustestit ovat joukko menetelmiä, joita käytetään graafiteoriassa ja tietojenkäsittelytieteessä määrittämään, onko annettu graafi planetaarinen. Planetaarinen graafi on sellainen, joka voidaan piirtää tasoon ilman, että reunat leikkaavat toisiaan. Toisin sanoen, planetaarinen graafi voidaan esittää tasokuviona.

Yksi tunnetuimmista tuloksista planetaarisuustestauksessa on Kuratowski'n lause. Se toteaa, että graafi on planetaarinen jos ja vain jos se ei sisällä subgraafina K5:ttä (täydellinen graafi viidellä solmulla) tai K3,3:ta (täydellinen kaksijakoinen graafi, jossa molemmissa osajoukoissa on kolme solmua). Nämä kaksi graafia ovat pienimmät ei-planetaariset graafit.

Toinen tapa testata planetaarisuutta on käyttää algoritmia, joka yrittää rakentaa graafin tasoesitystä. Yksi tällainen algoritmi perustuu graafin jakamiseen pienempiin osiin ja näiden osien yhdistämiseen asteittain. Jos missään vaiheessa ei löydy tapaa yhdistää osia ilman leikkauksia, graafi ei ole planetaarinen. Boyer-Myrvaathin algoritmi on yksi tehokkaimmista planetaarisuustesteistä, ja sen aikakompleksisuus on lineaarinen, eli O(n), missä n on solmujen määrä.

Planetaarisuustestauksella on sovelluksia monilla aloilla, kuten piirilevyjen suunnittelussa, verkkoteoriassa ja tietokonegrafiikassa. Esimerkiksi, kun suunnitellaan sähköpiirejä, on usein tärkeää, että piirin kytkentäkaavio voidaan piirtää tasoon ilman johtojen risteämistä, mikä vastaa planetaarisen graafin käsitettä.