Upward Point Set Embeddability for Convex Point Sets is in $P$

Details Upward Point Set Embeddability for Convex Point Sets is in $P$ Upward Point Set Embeddability for Convex Point Sets is in $P$

2011-08-15

arxiv.org/abs/1108.3092v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we present a polynomial dynamic programming algorithm that tests whether a $n$-vertex directed tree $T$ has an upward planar embedding into a convex point-set $S$ of size $n$. Further, we extend our approach to the class of outerplanar digraphs. This nontrivial and surprising result implies that any given digraph can be efficiently tested for an upward planar embedding into a given convex point set.

Affiliated with

Also associated with

No associations

Rating

Upward Point Set Embeddability for Convex Point Sets is in $P$ 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 Upward Point Set Embeddability for Convex Point Sets is in $P$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upward Point Set Embeddability for Convex Point Sets is in $P$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-194312