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

In this paper we study the problem of existence of a crossing-free acyclic hamiltonian path completion (for short, HP-completion) set for embedded upward planar digraphs. In the context of book embeddings, this question becomes: given an embedded upward planar digraph G, determine whether there exists an upward 2-page book embedding of G preserving the given planar embedding. Given an embedded st-digraph G which has a crossing-free HP-completion set, we show that there always exists a crossing-free HP-completion set with at most 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 set for G which, moreover, can be computed in linear time For a width-k embedded planar st-digraph G, we show that it can be efficiently tested whether G admits a crossing-free acyclic HP-completion set.