Bitonic st-orderings for Upward Planar Graphs

Gronemann, Martin (2016) Bitonic st-orderings for Upward Planar Graphs.
Published In: Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), Lecture Notes in Computer Science. 9801 Springer 2016, pp. 222-235.


Canonical orderings serve as the basis for many incremental planar drawing algorithms. All these techniques, however, have in common that they are limited to undirected graphs. While st-orderings do extend to directed graphs, especially planar st-graphs, they do not offer the same properties as canonical orderings. In this work we extend the so called bitonic st-orderings to directed graphs. We fully characterize planar st-graphs that admit such an ordering and provide a linear-time algorithm for recognition and ordering. If for a graph no bitonic st-ordering exists, we show how to find in linear time a minimum set of edges to split such that the resulting graph admits one. With this new technique we are able to draw every upward planar graph on n vertices by using at most one bend per edge, at most n - 3 bends in total and within quadratic area.

Download: [img] PDF - Preprinted Version
Download (407kB)
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
Depositing User: Martin Gronemann
Date Deposited: 09 Mar 2018 13:36
Last Modified: 13 Mar 2018 09:27