Testování rovinnosti - Planarity testing

v teorie grafů, testování rovinnosti problém je algoritmické problém testování, zda je daný graf a rovinný graf (to znamená, zda lze kreslit v rovině bez průsečíků hran). Toto je dobře prostudovaný problém v počítačová věda pro které je mnoho praktických algoritmy se objevily, mnohé využívají výhod románu datové struktury. Většina z těchto metod funguje Ó (n) čas (lineární čas), kde n je počet hran (nebo vrcholů) v grafu, což je asymptoticky optimální. Spíše než být jedinou booleovskou hodnotou může být výstup algoritmu testování rovinnosti rovinný vkládání grafů, je-li graf rovinný nebo překážka rovinnosti, například a Kuratowského podgraf pokud tomu tak není.

Kritéria rovinnosti

Algoritmy pro testování rovinnosti obvykle využívají výhod teorémů v teorii grafů, které charakterizují množinu rovinných grafů z hlediska nezávislého na výkresech grafů.

Kritérium Fraysseix – Rosenstiehl pro rovinnost lze použít přímo jako součást algoritmů pro testování rovinnosti, zatímco Kuratowského a Wagnerovy věty mají nepřímé aplikace: pokud algoritmus dokáže najít kopii K.5 nebo K.3,3 v rámci daného grafu si můžete být jisti, že vstupní graf není rovinný a vrátí se bez dalšího výpočtu.

Další kritéria rovinnosti, která matematicky charakterizují planární grafy, ale jsou méně důležitá pro algoritmy testování rovinnosti, zahrnují:

Algoritmy

Metoda přidání cesty

Klasika přidání cesty metoda Hopcroft a Tarjan[1] byl první publikovaný algoritmus testování rovinnosti v lineárním čase v roce 1974. Implementace Hopcroft a Tarjan Algoritmus je uveden v Knihovna efektivních datových typů a algoritmů podle Mehlhorn, Mutzel a Näher [2][3].[4] V roce 2012 Taylor [5] rozšířil tento algoritmus o generování všech permutací cyklického uspořádání hran pro planární vložení biconnected komponent.

Metoda přidání vrcholu

Metody přidávání vrcholů fungují tak, že udržují datovou strukturu představující možné vložení indukovaný podgraf daného grafu a přidávání vrcholů jeden po druhém do této datové struktury. Tyto metody začaly neúčinným O (n2) metoda koncipovaná Lempel, Dokonce a Cederbaum v roce 1967.[6] Vylepšili to Even a Tarjan, kteří našli řešení lineárního času pro s,t- krok číslování,[7] a tím Booth a Lueker, který vyvinul PQ strom datová struktura. S těmito vylepšeními je to lineární čas a v praxi překonává metodu přidání cesty.[8] Tato metoda byla také rozšířena, aby bylo možné efektivně vypočítat planární vkládání (kreslení) pro rovinný graf.[9] V roce 1999 Shih a Hsu zjednodušili tyto metody pomocí stromu PC (nezakořeněná varianta stromu PQ) a postorder traversal z hloubkové vyhledávání strom vrcholů.[10]

Metoda přidání hrany

V roce 2004 John Boyer a Wendy Myrvoldová [11] vyvinuli zjednodušený O (n) algoritmus, původně inspirovaný metodou stromu PQ, která se zbavuje stromu PQ a pokud je to možné, používá k výpočtu planárního vkládání okrajové doplňky. Jinak Kuratowského dělení (buď K.5 nebo K.3,3) je vypočítán. Jedná se o jeden ze dvou současných nejmodernějších algoritmů současnosti (druhý je algoritmus testování rovinnosti de Fraysseixe, de Mendeze a Rosenstiehla[12][13]). Vidět [14] pro experimentální srovnání s předběžnou verzí Boyerova a Myrvoldova testu rovinnosti. Kromě toho byl rozšířen Boyerův-Myrvoldův test, aby se extrahovalo několik Kuratowského dělení nerovinného vstupního grafu za běhu lineárně v závislosti na velikosti výstupu.[15] Zdrojový kód pro test rovinnosti[16][17] a extrakce několika dělení Kuratowski[16] je veřejně dostupný. Algoritmy, které lokalizují Kuratowského podgraf v lineárním čase ve vrcholech, vyvinul Williamson v 80. letech.[18]

Metoda konstrukční sekvence

