Síkbarajzolhatóság tesztelése

A gráfelméletben a síkbarajzolhatósági tesztelés problémája, egy algoritmikus probléma, annak tesztelésére, hogy egy adott gráf síkbarajzolható gráf-e (vagyis hogy rajzolható-e síkban úgy, hogy az élei metszenék egymást). Ez a számítástudományban egy jól körüljárt probléma, újszerű adatszerkezeteket használva gyors algoritmusok léteznek erre a problémára:.A legtöbb ilyen módszer O(n) idő alatt alkalmazható n csúcsú gráf esetén és időben aszimptotikus, lineáris. A síkbarajzolhatóság-tesztelési algoritmus kimenetének két értéke lehet, egy síkba ágyazott gráf, vagyis síkgráf, és, ha nem síkba rajzolható, akkor például egy Kuratowski részgráf.

Síkba rajzolhatósági kritériumok

A síkbarajzolhatósági tesztelési algoritmusok jellemzően kihasználják azokat a tételeket a gráfelméletben, amelyek a síkbeli gráfok halmazát a gráfrajzoktól függetlenül jellemzik. Ezek pedig a:

• Kuratowski-tétel, miszerint egy véges gráf akkor és csak akkor rajzolható síkba, ha nem tartalmaz olyan részgráfot, amely topologikusan izomorf K₅-tel (az ötcsúcsú teljes gráffal) vagy K_3,3-mal (az ún. három ház–három kút gráffal.
• Wagner-tétel, miszerint egy síkgráf akkor és csak akkor síkba rajzolható, ha sem a K₅, sem a K_3,3 nem minora.
• A Fraysseix–Rosenstiehl síkbarajzolhatósági kritérium, amely jellemzi a síkgráfot az élek bal és jobb oldali rendezése alapján, a mélységi keresési fában(depth-first search tree).

A Fraysseix–Rosenstiehl síkbarajzolhatósági kritérium közvetlenül felhasználható a síkbarajzolhatóság tesztelésére szolgáló algoritmusok részeként, míg a Kuratowski és a Wagner tétele közvetett módon alkalmazható: ha egy algoritmus egy adott gráfon belül megtalálja a K ₅ vagy K _3,3 másolatát, akkor egy adott gráfon belül biztos lehet abban, hogy a bemeneti gráf nem síkgráf,ezt adja vissza további számolások nélkül.

Más síkbarajzolhatósági kritériumok, amelyek matematikailag jellemzőek, de a síkba rajzolhatósági tesztelési algoritmusok szempontjából kevésbé fontosak:

• A Whitney síkbarajzolhatósági kritérium, miszerint egy gráf sík, akkor és csak akkor, ha a grafikus matroidja szintén grafikus.
• A Mac Lane síkbarajzolhatósági kritérium a véges síkbeli gráfokat a körterei alapján jellemzi.
• A Schnyder-tétel, amely a síkgráfokat egy társított, parciális rendezés dimenziója alapján jellemzi, és
• Colin de Verdière síkbarajzolhatósági Colin de Verdière-gráfinvariáns kritériuma a spektrális gráfelmélet alapján dolgozik.

Algoritmusok

További útvonalak

A Hopcroft és Tarjan klasszikus útvonal-összeadási módszere volt az első, amely 1974-ben közzétett egy lineáris idejű, síkbarajzolhatósági tesztelési algoritmust. A Hopcroft és Tarjan algoritmusa megtalálható a Library of Efficient Data types and Algorithms könyvben, Mehlhorn, Mutzel és Näher szerzőktől. 2012-ben Taylor kibővítette ezt az algoritmust, hogy előállítsa a ciklikus élrendezés minden permutációját a kétszeresen összefüggő komponensek síkbeli beágyazásához.

A csúcshozzáadás módszere

A csúcshozzáadási módszerek úgy működnek, hogy bemutatják az adott gráf, indukált részgráfjának lehetséges beágyazódását ábrázoló adatszerkezetet, és a csúcsokat egyenként adják hozzá ehhez az adatszerkezethez. Ezek a módszerek egy nem hatékony O (n²) módszerrel kezdődtek, ezeket Lempel, Even és Cederbaum dolgozta ki 1967-ben. Ezt fejlesztették tovább Even és Tarjan, akik lineáris idejű megoldást találtak az s, t- számozására valamint Booth és Lueker, akik kidolgozták a PQ fa adatstruktúráját. Ezekkel a fejlesztésekkel az időtartam lineáris futású, és gyakorlatban túlszárnyalja a csúcs hozzáadási módszert. Ezt a módszert kiterjesztették arra is, hogy a síkba ágyazás (rajz) hatékonyan kiszámítható legyen egy síkgráfra. 1999-ben Shih és Hsu leegyszerűsítette ezeket a módszereket a PC-fa (a PQ-fa gyökérzet nélküli változata) és a csúcsok mélységi keresési fájának postorder-bejárásával.

Az élhozzáadás módszere

John Boyer és Wendy Myrvold 2004-ben kifejlesztett egy egyszerűsített O (n) algoritmust, amelyet eredetileg a PQ fa módszer ihletett, amely megszabadul a PQ fától és élek hozzáadását használja, ha lehetséges, a síkba ágyazás kiszámításához. Ellenkező esetben Kuratowski alcsoportot ( hogy nem K ₅ vagy K _3,3 ) néz. Ez az egyike a manapság legkorszerűbb két algoritmusnak (a másik a de Fraysseix, de Mendez és Rosenstiehl síkba rajzolhatósági tesztelési algoritmus ). Lásd még a a kísérleti összehasonlítást a Boyer és a Myrvold síkbarajzolhatósági-teszt előzetes verziójával. Ezenkívül a Boyer – Myrvold tesztet használják arra, hogy egy nem síkbeli bemeneti gráfból, több Kuratowski algráfot keressenek egy futási időben, a kimeneti méret függvényében. A síkbarajzolhatósági vizsgálat és a több Kuratowski algráf kinyerésének forráskódja nyilvánosan elérhető. Azt az algoritmust, amely megmutatja a Kuratowski-algráfot a csúcsok lineáris idejében, Williamson fejlesztette ki az 1980-as években.

Felépítési sorrend módszer

Ez egy másik módszer, ami a 3 összeköttetésű (triconnected) gráfok induktív konstrukcióját alkalmazza, a G minden 3 összeköttetésű összetevőjének, síkbeli beágyazásának fokozatos létrehozására (és ennélfogva a G síkba ágyazására). A felépítés K₄-gyel kezdődik, oly módon, hogy minden közbenső gráf, amely a teljes felépítés felé vezet, ismét 3 összeköttetésű legyen. Mivel az ilyen gráfoknak egyedi beágyazása van (a flippelésig és a külső oldal megválasztásáig), a következő nagyobb gráfnak, ha még mindig sík, a korábbi gráf finomításának kell lennie. Ez lehetővé teszi a síkbarajzolhatósági tesztet úgy, hogy minden egyes lépést teszteljen arra, hogy a következő hozzáadott élnek megvan-e mindkét vége, rendelkezik-e beágyazással. Noha ez fogalmi szempontból nagyon egyszerű (és lineáris futási időt ad), maga a módszer szenved a szerkesztési sorrend bonyolultságától.

Fordítás

Ez a szócikk részben vagy egészben a Planarity testing című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.