Simultaneous PQ-ordering with applications to constrained embedding problems
From MaRDI portal
Abstract: In this paper, we define and study the new problem 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 that it is efficiently solvable for a special subset of instances, the 2-fixed instances. We then show that several constrained embedding problems can be formulated as such 2-fixed instances. In particular, we obtain a linear-time algorithm for Partially PQ-Constrained Planarity for biconnected graphs, a common generalization of two recently considered embedding problems, and a quadratic-time algorithm for Simultaneous Embedding with Fixed Edges for biconnected graphs with a connected intersection; formerly only the much more restricted case that the intersection is biconnected was known to be efficiently solvable. 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 non-trivial blocks. This includes for example the case where both graphs have maximum degree 5. Moreover, we give an optimal linear-time algorithm for recognition of simultaneous interval graphs, improving upon a recent O(n^2 log n)-time algorithm due to Jampani and Lubiw and show that this can be used to also solve the problem of extending partial interval representations of graphs with n vertices and m edges in time O(n + m), improving a recent result of Klav'ik et al.
Recommendations
Cited in
(32)- Partial and simultaneous transitive orientations via modular decompositions
- Simple algorithms for partial and simultaneous rectangular duals with given contact orientations
- Simultaneous representation of proper and unit interval graphs
- Partial and constrained level planarity
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
- Experimental comparison of PC-trees and PQ-trees
- Maintaining triconnected components under node expansion
- On the classes of interval graphs of limited nesting and count of lengths
- Convex embeddability and knot theory
- Simultaneous representation of proper and unit interval graphs
- Bounded Embeddings of Graphs in the Plane
- Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
- Maintaining triconnected components under node expansion
- Constrained planarity in practice -- engineering the synchronized planarity algorithm
- Upward and orthogonal planarity are W[1]-hard parameterized by treewidth
- Beyond level planarity: cyclic, torus, and simultaneous level planarity
- Synchronized Planarity with Applications to Constrained Planarity Problems
- Atomic Embeddability, Clustered Planarity, and Thickenability
- Simultaneous contact representations of planar graphs
- Clustered planarity with pipes
- Synchronized planarity with applications to constrained planarity problems
- Simultaneous PQ-ordering with applications to constrained embedding problems
- The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
- Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
- Simple realizability of abstract topological graphs
- Hanani-Tutte for radial planarity. II
- Extending partial representations of circular-arc graphs
- Simultaneous Embedding
- Parameterized complexity of graph planarity with restricted cyclic orders
- Minimal obstructions for partial representations of interval graphs
- Parameterized complexity of graph planarity with restricted cyclic orders
- The QuaSEFE problem
This page was built for publication: Simultaneous PQ-ordering with applications to constrained embedding problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962212)
