Testiranje planarnosti
U teoriji grafova, testiranje planarnosti je algoritmički problem ispitivanja da li je dati graf planarni graf (to jest, da li se može nacrtati u ravni bez ukrštanja ivica). Ovo je dobro istražen problem u informatici za koji su se pojavili mnogi praktični Algoritam, mnogi koristeći nove struktura podataka . Većina ovih metoda se izvršava u O (n) vremenu (linearno vreme), gde je n broj ivica (ili čvorova) na grafiku, koji je asimptotski optimalan. Umesto da samo bude jedna tačno-netačna vrednost, izlaz od algoritma planarnog testiranja može biti ugradnja planarnog grafa, ukoliko graf je planaran, ili prepreka planarnosti poput Kuratovski podgrafa ako nije.
Kriterijumi planarnosti
urediTestiranje planarnosti algoritama obično koristi teoreme iz teorije grafova koje karakterišu skup planarnih grafova u smislu da su nezavisni od crteža grafa.
Ovo uključuje
- Teorema Kuratovskog da je graf planaran ako i samo ako ne sadrži podgraf koji je potpodela od K 5 (kompletan graf od pet čvorova) ili K 3,3 (kompletan bipartitivan graf sa šest čvorova, od kojih su tri čvora povezana sa druga tri čvora).
- Teorema Vagnera da je graf planaran ako i samo ako ne sadrži minor (podgraf kontrakcije) koji je izomorfan sa K 5 ili K 3,3 .
- Frajsiks-Rosenstil kriterijum planarnosti, karakteriše planarne grafove u smislu levo-desne orijentacije čvorova kod pretrage u dubinu stabla.
Frajsiks-Rosenstil kriterijum planarnosti se može direktno koristiti kao deo algoritama za testiranje planarnosti, dok Kuratovskijeve i Vagnerove teoreme imaju indirektne dodatke: ako algoritam može naći primerak K 5 ili K 3,3 u okviru datog grafa, može biti siguran da ulazni graf nije planaran i vratiti se bez daljeg računanja.
Algoritmi
urediMetoda dodavanja puteva
urediKlasična metoda dodavanja puteva Hopkrofta i Tarjana[1] je prvi objavljeni algoritam za planarno testiranje koji se izvršavao za linearno vreme 1974. godine.
Metoda dodavanja vrha
urediMetode za dodavanje vrha rade na principu održavanja strukture podataka koja predstavlja moguća ugrađivanja u indukovani podgraf datog grafa i dodavanje čvorova jedan po jedan na ove strukture podataka. Ove metode počinju sa neefikasnom O (n 2 ) metodom koju je osmislio Lempel, Even i Cederbaum 1967. godine.[2] Nju su poboljšali Even i Tarjan, koji su pronašli linearno vremensko rešenje za s,t- numerisanih koraka,[3] i But. I Lueker, koji su razvili strukturu podataka-PQ stablo. Sa ovim poboljšanjima linearno-vremensko je i prevazilazi metodu dodavanja puteva u praksi[4] Ova metoda je takođe proširena da bi omogućila da se planarno ugraćivanje(crtanje) efikasno izvršava za planarni graf[5] 1999. Shih i Hsu su pojednostavili ove metode pomoću PC stabla (beskorenske varijante PQ stabla).[6]
Metoda dodavanja ivice
uredi2004. godine, Bojer i Mirvold[7] su razvili pojednostavljeni O(n) algoritam, prvobitno inspirisan PQ metodom stabla, koji se oslobađa PQ stabla i koristi dodavanje ivica za planarno ugrađivanje, ako je to moguće. U suprotnom, izvršava se Kuratovski potpodela (ili K 5 ili K 3,3 ). Ovo je dan-danas jedan od dva najnaprednija algoritma (drugi je algoritam za planarno testiranje koji je napravio Fraysseix, de Mendez and Rosenstiehl[8][9]).. Videti[10] za eksperimentalno poređenje sa preliminarnom verzijom Boier i Mirvoldovog testiranja planarnosti. Osim toga, Bojer-Mirvold test je poboljšan da može da izdvoji više Kuratovski podgrafova iz neplanarnog ulaznog grafa u vremenu koje je linearno zavisno od izlaznog formata.[11] Izvorni kod za test planarnosti[12][13] i pronalaženje više Kuratovski podgrupa je dostupan javnosti. Algoritme koji pronalaze Kuratovski podgraf u linearnom vremenu od temena je izumeo Williamson 1980.[14]
Reference
uredi- ^ Hopcroft, John; Tarjan, Robert E. (1974), „Efficient planarity testing”, Journal of the Association for Computing Machinery, 21 (4): 549—568, doi:10.1145/321850.321852
- ^ Lempel, A.; Even, S.; Cederbaum, I. (1967), „An algorithm for planarity testing of graphs”, Ur.: Rosenstiehl, P., Theory of Graphs, New York: Gordon and Breach, str. 215—232
- ^ Even, Shimon; Tarjan, Robert E. (1976), „Computing an st-numbering”, Theoretical Computer Science, 2 (3): 339—344, doi:10.1016/0304-3975(76)90086-4
- ^ Boyer & Myrvold 2004. str. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.”
- ^ Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), „A linear algorithm for embedding planar graphs using PQ–trees”, Journal of Computer and Systems Sciences, 30 (1): 54—76, doi:10.1016/0022-0000(85)90004-2
- ^ Shih, W. K.; Hsu, W. L. (1999), „A new planarity test”, Theoretical Computer Science, 223 (1–2): 179—191, doi:10.1016/S0304-3975(98)00120-0
- ^ Boyer, John M.; Myrvold, Wendy J. (2004), „On the cutting edge: simplified O(n) planarity by edge addition” (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241—273
- ^ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), „Trémaux Trees and Planarity”, International Journal of Foundations of Computer Science, 17 (5): 1017—1030, doi:10.1142/S0129054106004248
- ^ Brandes, Ulrik (2009), The left-right planarity test (PDF)
- ^ Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), „Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm”, Proc. 11th Int. Symp. Graph Drawing (GD '03), Lecture Notes in Computer Science, 2912, Springer-Verlag, str. 25—36
- ^ Chimani, M.; Mutzel, P.; Schmidt, J. M. (2008), „Efficient extraction of multiple Kuratowski subdivisions”, Proc. 15th Int. Symp. Graph Drawing (GD'07), Lecture Notes in Computer Science, 4875, Sydney, Australia: Springer-Verlag, str. 159—170
- ^ OGDF - Open Graph Drawing Framework: start
- ^ Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0
- ^ Williamson, S. G. (1984), „Depth First Search and Kuratowski Subgraphs”, Journal Association of Computing Machinery, 31: 681—693, doi:10.1145/1634.322451