Experimental Comparison of PC-Trees and PQ-Trees

Authors Simon D. Fink , Matthias Pfretzschner , Ignaz Rutter



PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.43.pdf
  • Filesize: 10.34 MB
  • 13 pages

Document Identifiers

Author Details

Simon D. Fink
  • Faculty of Informatics and Mathematics, Universität Passau, Germany
Matthias Pfretzschner
  • Faculty of Informatics and Mathematics, Universität Passau, Germany
Ignaz Rutter
  • Faculty of Informatics and Mathematics, Universität Passau, Germany

Cite AsGet BibTex

Simon D. Fink, Matthias Pfretzschner, and Ignaz Rutter. Experimental Comparison of PC-Trees and PQ-Trees. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.43

Abstract

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. 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 [Hsu et al., 2003] 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 [Markus Chimani et al., 2014; Leipert, 1997], 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
  • Mathematics of computing → Trees
  • Mathematics of computing → Graph algorithms
Keywords
  • PQ-Tree
  • PC-Tree
  • circular consecutive ones
  • implementation
  • experimental evaluation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. S. Benzer. On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences, 45(11):1607-1620, November 1959. URL: https://doi.org/10.1073/pnas.45.11.1607.
  2. Thomas Bläsius and Ignaz Rutter. Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms, 12(2):16:1-16:46, 2016. URL: https://doi.org/10.1145/2738054.
  3. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci., 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
  4. John M. Boyer, Cristina G. Fernandes, Alexandre Noma, and José C. de Pina. Lempel, Even, and Cederbaum planarity method. In Experimental and Efficient Algorithms, pages 129-144. Springer Berlin Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-540-24838-5_10.
  5. Guido Brückner and Ignaz Rutter. Partial and constrained level planarity. In Philip N. Klein, editor, Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17), pages 2000-2011. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.130.
  6. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 17. CRC Press, 2014. Google Scholar
  7. Alex William Cregten and Hannes Kristján Hannesson. Implementation of a planarity testing method using PQ-trees. Technical report, Reykjavík University, 2017. URL: https://skemman.is/bitstream/1946/29618/1/Planarity_testing_with_PQTrees.pdf.
  8. Alejandro Estrella-Balderrama, J. Joseph Fowler, and Stephen G. Kobourov. Graph simultaneous embedding tool, GraphSET. In Graph Drawing, pages 169-180. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-00219-9_17.
  9. Gregory A. Grothaus, Adeel Mufti, and T. M. Murali. Automatic layout and visualization of biclusters. Algorithms for Molecular Biology, 1(1):15, 2006. URL: https://doi.org/10.1186/1748-7188-1-15.
  10. Bernhard Haeupler and Robert E. Tarjan. Planarity algorithms via PQ-trees (extended abstract). Electronic Notes in Discrete Mathematics, 31:143-149, August 2008. URL: https://doi.org/10.1016/j.endm.2008.06.029.
  11. Jon Harris. JGraphEd - a java graph editor and graph drawing framework. Technical report, Carleton University, School of Computer Science, Comp 5901 Directed Studies, 2004. URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.5066&rank=1.
  12. Wen-Lian Hsu. An efficient implementation of the PC-tree algorithm of Shih & Hsu’s planarity test. Technical report, Institute of Information Science, Academia Sinica, 2003. URL: http://iasl.iis.sinica.edu.tw/webpdf/paper-2003-PLANAR_implementation.pdf.
  13. Wen-Lian Hsu and Ross McConnell. PQ trees, PC trees, and planar graphs. In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, chapter 32. Chapman and Hall/CRC, January 2004. URL: https://doi.org/10.1201/9781420035179.
  14. Wen-Lian Hsu and Ross M. McConnell. PC trees and circular-ones arrangements. Theoretical Computer Science, 296(1):99-116, March 2003. URL: https://doi.org/10.1016/s0304-3975(02)00435-8.
  15. Sebastian Leipert. PQ-trees, an implementation as template class in C++. Technical report, University of Cologne, 1997. URL: http://e-archive.informatik.uni-koeln.de/id/eprint/259.
  16. Wei-Kuan Shih and Wen-Lian Hsu. A new planarity test. Theoretical Computer Science, 223(1-2):179-191, July 1999. URL: https://doi.org/10.1016/s0304-3975(98)00120-0.
  17. João Paulo Pereira Zanetti. Complexidade de construção de árvores PQR. Master’s thesis, Universidade Estadual de Campinas, Instituto de Computação, 2012. URL: http://bdtd.ibict.br/vufind/Record/CAMP_0b551865d78ef032289f17f95e3ccee7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail