Upward Point-Set Embeddability

Details Upward Point-Set Embeddability Upward Point-Set Embeddability

2010-10-28

arxiv.org/abs/1010.5937v1

Computer Science

Data Structures and Algorithms

Scientific paper

We study the problem of Upward Point-Set Embeddability, that is the problem of deciding whether a given upward planar digraph $D$ has an upward planar embedding into a point set $S$. We show that any switch tree admits an upward planar straight-line embedding into any convex point set. For the class of $k$-switch trees, that is a generalization of switch trees (according to this definition a switch tree is a $1$-switch tree), we show that not every $k$-switch tree admits an upward planar straight-line embedding into any convex point set, for any $k \geq 2$. Finally we show that the problem of Upward Point-Set Embeddability is NP-complete.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583762