Тестирање планарности
У теорији графова, тестирање планарности је алгоритмички проблем испитивања да ли је дати граф планарни граф (то јест, да ли се може нацртати у равни без укрштања ивица). Ово је добро истражен проблем у информатици за који су се појавили многи практични Алгоритам, многи користећи нове структура података . Већина ових метода се извршава у О (n) времену (линеарно време), где је n број ивица (или чворова) на графику, који је асимптотски оптималан. Уместо да само буде једна тачно-нетачна вредност, излаз од алгоритма планарног тестирања може бити уградња планарног графа, уколико граф је планаран, или препрека планарности попут Куратовски подграфа ако није.
Критеријуми планарности
уредиТестирање планарности алгоритама обично користи теореме из теорије графова које карактеришу скуп планарних графова у смислу да су независни од цртежа графа.
Ово укључује
- Теорема Куратовског да је граф планаран ако и само ако не садржи подграф који је потподела од К 5 (комплетан граф од пет чворова) или К 3,3 (комплетан бипартитиван граф са шест чворова, од којих су три чвора повезана са друга три чвора).
- Теорема Вагнера да је граф планаран ако и само ако не садржи минор (подграф контракције) који је изоморфан са К 5 или К 3,3 .
- Фрајсикс-Росенстил критеријум планарности, карактерише планарне графове у смислу лево-десне оријентације чворова код претраге у дубину стабла.
Фрајсикс-Росенстил критеријум планарности се може директно користити као део алгоритама за тестирање планарности, док Куратовскијеве и Вагнерове теореме имају индиректне додатке: ако алгоритам може наћи примерак К 5 или К 3,3 у оквиру датог графа, може бити сигуран да улазни граф није планаран и вратити се без даљег рачунања.
Алгоритми
уредиМетода додавања путева
уредиКласична метода додавања путева Хопкрофта и Тарјана[1] је први објављени алгоритам за планарно тестирање који се извршавао за линеарно време 1974. године.
Метода додавања врха
уредиМетоде за додавање врха раде на принципу одржавања структуре података која представља могућа уграђивања у индуковани подграф датог графа и додавање чворова један по један на ове структуре података. Ове методе почињу са неефикасном О (n 2 ) методом коју је осмислио Лемпел, Евен и Цедербаум 1967. године.[2] Њу су побољшали Евен и Тарјан, који су пронашли линеарно временско решење за s,t- нумерисаних корака,[3] и Бут. И Луекер, који су развили структуру података-PQ стабло. Са овим побољшањима линеарно-временско је и превазилази методу додавања путева у пракси[4] Ова метода је такође проширена да би омогућила да се планарно уграћивање(цртање) ефикасно извршава за планарни граф[5] 1999. Схих и Хсу су поједноставили ове методе помоћу PC стабла (бескоренске варијанте PQ стабла).[6]
Метода додавања ивице
уреди2004. године, Бојер и Мирволд[7] су развили поједностављени О(n) алгоритам, првобитно инспирисан PQ методом стабла, који се ослобађа PQ стабла и користи додавање ивица за планарно уграђивање, ако је то могуће. У супротном, извршава се Куратовски потподела (или К 5 или К 3,3 ). Ово је дан-данас један од два најнапреднија алгоритма (други је алгоритам за планарно тестирање који је направио Fraysseix, de Mendez and Rosenstiehl[8][9]).. Видети[10] за експериментално поређење са прелиминарном верзијом Боиер и Мирволдовог тестирања планарности. Осим тога, Бојер-Мирволд тест је побољшан да може да издвоји више Куратовски подграфова из непланарног улазног графа у времену које је линеарно зависно од излазног формата.[11] Изворни код за тест планарности[12][13] и проналажење више Куратовски подгрупа је доступан јавности. Алгоритме који проналазе Куратовски подграф у линеарном времену од темена је изумео Williamson 1980.[14]
Референце
уреди- ^ 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”, Ур.: Rosenstiehl, P., Theory of Graphs, New York: Gordon and Breach, стр. 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. стр. 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, стр. 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, стр. 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