Abstract
The upward planarity testing problem is known to be NP-hard. We describe an O(n 4)-time upward planarity testing and embedding algorithm for the class of digraphs that do not contain rigid triconnected components. We also present a new FPT algorithm that solves the upward planarity testing and embedding problem for general digraphs.
This work is partially supported by the MIUR Project ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Applications.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bertolazzi, P., Battista, G.D., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 6(12), 476–497 (1994)
Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002)
Bertolazzi, P., Di Battista, G., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27, 132–169 (1998)
Chan, H.: A parameterized algorithm for upward planarity testing. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 157–168. Springer, Heidelberg (2004)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Upper Saddle River (1999)
Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 275–298 (1998)
Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25, 956–997 (1996)
Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. Technical report. RT-006-05, DIEI - Universitá di Perugia, Italy (2005)
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)
Healy, P., Lynch, K.: Building blocks of upward planar digraphs. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 296–306. Springer, Heidelberg (2005)
Healy, P., Lynch, K.: Building blocks of upward planar digraphs. Technical report, TR UL-CSIS-05-2 (2005)
Healy, P., Lynch, K.: Fixed-parameter tractable algorithms for testing upward planarity. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 199–208. Springer, Heidelberg (2005)
Hutton, M.D., Lubiw, A.: Upward planarity testing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291–311 (1996)
Papakostas, A.: Upward planarity testing of outerplanar dags. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 7298–7306. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Didimo, W., Giordano, F., Liotta, G. (2006). Upward Spirality and Upward Planarity Testing. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_12
Download citation
DOI: https://doi.org/10.1007/11618058_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)