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[uredi | uredi izvor]
Testiranje 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[uredi | uredi izvor]
Metoda dodavanja puteva[uredi | uredi izvor]
Klasič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[uredi | uredi izvor]
Metode 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[uredi | uredi izvor]
2004. 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 | uredi izvor]
- ^ 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