Abstract
Vertex orderings play an important role in the design of graph drawing algorithms. Compared to canonical orderings, st-orderings lack a certain property that is required by many drawing methods. In this paper, we propose a new type of st-ordering for biconnected planar graphs that relates the ordering to the embedding. We describe a linear-time algorithm to obtain such an ordering and demonstrate its capabilities with two 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
Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. In: Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, SoCG 2012, pp. 21–30. ACM (2012)
Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering. Journal of Graph Algorithms and Applications 15(1), 97–126 (2011)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
Di Battista, G., Tamassia, R.: Incremental planarity testing. In: 30th Annual Symposium on Foundations of Computer Science, pp. 436–441 (1989)
Even, S., Tarjan, R.E.: Computing an st-numbering. Theoretical Computer Science 2(3), 339–344 (1976)
Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167–182. Springer, Heidelberg (1999)
Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)
Harel, D., Sardas, M.: An algorithm for straight-line drawing of planar graphs. Algorithmica 20(2), 119–135 (1998)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996)
OGDF - Open Graph Drawing Framework, http://www.ogdf.net/
Tamassia, R.: Handbook of Graph Drawing and Visualization (Discrete Mathematics and Its Applications). Chapman & Hall/CRC (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gronemann, M. (2014). Bitonic st-orderings of Biconnected Planar Graphs. In: Duncan, C., Symvonis, A. (eds) Graph Drawing. GD 2014. Lecture Notes in Computer Science, vol 8871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45803-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-662-45803-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45802-0
Online ISBN: 978-3-662-45803-7
eBook Packages: Computer ScienceComputer Science (R0)