Upward Point Set Embeddability for Convex Point Sets Is in P
Kaufmann, Michael and Mchedlidze, Tamara and Symvonis, Antonios (2012) Upward Point Set Embeddability for Convex Point Sets Is in P. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 403-414 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_38).
Full text not available from this repository.
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. We also note that our approach can be extended 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.
Repository Staff Only: item control page