Upward Point Set Embeddability for Convex Point Sets is in P
Kaufmann, Michael · Mchedlidze, Tamara · Symvonis, Antonios
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.