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 , pp. 403-414(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_38).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_38
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1273

Actions (login required)

View Item View Item