A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs

Rextin , Aimal and Healy, Patrick (2009) A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 254-265 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_24).

Full text not available from this repository.

Abstract

In this chapter, we present a dynamic algorithm that checks if a singlesource 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(log n) amortized time when the external face is fixed.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_24
Classifications:P Styles > P.840 Upward
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:911

Repository Staff Only: item control page

References

Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two simplified algorithms for maintaining order in a list. In: 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, chap. 10.2, Dynamic Graph Algorithms. J. Yellen and J.L. Gross eds., CRC Press Series, in Discrete Mathematics and Its Applications, ISBN 1-58488-090-2 (2003)

Di Battista, G., Eades, P., Tamassia, R., G. Tollis, I.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

Didimo, W.: Computing upward planar drawings using switch-regularity heuristics. In: SOF- SEM. pp. 117–126 (2005)

Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. In: GD 05., 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)