Abstract
In this paper, we present a dynamic algorithm that checks if a single-source embedded digraph is upward planar in the presence of edge insertions and edge deletions. Let G φ be an upward planar single-source embedded digraph and let G′ φ′ be a single-source embedded digraph obtained by updating G φ . We show that the upward planarity of G′ φ′ can be checked in O(logn) amortized time when the external face is fixed.
Chapter PDF
Similar content being viewed by others
References
Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 152–164. Springer, Heidelberg (2002)
Bertolazzi, P., Battista, G.D., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474–506 (2002)
Bertolazzi, P., Battista, G.D., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)
Bertolazzi, P., Battista, G.D., Mannino, C., Tamassia, R.: Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27(1), 132–169 (1998)
Demetrescu, C., Finocchi, I., Italiano, G.: Handbook of Graph Theory. In: Yellen, J., Gross, J.L. (eds.) Dynamic Graph Algorithms. CRC Press Series, in Discrete Mathematics and Its Applications, vol. 10.2 (2003) ISBN 1-58488-090-2
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)
Didimo, W.: Computing upward planar drawings using switch-regularity heuristics. In: SOFSEM, pp. 117–126 (2005)
Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 117–128. Springer, Heidelberg (2006)
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)
Hutton, M.D., Lubiw, A.: Upward planar drawing of single-source acyclic digraphs. SIAM J. Comput. 25(2), 291–311 (1996)
Papakostas, A.: Upward planarity testing of outerplanar DAGs. In: Proceedings Graph Drawing. pp. 298–306 (1994)
Tamassia, R.: On-line planar graph embedding. J. Algorithms 21(2), 201–239 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rextin, A., Healy, P. (2009). A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs. In: Tollis, I.G., Patrignani, M. (eds) Graph Drawing. GD 2008. Lecture Notes in Computer Science, vol 5417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00219-9_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-00219-9_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00218-2
Online ISBN: 978-3-642-00219-9
eBook Packages: Computer ScienceComputer Science (R0)