Bitonic st-orderings for Upward Planar Graphs

Gronemann, Martin (2016) Bitonic st-orderings for Upward Planar Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 222-235(Official URL:

Full text not available from this repository.


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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.280 Canonical Ordering
P Styles > P.480 Layered

Actions (login required)

View Item View Item