Drawing Graphs Methods and Models

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
Ren ́ Weiskircher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
e
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 What Is a Planar Graph? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 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 M ̈ller-Hannemann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
u
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, S ́ndor P. Fekete, and Gunnar W. Klau . . . . . . . 121
a
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
J ̈ rgen Branke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
u
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

Another Graph Theory Books
Download