Jiná metoda používá indukční konstrukci grafů se 3 spoji k postupnému vytváření rovinných vložení každé 3-spojené komponenty G (a tedy rovinné vložení G sám).[19] Stavba začíná K.4 a je definován takovým způsobem, že každý mezilehlý graf na cestě k úplné složce je opět spojen 3. Jelikož takové grafy mají jedinečné vložení (až překlopení a výběr vnější plochy), další větší graf, pokud je stále rovinný, musí být upřesněním původního grafu. To umožňuje snížit test rovinnosti pouze na testování pro každý krok, zda má další přidaná hrana oba konce na vnější ploše aktuálního vložení. I když je to koncepčně velmi jednoduché (a poskytuje lineární dobu chodu), samotná metoda trpí složitostí hledání konstrukční sekvence.

Reference

  1. ^ Hopcroft, Johne; Tarjan, Robert E. (1974), "Efektivní testování rovinnosti", Časopis Asociace pro výpočetní techniku, 21 (4): 549–568, doi:10.1145/321850.321852, hdl:1813/6011.
  2. ^ Mehlhorn, Kurt; Mutzel, Petra (1996), „O fázi vkládání algoritmu pro testování rovinnosti Hopcroft a Tarjan“, Algorithmica, 16 (2): 233–242, doi:10.1007 / bf01940648, hdl:11858 / 00-001M-0000-0014-B51D-B
  3. ^ Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), Implementace Hopcroftova a Tarjanova testu rovinnosti a vkládacího algoritmu
  4. ^ Mehlhorn, Kurt; Näher, Stefan (1995), „LEDA: Library of efficient data types and algorithms“, Komunikace ACM, 38 (1): 96–102, CiteSeerX  10.1.1.54.9556, doi:10.1145/204865.204889
  5. ^ Taylor, Martyn G. (2012). Testování rovinnosti podle přidání cesty (Ph.D.). University of Kent. Archivováno z původního dne 2016-03-05. Alternativní URL
  6. ^ Lempel, A .; Dokonce, S .; Cederbaum, I. (1967), „Algoritmus pro testování rovinnosti grafů“, Rosenstiehl, P. (ed.), Teorie grafů, New York: Gordon and Breach, s. 215–232.
  7. ^ Dokonce, Šimon; Tarjan, Robert E. (1976), „Computing an Svatý-číslování ", Teoretická informatika, 2 (3): 339–344, doi:10.1016/0304-3975(76)90086-4.
  8. ^ Boyer & Myrvold (2004), str. 243: „Jeho implementace v LEDA je pomalejší než implementace LEDA v mnoha jiných O (n) časové algoritmy. “
  9. ^ Chiba, N .; Nishizeki, T.; Abe, A .; Ozawa, T. (1985), „Lineární algoritmus pro vkládání rovinných grafů pomocí stromů PQ“, Journal of Computer and System Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2.
  10. ^ Shih, W. K .; Hsu, W. L. (1999), „Nový test rovinnosti“, Teoretická informatika, 223 (1–2): 179–191, doi:10.1016 / S0304-3975 (98) 00120-0.
  11. ^ Boyer, John M .; Myrvold, Wendy J. (2004), „Na špici: zjednodušený O (n) rovinnost podle přidání hrany “ (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273, doi:10,7155 / jgaa 00091.
  12. ^ de Fraysseix, H .; Ossona de Mendez, P.; Rosenstiehl, P. (2006), „Trémauxské stromy a rovinnost“, International Journal of Foundations of Computer Science, 17 (5): 1017–1030, arXiv:matematika / 0610935, doi:10.1142 / S0129054106004248.
  13. ^ Brandes, Ulrik (2009), Test rovinnosti zleva doprava (PDF).
  14. ^ Boyer, John M .; Cortese, P. F .; Patrignani, M .; Battista, G. D. (2003), „Přestaňte si všímat svých P a Q: implementace rychlého a jednoduchého algoritmu pro testování rovnosti a vkládání založeného na DFS“, Proc. 11. Int. Symp. Kreslení grafu (GD '03), Přednášky z informatiky, 2912, Springer-Verlag, s. 25–36
  15. ^ Chimani, M .; Mutzel, P.; Schmidt, J. M. (2008), „Efektivní extrakce několika dělení Kuratowski“, Proc. 15. Int. Symp. Kreslení grafu (GD'07), Přednášky v informatice, 4875, Sydney, Austrálie: Springer-Verlag, s. 159–170.
  16. ^ A b "OGDF - Open Graph Drawing Framework: Start".
  17. ^ „Boost Graph Library: Boyer-Myrvold Planarity Testing / Embedding - 1.40.0“.
  18. ^ Williamson, S. G. (1984), „Depth First Search and Kuratowski Subgraphs“, Deník ACM, 31 (4): 681–693, doi:10.1145/1634.322451
  19. ^ Schmidt, Jens M. (2014), Automaty, jazyky a programování, Přednášky v informatice, 8572, str. 967–978, doi:10.1007/978-3-662-43948-7_80, ISBN  978-3-662-43947-0