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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show an $O(n)$-time reduction from the problem of testing whether amultiset of positive integers can be partitioned into two multisets so that thesum of the integers in each multiset is equal to $n/2$ to the problem oftesting whether an $n$-vertex biconnected outerplanar DAG admits an upwardplanar drawing. This constitutes the first barrier to the existence ofefficient algorithms for testing the upward planarity of DAGs with no largetriconnected minor.  We also show a result in the opposite direction. Suppose that partitioning amultiset of positive integers into two multisets so that the sum of theintegers in each multiset is $n/2$ can be solved in $f(n)$ time. Let $G$ be an$n$-vertex biconnected outerplanar DAG and $e$ be an edge incident to the outerface of an outerplanar drawing of $G$. Then it can be tested in $O(f(n))$ timewhether $G$ admits an upward planar drawing with $e$ on the outer face.

Upward Planarity Testing of Biconnected Outerplanar DAGs Solves Partition