{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:35Z","timestamp":1750219715836,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T00:00:00Z","timestamp":1697241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["RU-1903\/3-1"],"award-info":[{"award-number":["RU-1903\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>PQ-trees and PC-trees are data structures that represent sets of linear and circular orders, respectively, subject to constraints that specific subsets of elements have to be consecutive. While equivalent to each other, PC-trees are conceptually much simpler than PQ-trees; updating a PC-tree so that a set of elements becomes consecutive requires only a single operation, whereas PQ-trees use an update procedure that is described in terms of nine transformation templates that have to be recursively matched and applied.<\/jats:p>\n          <jats:p>\n            Despite these theoretical advantages, to date no practical PC-tree implementation is available. This might be due to the original description by Hsu and McConnell\u00a0[\n            <jats:xref ref-type=\"bibr\">14<\/jats:xref>\n            ] in some places only sketching the details of the implementation. In this paper, we describe two alternative implementations of PC-trees. For the first one, we follow the approach by Hsu and McConnell, filling in the necessary details and also proposing improvements on the original algorithm. For the second one, we use a different technique for efficiently representing the tree using a Union-Find data structure. In an extensive experimental evaluation we compare our implementations to a variety of other implementations of PQ-trees that are available on the web as part of academic and other software libraries. Our results show that both PC-tree implementations beat their closest fully correct competitor, the PQ-tree implementation from the OGDF library\u00a0[\n            <jats:xref ref-type=\"bibr\">6<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">15<\/jats:xref>\n            ], by a factor of 2 to 4, showing that PC-trees are not only conceptually simpler but also fast in practice. Moreover, we find the Union-Find-based implementation, while having a slightly worse asymptotic runtime, to be twice as fast as the one based on the description by Hsu and McConnell.\n          <\/jats:p>","DOI":"10.1145\/3611653","type":"journal-article","created":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T12:10:24Z","timestamp":1690805424000},"page":"1-24","source":"Crossref","is-referenced-by-count":1,"title":["Experimental Comparison of PC-Trees and PQ-Trees"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2754-1195","authenticated-orcid":false,"given":"Simon D.","family":"Fink","sequence":"first","affiliation":[{"name":"University of Passau, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5378-1694","authenticated-orcid":false,"given":"Matthias","family":"Pfretzschner","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3794-4406","authenticated-orcid":false,"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[{"name":"University of Passau, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,10,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.45.11.1607"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2738054"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24838-5_10"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.130"},{"key":"e_1_3_3_7_2","volume-title":"Handbook of Graph Drawing and Visualization","author":"Chimani Markus","year":"2014","unstructured":"Markus Chimani, Carsten Gutwenger, Michael J\u00fcnger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. 2014. The open graph drawing framework (OGDF). In Handbook of Graph Drawing and Visualization, R. Tamassia (Ed.). CRC Press, Chapter 17."},{"key":"e_1_3_3_8_2","volume-title":"Implementation of a Planarity Testing Method using PQ-Trees","author":"Cregten Alex William","year":"2017","unstructured":"Alex William Cregten and Hannes Kristj\u00e1n Hannesson. 2017. Implementation of a Planarity Testing Method using PQ-Trees. Technical Report. Reykjav\u00edk University. https:\/\/skemman.is\/bitstream\/1946\/29618\/1\/Planarity_testing_with_PQTrees.pdf"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00219-9_17"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-1-15"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.029"},{"key":"e_1_3_3_12_2","volume-title":"JGraphEd \u2013 A Java Graph Editor and Graph Drawing Framework","author":"Harris Jon","year":"2004","unstructured":"Jon Harris. 2004. JGraphEd \u2013 A Java Graph Editor and Graph Drawing Framework. Technical Report. Carleton University, School of Computer Science, Comp 5901 Directed Studies. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.188.5066&rank=1"},{"key":"e_1_3_3_13_2","volume-title":"An Efficient Implementation of the PC-Tree Algorithm of Shih & Hsu\u2019s Planarity Test","author":"Hsu Wen-Lian","year":"2003","unstructured":"Wen-Lian Hsu. 2003. An Efficient Implementation of the PC-Tree Algorithm of Shih & Hsu\u2019s Planarity Test. Technical Report. Institute of Information Science, Academia Sinica. http:\/\/iasl.iis.sinica.edu.tw\/webpdf\/paper-2003-PLANAR_implementation.pdf"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035179"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-3975(02)00435-8"},{"key":"e_1_3_3_16_2","volume-title":"PQ-Trees, An Implementation as Template Class in C++","author":"Leipert Sebastian","year":"1997","unstructured":"Sebastian Leipert. 1997. PQ-Trees, An Implementation as Template Class in C++. Technical Report. University of Cologne. http:\/\/e-archive.informatik.uni-koeln.de\/id\/eprint\/259"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-3975(98)00120-0"},{"key":"e_1_3_3_18_2","volume-title":"Complexidade de constru\u00e7\u00e3o de \u00e1rvores PQR","author":"Zanetti Jo\u00e3o Paulo Pereira","year":"2012","unstructured":"Jo\u00e3o Paulo Pereira Zanetti. 2012. Complexidade de constru\u00e7\u00e3o de \u00e1rvores PQR. Master\u2019s Thesis. Universidade Estadual de Campinas, Instituto de Computa\u00e7\u00e3o. http:\/\/bdtd.ibict.br\/vufind\/Record\/CAMP_0b551865d78ef032289f17f95e3ccee7"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611653","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:12Z","timestamp":1750178172000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,14]]},"references-count":17,"alternative-id":["10.1145\/3611653"],"URL":"https:\/\/doi.org\/10.1145\/3611653","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2023,10,14]]}}}