English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

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 circularorders of their leaves, together with a set of child-parent relations betweenthese PQ-trees, such that the leaves of the child form a subset of the leavesof the parent. Simultaneous PQ-Ordering asks whether orders of the leaves ofeach of the trees can be chosen simultaneously, that is, for every child-parentrelation the order chosen for the parent is an extension of the order chosenfor the child. We show that Simultaneous PQ-Ordering is NP-complete in generaland that it is efficiently solvable for a special subset of instances, the2-fixed instances. We then show that several constrained embedding problems canbe formulated as such 2-fixed instances.  In particular, we obtain a linear-time algorithm for Partially PQ-ConstrainedPlanarity for biconnected graphs, a common generalization of two recentlyconsidered embedding problems, and a quadratic-time algorithm for SimultaneousEmbedding with Fixed Edges for biconnected graphs with a connectedintersection; formerly only the much more restricted case that the intersectionis biconnected was known to be efficiently solvable. Both results can beextended to the case where the input graphs are not necessarily biconnected buthave the property that each cutvertex is contained in at most two non-trivialblocks. This includes for example the case where both graphs have maximumdegree 5. Moreover, we give an optimal linear-time algorithm for recognition ofsimultaneous interval graphs, improving upon a recent O(n^2 log n)-timealgorithm due to Jampani and Lubiw and show that this can be used to also solvethe problem of extending partial interval representations of graphs with nvertices and m edges in time O(n + m), improving a recent result of Klav\'ik etal.

Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems