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 study the problem of existence of a crossing-free acyclichamiltonian path completion (for short, HP-completion) set for embedded upwardplanar digraphs. In the context of book embeddings, this question becomes:given an embedded upward planar digraph $G$, determine whether there exists anupward 2-page book embedding of $G$ preserving the given planar embedding.  Given an embedded $st$-digraph $G$ which has a crossing-free HP-completionset, we show that there always exists a crossing-free HP-completion set with atmost two edges per face of $G$. For an embedded $N$-free upward planar digraph$G$, we show that there always exists a crossing-free acyclic HP-completion setfor $G$ which, moreover, can be computed in linear time. For a width-$k$embedded planar $st$-digraph $G$, we show that we can be efficiently testwhether $G$ admits a crossing-free acyclic HP-completion set.

Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs