Tasomaisuusongelma on algoritminen ongelma , jolla tarkistetaan, onko tietty graafi tasomainen (eli voidaanko se piirtää tasolle ilman, että se risteää reunoja). Ongelma on hyvin tutkittu tietojenkäsittelytieteessä ja siihen on keksitty monia käytännön algoritmeja , joista monet käyttävät nykyaikaisia tietorakenteita . Useimmat näistä menetelmistä toimivat O( n ) ajassa (lineaarinen aika), jossa n on graafin reunojen (tai kärkien) lukumäärä, mikä on asymptoottisesti optimaalinen algoritmi . Yksinkertaisen Boolen arvon sijaan tasoisuudentarkistusalgoritmien tulos voi tuottaa graafin upotuksen , jos kaavio on tasomainen, tai tasomaisuussuojauksen, kuten Kuratowskin aligraafin , jos graafi ei ole tasomainen.
Tasoisuustestausalgoritmit käyttävät yleensä graafiteorian lauseita, jotka kuvaavat tasograafien joukkoa graafin piirtämisestä riippumattomilla termeillä. Tämä sisältää
De Fraisex-Rosenstilin tasoisuuskriteeriä voidaan käyttää suoraan osana tasomaisuustestausalgoritmia, kun taas Kuratowskin ja Wagnerin lauseita sovelletaan epäsuorasti - jos algoritmi löytää kopion K 5 :stä tai K 3,3 :sta annetusta graafista, yksi voi olla varma, että syötekaavio ei ole tasomainen
Muita tasomaisuuskriteerejä, jotka kuvaavat tasomaisia graafisia matemaattisesti, mutta jotka eivät sovellu tasomaisuuden testausalgoritmeihin, sisältävät Whitneyn tasomaisuuskriteerin , jonka mukaan graafi on tasomainen, jos ja vain jos sen graafin matroidi on myös cograph, McLanen tasomaisuuskriteeri , joka kuvaa tasomaiset graafit kantojen mukaan. niiden syklisistä avaruuksista , Schneiderin lause , joka kuvaa tasograafit, joiden järjestysmitta niihin liittyvien osittain järjestettyjen joukkojen , ja Colin de Verdièren tasoisuuden kriteeri , spektrigraafiteoriaa käyttäen .
Ensimmäinen julkaistu (vuonna 1974) tasomaisuuden tarkistusalgoritmi oli Hopcroftin ja Tarjanin klassinen polunlisäysmenetelmä [1] , joka juoksi lineaarisessa ajassa. Hopcroftin ja Tarjanin algoritmin toteutus sisältyy tehokkaiden tietotyyppien ja algoritmien kirjastoon Mehlhorn , Muzel ja Neher [2] [3] [4] . Vuonna 2012 Taylor [5] laajensi tätä algoritmia generoimaan kaikki syklisten reunajärjestyksen permutaatiot kahdesti kytkettyjen komponenttien upottamiseksi.
Menetelmä pisteiden lisäämiseksi luomalla tietorakenne, joka edustaa tietyn graafin generoidun aligraafin mahdollisia sisäkkäiskohtia, ja lisäämällä tähän tietorakenteeseen kärkipisteitä yksitellen. Nämä menetelmät alkoivat Lempelin , Ewen ja Zederbaumin vuonna 1967 [6] ehdottamasta tehottomasta O( n 2 ) -menetelmästä . Menetelmää paransivat Ewen ja Tarjan, jotka löysivät lineaarisen aikaratkaisun vaiheille s , t -numerointi [7] , ja sitten paransivat Booth ja Luker, jotka kehittivät PQ-puun tietorakenteen . Näiden parannusten myötä menetelmästä tuli ajan mittaan lineaarinen ja käytännössä se alkoi toimia nopeammin kuin polkujen lisäämismenetelmä [8] . Tätä menetelmää on myös laajennettu laskemaan tehokkaasti tasomaisen upotuksen (piirroksen) tasograafille [9] . Vuonna 1999 Shi ja Xu yksinkertaistivat näitä menetelmiä käyttämällä PC-puuta (PQ-puun ei-juurtunut versio) ja viivästettyä vertex -puun läpikulkua syvyys-ensimmäisellä haulla [10] .
Vuonna 2004 Boyer ja Myhrvold [11] kehittivät yksinkertaistetun algoritmin, jonka ajoaika oli O( n ), joka on saanut inspiraationsa PQ-puumenetelmästä, mutta jossa PQ-puu hylättiin ja algoritmi laskee tasomaisen upotuksen reunalisäyksen avulla. jos mahdollista. Muussa tapauksessa lasketaan Kuratowskin alajako (joko K 5 -kuvaaja tai K 3,3 -graafi ). Menetelmä on toinen kahdesta tällä hetkellä olemassa olevasta algoritmista (toinen on de Freisexin, de Mendesin ja Rosenstielin [12] [13] tasomaisuuden tarkistusalgoritmi ). Katso Boyer, Cortese, Patrignami ja Battista [14] kokeellisesta vertailusta Boyerin ja Myhrvoldin tasomaisuuden tarkistusalgoritmin alustavaan versioon. Samaan aikaan Boyerin ja Myhrvoldin varmennusalgoritmia laajennettiin poimimaan useita Kuratov-epätasoisen syöttögraafin alajakoja, joiden käyntiaika riippuu lineaarisesti ulostulon koosta [15] . Tasomaisuuden tarkistuksen [16] [17] ja useiden Kuratovsky-alaosastojen [16] valinnan lähdekoodit ovat julkisia (C++:ssa). Williamson kehitti 1980-luvulla algoritmin, joka määrittää Kuratowskin aligraafin aikalineaarisesti pisteiden lukumäärässä [18] .
Toinen menetelmä käyttää 3-liitettävien graafien rakentamista induktiolla rakentamaan peräkkäin graafin G minkä tahansa 3-liitetyn komponentin tasomainen upottaminen (ja siten itse graafin G tasomainen upottaminen ) [ 19] . Konstruktio alkaa K 4 :stä ja määritellään siten, että mikä tahansa väligraafi matkalla kokonaiseen komponenttiin on jälleen 3-kytketty. Koska tällaisissa kaavioissa on yksi upotus (ulkopinnan valintaan asti), seuraavan suuremman graafin, jos se pysyy tasomaisena, on oltava edellisen graafin jalostus. Tämä vähentää tasomaisuustestin yksinkertaisesti sen tarkistamiseen, onko seuraavalla lisätyllä reunalla molemmat päät nykyisen sisäkkäisyyden ulkopinnalla. Koska menetelmä on käsitteellisesti hyvin yksinkertainen (ja se antaa lineaarisen käyntiajan), menetelmällä on paljon monimutkaisuutta rakennussekvenssin löytämisessä.