Simultaneous PQ-ordering with applications to constrained embedding problems

Thomas Blaesius, Ignaz Rutter

Research output: Contribution to journalArticleAcademicpeer-review

25 Citations (Scopus)

Abstract

In this article, we define and study the new problem of Simultaneous PQ-Ordering. Its input consists of a set of PQ-trees, which represent sets of circular orders of their leaves, together with a set of child-parent relations between these PQ-trees, such that the leaves of the child form a subset of the leaves of the parent. Simultaneous PQ-Ordering asks whether orders of the leaves of each of the trees can be chosen simultaneously; that is, for every child-parent relation, the order chosen for the parent is an extension of the order chosen for the child. We show that Simultaneous PQ-Ordering is NP-complete in general, and we identify a family of instances that can be solved efficiently, the 2-fixed instances. We show that this result serves as a framework for several other problems that can be formulated as instances of Simultaneous PQ-Ordering. In particular, we give linear-time algorithms for recognizing simultaneous interval graphs and extending partial interval representations. Moreover, we obtain a linear-time algorithm for Partially PQ-Constrained Planarity for biconnected graphs, which asks for a planar embedding in the presence of PQ-trees that restrict the possible orderings of edges around vertices, and a quadratic-time algorithm for Simultaneous Embedding with Fixed Edges for biconnected graphs with a connected intersection. Both results can be extended to the case where the input graphs are not necessarily biconnected but have the property that each cutvertex is contained in at most two nontrivial blocks. This includes, for example, the case where both graphs have a maximum degree of 5.
Original languageEnglish
Article number16
Number of pages46
JournalACM Transactions on Algorithms
Volume12
Issue number2
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Algorithms
  • Theory
  • Ordering problem
  • PQ-trees
  • planar embeddings
  • simultaneous embedding
  • interval graphs

Fingerprint

Dive into the research topics of 'Simultaneous PQ-ordering with applications to constrained embedding problems'. Together they form a unique fingerprint.

Cite this