Abstract
We study the problem of Upward Point-Set Embeddability, that is the problem of deciding whether a given upward planar digraph D has an upward planar embedding into a point set S. We show that any switch tree admits an upward planar straight-line embedding into any convex point set. For the class of k-switch trees, that is a generalization of switch trees (according to this definition a switch tree is a 1-switch tree), we show that not every k-switch tree admits an upward planar straight-line embedding into any convex point set, for any k ≥ 2. Finally we show that the problem of Upward Point-Set Embeddability is NP-complete.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward geometric graph embeddings into point sets. In: 18th International Symposium on Graph Drawing (GD 2010), LNCS (2010) (to appear)
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)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward point-set embeddability. Technical report. arXiv:1010:5937, http://arxiv.org/abs/1010:5937
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)
Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mont. 98, 165–166 (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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A. (2011). Upward Point-Set Embeddability. In: Černá, I., et al. SOFSEM 2011: Theory and Practice of Computer Science. SOFSEM 2011. Lecture Notes in Computer Science, vol 6543. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18381-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-18381-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18380-5
Online ISBN: 978-3-642-18381-2
eBook Packages: Computer ScienceComputer Science (R0)