Bitonic st-orderings of Biconnected Planar Graphs

Gronemann, Martin (2014) Bitonic st-orderings of Biconnected Planar Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 162-173 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_14).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_14
Classifications:G Algorithms and Complexity > G.280 Canonical Ordering
G Algorithms and Complexity > G.630 Labeling
P Styles > P.540 Planar
P Styles > P.780 Symmetric
P Styles > P.900 Visibility
ID Code:1430

Repository Staff Only: item control page

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)