
558 CHAPTER 17. THE OPEN GRAPH DRAWING FRAMEWORK (OGDF)
10
1
12
13
14
15
16 17
18
19
20 21
22
23 24
25
26
27 28
29
0
1
2
3
4 30
5
31
6
32
7
33
8
34
9
35
36
37
10
1
12
13
14
15
1617
18
19
2021
22
2324
25
26
27
28
29
0
1
2
3
4
30
5
31
6
32
7
33
8
34
9
35
36
37
Figure 17.11 Two upward drawings of the same graph, drawn with SugiyamaLayout
(left, 27 crossings) and UpwardPlanarizationLayout (right, 1 crossing).
s-t-planar digraph is a directed, acyclic planar graph G with exactly one source s and
exactly one sink t. DominanceLayout applies the layout algorithm for s-t-planar digraphs
by Di Battista, Tamassia, and Tollis [DTT92]. If the input digraph G contains no transitive
edges, the algorithm computes a planar dominance ...