A síksági probléma annak ellenőrzésére szolgáló algoritmikus probléma, hogy egy adott gráf sík -e (vagyis megrajzolható-e egy síkon élek keresztezése nélkül). A problémát jól tanulmányozták a számítástechnikában , és sok gyakorlati algoritmust találtak ki rá , amelyek közül sok modern adatstruktúrát használ . A legtöbb ilyen metódus O( n ) időben fut (lineáris idő), ahol n a gráf éleinek (vagy csúcsainak) száma, ami egy aszimptotikusan optimális algoritmus . Egy egyszerű logikai érték helyett a planaritás-ellenőrző algoritmusok kimenete egy gráfbeágyazást eredményezhet, ha a gráf sík, vagy egy síksági fedezetet, például egy Kuratowski-részgráfot , ha a gráf nem sík.
A síkosságvizsgáló algoritmusok általában gráfelméleti tételeket használnak, amelyek a síkgráfok halmazát a gráfrajzolástól független kifejezésekkel írják le. Ebbe beletartozik
A De Fraisex-Rosenstil síksági kritérium közvetlenül használható a síksági vizsgálati algoritmus részeként, míg a Kuratowski- és Wagner-tétel közvetetten alkalmazható - ha az algoritmus egy adott gráfban megtalálja K 5 vagy K 3,3 másolatát, egy biztos lehet benne, hogy a bemeneti gráf nem síkbeli
A síkgráfokat matematikailag leíró, de síkosság-tesztelési algoritmusokhoz kevésbé alkalmas síkbeliségi kritériumok közé tartozik a Whitney-féle síksági kritérium , amely szerint a gráf akkor és csak akkor sík, ha a gráfmatroidja egyben kográf is, a McLane-féle síksági kritérium , amely a sík gráfokat bázisok szerint írja le. ciklikus tereik közül a Schneider-tétel , amely a kapcsolódó részlegesen rendezett halmazok sorrendi dimenziójával ír le síkgráfokat , és Colin de Verdière síksági kritériuma spektrális gráfelmélet segítségével .
Az első publikált (1974-ben) síkosság-ellenőrző algoritmus Hopcroft és Tarjan klasszikus útösszeadási módszere [1] volt, amely lineáris időben futott. A Hopcroft és Tarjan -féle algoritmus megvalósítását a hatékony adattípusok és algoritmusok Mehlhorn , Muzel és Neher [2] [3] [4] könyvtára tartalmazza . 2012-ben Taylor [5] kiterjesztette ezt az algoritmust, hogy létrehozza a ciklikus élsorrendek összes permutációját a kétszeresen összekapcsolt komponensek beágyazásához.
Csúcsok hozzáadásának módszere egy olyan adatstruktúra létrehozásával, amely egy adott gráf generált részgráfjának lehetséges egymásba ágyazását reprezentálja , és egyenként hozzáadja a csúcsokat ehhez az adatstruktúrához. Ezek a módszerek a Lempel , Ewen és Zederbaum által 1967-ben javasolt nem hatékony O( n 2 ) módszerrel kezdődtek [6] . A módszert Ewen és Tarjan fejlesztette tovább, akik lineáris időmegoldást találtak az s lépésekre , t -számozásra [7] , majd Booth és Luker továbbfejlesztette, akik kidolgozták a PQ-fa adatstruktúrát . Ezekkel a fejlesztésekkel a módszer idővel lineárissá vált, és a gyakorlatban gyorsabban kezdett működni, mint az útvonal-összeadás módszere [8] . Ezt a módszert kiterjesztették a sík gráfok síkbeli beágyazásának (rajzának) hatékony kiszámítására is [9] . 1999-ben Shi és Xu leegyszerűsítette ezeket a módszereket PC-fa (a PQ-fa nem gyökerező változata) és késleltetett csúcsfa bejárás segítségével mélység-első kereséssel [10] .
2004-ben Boyer és Myhrvold [11] kifejlesztett egy egyszerűsített algoritmust O( n ) futási idővel , amelyet a PQ fa módszer ihletett, de amelyben a PQ fát elvetették, és az algoritmus élösszeadást használ a síkbeli beágyazás kiszámításához, ha lehetséges. Ellenkező esetben a Kuratowski-felosztás kerül kiszámításra (vagy a K 5 gráf, vagy a K 3,3 gráf ). A módszer a két jelenleg létező algoritmus egyike (a másik a de Freisex, de Mendes és Rosenstiel [12] [13] planaritás-ellenőrző algoritmus ). Lásd Boyer, Cortese, Patrignami és Battista [14] a kísérleti összehasonlításhoz Boyer és Myhrvold síkosság-ellenőrző algoritmusának előzetes változatával. Ezzel egyidejűleg a Boyer és Myhrvold ellenőrző algoritmust kibővítették a Kuratov nem síkbeli bemeneti gráf több felosztására, amelyek futási ideje lineárisan függ a kimeneti mérettől [15] . A síkosság-ellenőrzés [16] [17] és számos Kuratovsky-alosztály kiválasztása [16] forráskódjai nyilvánosak (C++ nyelven). Williamson az 1980-as években kifejlesztett egy algoritmust, amely a Kuratowski részgráfot időlineárisan határozza meg a csúcsok számában [18] .
Egy másik módszer 3 összekapcsolt gráfok indukciós felépítését használja a G gráf tetszőleges 3 összekapcsolt komponensének szekvenciális síkbeli beágyazásának megalkotására (és ezért magának a G gráfnak síkbeli beágyazását ) [19] . A konstrukció K 4 -ből indul, és úgy van definiálva, hogy a teljes komponens felé vezető úton bármely köztes gráf ismét 3-as összeköttetésű legyen. Mivel az ilyen gráfok egyetlen beágyazásúak (a külső felület kiválasztásáig), a következő nagyobb gráfnak, ha sík marad, az előző gráf finomítása kell legyen. Ez lecsökkenti a síksági tesztet arra, hogy egyszerűen ellenőrizze, hogy a következő hozzáadott él mindkét vége az aktuális egymásba ágyazás külső oldalán lesz-e. Mivel fogalmilag nagyon egyszerű (és lineáris futási időt ad), a módszer nagyon bonyolult a felépítési sorrend megtalálásában.