On upward point set embeddability ?
We study the problem of upward point set embeddability, that is the problem to decide whether an n-vertex directed graph has an upward planar drawing when its vertices have to be placed on the points of a given point set of size n . We first present some positive and negative results concerning directed trees and convex point sets. Next, we prove that upward point set embeddability can be solved in polynomial time for the case of a directed tree and a convex point set. Further, we extend our approach to the class of outerplanar directed graphs. This implies that upward point set embeddability can be efficiently solved for the case of convex point sets. Finally, we show that the general problem of upward point set embeddability is NP NP -complete even for 2-convex point sets.
directed trees point set embedding upward planar digraphs outerplanar digraphs