Table of Contents
1. Graph Drawing and Its Applications
Rudolf Fleischer and Colin Hirsch................................................. 1
1.1
Introduction.............................................................................. 1
1.2
Some Applications.................................................................... 3
1.3
How to Draw a Graph........................................................ 17
1.4
Algorithmic Approaches to Graph
Drawing............................... 20
1.5
Conclusion ......................................................................... 21
2. Drawing Planar Graphs
Rene Weiskircher........................................................................ 23
2.1
Introduction............................................................................. 23
2.2
What Is a Planar Graph?.......................................................... 23
23 Planarity Testing.................................................................. 25
2.4
How to Make a Graph Planar.............................................. 29
2.5
How to Make a Planar Graph 2-Connected Planar................ 31
2.6
Convex Representations...................................................... 33
2.7
Methods Based on Canonical
Orderings.................................... 37
3. Drawing Trees, Series-Parallel Digraphs, and Lattices
Matthias Muller-Hannemann......................................................... 46
3.1
Trees...................................................................................... 46
3.2
Series-Parallel Digraphs........................................................... 52
3.3
Lattices.............................................................................. 63
4. Drawing on Physical Analogies
Ulrik Brandes............................................................................... 71
4.1
The Springs ............................................................................ 71
4.2
Force-Directed Placement ...................................................... 72
4.3
Energy-Based Placement..................................................... 78
4.4
Modeling with Forces and
Energies...................................... 82
5. Layered Drawings of Digraphs
Oliver Bastert and Christian Matuszewski ..................................... 87
5.1
Introduction........................................................................ 87
5.2
Cycle Removal..................................................................... 89
5.3
Layer Assignment................................................................ 96
5.4
Crossing Reduction............................................................... 101
5.5
Horizontal Coordinates.......................................................... 112
5.6
Positioning of Edges.............................................................. 115
5.7
Related Approaches............................................................ 118
6. Orthogonal Graph Drawing
Markus Eiglsperger, Sandor P. Fekete, and Gunnar W. Klau........... 121
6.1
Introduction........................................................................ 121
6.2
Angles in Drawings............................................................. 122
6.3
Orthogonal Drawings and Their Encoding............................. 126
6.4
Heuristics........................................................................... 132
6.5
Flow-Based Methods........................................................... 147
6.6
Compaction ........................................................................ 155
6.7
Improving Other Aesthetic
Criteria....................................... 167
6.8
Conclusions and Open Problems........................................... 170
7. 3D Graph Drawing
Britta Landgraf............................................................................ 172
7.1
Introduction......................................................................... 172
7.2
Physical Simulation.............................................................. 173
7.3
Layering............................................................................. 174
7.4
3D Orthogonal Drawings of Graphs
of Maximum Degree Six . 176
7.5
3D Orthogonal Drawings of Graphs
of Arbitrary Degree....... 182
7.6
Viewpoints.......................................................................... 190
8. Drawing Clusters and Hierarchies
Ralf Brockenauer and Sabine Cornelsen........................................ 193
8.1
Definitions.......................................................................... 193
8.2
Clustering Methods............................................................. 197
8.3
Planar Drawings of Hierarchical
Clustered Graphs................ 202
8.4
Hierarchical Representation of Compound Graphs................. 210
8.5
Force-Directed Methods for
Clustered Graphs...................... 216
8.6
Online Graph Drawing of Huge Graphs - A Case Study......... 222
8.7
Summary............................................................................ 227
9. Dynamic Graph Drawing
Jiirgen Branke.............................................................................. 228
9.1
Introduction........................................................................ 228
9.2
Maintaining the Mental Map - What
Does It Mean?.............. 229
9.3
Coping with the Dynamics................................................... 236
9.4
Conclusion and Future Work................................................ 245
10. Map Labeling with Application to Graph Drawing
Gabriele Neyer ......................................................................... 247
10.1
Formal Background............................................................. 248
10.2
Contents and Complexity Overview...................................... 251
10.3
Point Feature Label Placement............................................ 251
10.4
Line Feature Label Placement ........................................... 265
10.5
Graphical Feature Label Placement...................................... 268
10.6
General Optimization Strategies
Applied to Map Labeling ... 272
A. Software Packages
Thomas Willhalm........................................................................ 274
Bibliography................................................................................... 283
Index.............................................................................................. 307