Bitonic st-orderings of Biconnected Planar Graphs - Graph Drawing - page 172

5 Implementation Details

The presented work has been implemented in C++ using the OpenGraphDrawing
Framework (OGDF) [11]. For the canonical ordering, we implemented the leftist canon-
icalordering algorithm as described by Badent et al. [2]. The linear-time implemen-
tation of Gutwenger and Mutzel [8] is used for the SPQR-tree that is required for
Theorem 1. It is part of the OGDF, publicly available and provides a convenient
interface to navigate the tree and the skeletons.

6Con lu ion

We have shown that every biconnected planar graph has a bitonic st -order that can be
obtained in linear time. Moreover, two applications have been presented, both requiring
the property of being bitonic. We believe that the bitonic st -ordering is a useful addition
to the set of existing tools. Besides having potentially a broad range of applications, it
may simplify existing methods considerably.

References

1. Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing
cartograms with optimal complexity. In: ProceedingsoftheTwenty-Eighth Annual Sympo-
siumonComputational Geometry, SoCG 2012, pp. 21-30. ACM (2012)
2. Badent, M., Brandes, U., Cornelsen, S.: More canonical ordering.Journal of Graph Algo-
rithms and Applications 15(1), 97-126 (2011)
3. de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinator-
ica 10(1), 41-51 (1990)
4. Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing:Algorithms for the
Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
5. Di Battista, G., Tamassia, R.: Incremental planarity testing. In: 30th Annual Symposiumon
Foundations of Computer Science, pp. 436-441 (1989)
6. Even, S., Tarjan, R.E.: Computing an st-numbering. Theoretical Computer Science 2(3),
339-344 (1976)
7. Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: White-
sides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167-182. Springer, Heidelberg (1999)
8. 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)
9. Harel, D., Sardas, M.: An algorithm for straight-line drawing of planar graphs. Algorith-
mica 20(2), 119-135 (1998)
10. Kant, G.: Drawing planar graphs using the canonical ordering.Algorithmica 16, 4-32 (1996)
11. OGDF - Open Graph Drawing Framework, http://www.ogdf.net/
12. Tamassia, R.: Handbook of Graph Drawing and Visualization (Discrete Mathematics and Its
Applications). Chapman & Hall/CRC (2007)