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

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

2009-09-15

arxiv.org/abs/0909.2787v1

Computer Science

Data Structures and Algorithms

Accepted to ISAAC2009

Scientific paper

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 we can be efficiently test whether $G$ admits a crossing-free acyclic HP-completion set.

Affiliated with

Also associated with

No associations

Rating

Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555881