Planar Graph Drawing

Cover......Page 1
Title......Page 4
Copyright......Page 5
Motivation......Page 6
Organization of the Book......Page 7
Acknowledgments......Page 8
Contents......Page 10
1.1 Introduction......Page 16
1.2 Historical Background......Page 17
1.3 Drawing Styles......Page 18
1.3.1 Planar Drawing......Page 19
1.3.3 Straight Line Drawing......Page 20
1.3.5 Orthogonal Drawing......Page 21
1.3.6 Box-Orthogonal Drawing......Page 22
1.3.9 Grid Drawing......Page 23
1.3.10 Visibility Drawing......Page 24
1.4 Properties of Drawings......Page 25
1.5 Applications of Graph Drawing......Page 26
1.5.1 Floorplanning......Page 27
1.5.2 VLSI Layout......Page 28
1.5.3 Software Engineering......Page 29
1.6 Scope of This Book......Page 30
Exercise......Page 31
2.1.1 Graphs and Multigraphs......Page 34
2.1.2 Subgraphs......Page 35
2.1.4 Chains......Page 36
2.1.6 Trees and Forests......Page 37
2.1.7 Complete Graphs......Page 38
2.2 Planar Graphs......Page 39
2.2.1 Plane Graphs......Page 41
2.2.2 Euler\'s Formula......Page 44
2.2.3 Dual Graph......Page 45
Exercise......Page 46
3.1 What is an Algorithm?......Page 48
3.2.1 The O( ) notation......Page 49
3.2.3 NP-Complete Problems......Page 50
3.3 Data Structures and Graph Representation......Page 51
3.4.1 Depth-First Search......Page 53
3.4.2 Breadth-First Search......Page 54
3.5 Data Structures for Plane Graphs......Page 57
Exercise......Page 59
4.1 Introduction......Page 60
4.2.1 Canonical Ordering......Page 61
4.2.2 Shift Algorithm......Page 65
4.2.3 Linear-Time Implementation......Page 69
4.3.1 Barycentric Representation......Page 73
4.3.2 Schnyder Labeling......Page 77
4.3.3 Realizer......Page 81
4.3.4 Drawing Algorithm with Realizer......Page 84
4.4 Compact Grid Drawing......Page 87
4.4.1 Four-Canonical Ordering......Page 89
4.4.2 Algorithm Four-Connected-Draw......Page 92
4.4.3 Drawing G\'......Page 94
Exercise......Page 102
5.1 Introduction......Page 104
5.2 Convex Drawing......Page 105
5.3 Convex Testing......Page 109
5.3.1 Definitions......Page 110
5.3.2 Condition II......Page 113
5.3.3 Testing Algorithm......Page 116
5.4.1 Canonical Decomposition......Page 120
5.4.2 Algorithm for Convex Grid Drawing......Page 125
5.5.1 Four-Canonical Decomposition......Page 132
5.5.2.1 How to Compute x-Coordinates......Page 134
5.5.2.2 How to Compute y-Coordinates......Page 138
Exercises......Page 142
6.1 Introduction......Page 144
6.2 Rectangular Drawing and Matching......Page 145
6.3.1 Thomassen\'s Theorem......Page 150
6.3.2 Sufficiency......Page 152
6.3.3 Rectangular Drawing Algorithm......Page 167
6.3.4 Rectangular Grid Drawing......Page 171
6.4 Rectangular Drawings without Designated Corners......Page 174
6.5 Rectangular Drawings of Planar Graphs......Page 176
6.5.1 Case for a Subdivision of a Planar 3-connected Cubic Graph......Page 178
6.5.2 The Other Case......Page 184
Exercise......Page 188
7.2 Preliminaries......Page 190
7.3 Box-Rectangular Drawings with Designated Corner Boxes......Page 193
7.4 Box-Rectangular Drawings without Designated Corners......Page 197
7.4.1 Box-Rectangular Drawings of G with 3......Page 198
7.4.2 Box-Rectangular Drawings of G with 4......Page 208
Exercise......Page 210
8.1 Introduction......Page 212
8.2.1 Orthogonal Representation......Page 213
8.2.2 Flow Network......Page 216
8.2.3 Finding Bend-Optimal Drawing......Page 217
8.3 Linear Algorithm for Bend-Optimal Drawing......Page 223
8.3.1 Genealogical Tree......Page 226
8.3.2 Assignment and Labeling......Page 228
8.3.3 Feasible Orthogonal Drawing......Page 232
8.3.4 Algorithm......Page 239
8.4 Orthogonal Grid Drawing......Page 242
8.5 Orthogonal Drawings without Bends......Page 244
8.6 Bibliographic Notes......Page 246
Exercise......Page 247
9.1 Introduction......Page 248
9.2 Good Slicing Graphs......Page 250
9.3 Octagonal Drawing......Page 253
9.3.1 Algorithm Octagonal-Draw......Page 254
9.3.2 Embedding a Slicing Path......Page 258
9.3.3 Correctness and Time Complexity......Page 264
9.4 Bibliographic Notes......Page 265
Exercise......Page 266
A.1 Introduction......Page 268
A.2 Planarity Testing......Page 269
A.2.1 st-Numbering......Page 270
A.2.2 Bush Form and PQ-Tree......Page 274
A.2.3 Planarity Testing Algorithm......Page 278
A.3 Finding Planar Embedding......Page 281
A.3.1 Algorithm for Extending Au into Adj......Page 282
A.3.2 Algorithm for Constructing Au......Page 286
A.4 Bibliographic Notes......Page 292
Bibliography......Page 296
Index......Page 306