Тестирање планарности
У теорији графова, тестирање планарности је алгоритмички проблем испитивања да ли је дати граф планарни граф (то јест, да ли се може нацртати у равни без укрштања ивица). Ово је добро истражен проблем у информатици за који су се појавили многи практични Алгоритам, многи користећи нове структура података . Већина ових метода се извршава у О (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, Архивирано из оригинала (PDF) 15. 07. 2006. г., Приступљено 29. 05. 2013
- ^ 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