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.

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
ID Code:1273

Repository Staff Only: item control page

References

Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward Geometric Graph Embeddings into Point Sets. In: Brandes, U., Cornelsen,S.(eds.) GD 2010. LNCS, vol. 6502, pp. 25–37. Springer, Heidelberg (2011)

Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theor. Comput. Sci. 408(2-3), 129–142 (2008)

Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Computat. Geom. Th. Appl. 43, 219–232 (2010)

Bose, P.: On embedding an outer-planar graph in a point set. Computat. Geom. Th. Appl. 23(3), 303–312 (2002)

Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Alg. Appl. 1(2), 1–15 (1997)

Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Alg. Appl. 10(2), 353–366 (2006)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Trotta, F., Wismath, S.K.: k-colored point-set embeddability of outerplanar graphs. J. Graph Alg. Appl. 12(1), 29–49 (2008)

Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward Point-Set Embeddability. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 272–283. Springer, Heidelberg (2011)

Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A.: Computing Upward Topological Book Embeddings of Upward Planar Digraphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 172–183. Springer, Heidelberg (2007)

Giordano, F., Liotta, G., Whitesides, S.: Embeddability Problems for Upward Planar Digraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp.242–253. Springer, Heidelberg (2009)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mont. 98, 165–166 (1991)

Halton, J.: On the thickness of graphs of given degree. Inf. Sci. 54, 219–238 (1991)

Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs: Part I. SIAM J. Comput. 28(4), 1510–1539 (1999)

Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Alg. Appl. 6(1), 115–129 (2002)

Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward point set embeddability for convex point sets is in P. Technical report. arXiv:1108.3092, http://arxiv.org/abs/1108.3092

Mchedlidze, T., Symvonis, A.: On ρ-Constrained Upward Topological Book Embeddings. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 411–412. Springer, Heidelberg (2010)

Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001)