Thirty Essays on Geometric Graph Theory

Cover......Page 1
Thirty Essays on Geometric
Graph Theory......Page 4
Contents......Page 6
Contributors......Page 10
Minors, Embeddability, and Extremal Problems for Hypergraphs......Page 15
References......Page 17
1 Introduction......Page 19
1.2 Purpose and Timeliness of This Survey......Page 20
1.3 Structure of This Survey......Page 21
2 The RCN Project......Page 22
3 Lower Bounds I: Before 2004......Page 23
4 Lower Bounds II: The Breakthrough......Page 24
5 Lower Bounds III: Further Improvements......Page 25
6 Upper Bounds......Page 26
7.1 Sylvester's Four-Point Constant......Page 28
8 Further Thoughts and Future Research......Page 29
References......Page 31
1 Introduction......Page 33
2 Proof of Theorem 3......Page 34
References......Page 44
1 Introduction......Page 46
2 Some Background Motivation......Page 48
3 k-Blocked Sets with Small Color Classes......Page 49
4 4-Blocked Point Sets......Page 51
5 Midpoint-Blocked Point Sets......Page 59
References......Page 62
1 Introduction......Page 63
2 Preliminaries......Page 67
3 Disjoint Line Segments......Page 69
4 A Collection of Simple Polygons......Page 78
5 Obstacles in a Container......Page 81
6 Discussion......Page 83
References......Page 84
1 Introduction......Page 85
References......Page 95
1 Introduction......Page 96
1.1 Preliminary Work......Page 97
2 Sets of Edge-Disjoint Empty Triangles in Point Sets......Page 98
3 Covering the Triangles of Point Sets with Triangulations......Page 99
3.1 Points in Convex Position......Page 100
3.2 Covering the Empty Triangles on the Horton Set......Page 101
4 A Point in Many Edge-Disjoint Triangles......Page 103
4.1 Regular Polygons......Page 108
5 A Point in Many Edge-Disjoint Empty Triangles......Page 111
References......Page 113
1.1 Previous Results......Page 115
1.2 Our Results......Page 116
2.1 Notation Used in the Proof......Page 118
2.2 Proof in the Even Case......Page 119
2.3 Proof in the Odd Case......Page 123
3 Unbalanced Double-Chains with No NHAP......Page 124
4.1 Embedding on Balanced Double-Chains......Page 127
4.2 Open Problems......Page 130
References......Page 131
1 Introduction......Page 133
2.1 Planar Drawings, Planar Embeddings, and Planar Graphs......Page 134
2.3 Classes of Planar Graphs......Page 135
2.5 Area of a Drawing......Page 137
2.6 Directed Graphs and Planar Upward Drawings......Page 138
2.7 Proximity Drawings......Page 139
3 Straight-Line Drawings......Page 140
3.1 General Planar Graphs......Page 141
3.2 4-Connected and Bipartite Planar Graphs......Page 144
3.3 Series-Parallel Graphs......Page 146
3.4 Outerplanar Graphs......Page 148
3.5 Trees......Page 150
4.1 General Planar Graphs......Page 155
4.2 Series-Parallel and Outerplanar Graphs......Page 157
4.3 Trees......Page 158
5 Upward Drawings......Page 161
6 Convex Drawings......Page 163
7 Proximity Drawings......Page 165
8 Clustered Graph Drawings......Page 169
References......Page 172
1 Introduction......Page 178
2 Geometric RAC Graphs......Page 179
3 Complexity Questions About Geometric RAC Graphs......Page 181
4.1 Allowing Bends Along the Edges......Page 184
4.2 Drawings with Nonorthogonal Edge Crossings......Page 187
5 Future Research Directions......Page 189
5.2 Recognition and Characterization Problems......Page 190
5.3 Optimization Problems......Page 191
5.4 Algorithm Engineering Problems......Page 192
References......Page 193
1 Introduction......Page 196
2 Models of Reconfiguration for Systems of Objects in the Plane......Page 198
2.1 The Sliding Model......Page 201
2.2 The Translation Model......Page 206
2.3 The Lifting Model......Page 209
2.4 Further Questions......Page 212
3 Modular and Reconfigurable Systems......Page 213
4 Reconfigurations in Graphs and Grids......Page 217
5 Conclusion......Page 219
References......Page 220
1 Introduction......Page 223
2.1 Rectangular Drawing......Page 225
2.2 Rectangular Dual......Page 226
2.3 An Algorithm for Rectangular Drawings......Page 228
3.1 Segment Contact Graphs......Page 231
3.1.1 Separating Decompositions and Segment Contact Representations......Page 233
3.2 Visibility Graphs......Page 236
3.2.1 Bipolar Orientations......Page 237
3.2.2 From a Bipolar Orientation to a Rectangular Dissection......Page 238
3.3 Bipolar Orientations and Separating Decompositions......Page 239
4.1 Squarings and Electricity......Page 241
4.2 Squarings and Separating Decompositions......Page 243
4.3 Trapezoidal Dissections and Markov Chains......Page 247
5 Square Duals......Page 251
5.1 Square Duals and Transversal Structures......Page 253
References......Page 256
1 Introduction and Preliminaries......Page 259
2 Upper Bound on Convex Obstacle Number of Outerplanar Graphs......Page 260
2.1 Constructing the BFS-Digraph and Its Properties......Page 261
2.2 5-Convex Obstacle Representation of the BFS-Digraph of a Connected Outerplanar Graph......Page 263
2.3 Adjusting the Representation for General Outerplanar Graphs......Page 266
3 Lower Bound on Disjoint Convex Obstacle Number of Outerplanar Graphs......Page 267
4 Convex Obstacle Number of Bipartite Permutation Graphs......Page 269
References......Page 271
1 Introduction......Page 273
2 Weak Hanani–Tutte for Monotone Drawings......Page 274
2.1 From x-Monotone to x-Bounded......Page 280
3 Strong Hanani–Tutte for Monotone Drawings......Page 282
4 Level-Planarity Testing......Page 287
4.1 Testing x-Monotonicity......Page 288
4.2 Testing Level-Planarity......Page 289
5 Monotone Crossing Numbers......Page 291
6 Future Directions......Page 292
References......Page 294
1 Introduction......Page 297
2 Relating Extremal Functions......Page 300
3 Geometric Graphs with No (2, 1)-Crossing Family......Page 303
4 Simple Topological Graphs with No (k, 1)-Crossing Family......Page 306
References......Page 309
1 Introduction......Page 312
2 The Size of ps-Flippable Edge Sets......Page 317
3.1 The Ratio Between the Number of Crossing-Free Straight-Edge Graphs and the Number of Triangulations......Page 321
3.2 The Number of Spanning Trees and Forests......Page 324
3.3 The Number of Crossing-Free Straight-Edge Graphs with a Bounded Number of Edges......Page 326
References......Page 331
1 Introduction......Page 334
2.1 From Perfect Matchings to Hamiltonian Cycles and Paths......Page 336
2.2 From Perfect Matchings to Encompassing Trees......Page 339
2.3 Looking for a Second Matching......Page 341
3 An Extreme Case: Augmenting Empty Graphs......Page 343
3.1 Plane Drawings of Specific Graphs and Classes of Graphs......Page 344
3.2 The Number of Embeddings......Page 345
3.3 Spanning Graphs with Desirable Properties......Page 347
4.1 Connectivity Augmentation......Page 350
4.2 Network Optimization Through Augmentation......Page 354
References......Page 356
1 Introduction......Page 362
2 Geometric Alternating Matchings......Page 363
3 Balanced Subdivisions......Page 365
4 Geometric Spanning Trees......Page 367
References......Page 376
1 Introduction......Page 377
2 Spanning Trees......Page 378
3 Paths, Cycles, and Beyond......Page 380
4 Matchings......Page 382
5 Ramsey Multiplicity......Page 385
References......Page 386
1 Introduction......Page 389
2 Definitions and Notations......Page 391
3.1 The Size of the Blockers......Page 392
3.2 The Blockers Are Caterpillars......Page 394
4 The Convex Case: Proof of Theorem 1.4......Page 397
5 The General Case: Proof of Theorem 1.3......Page 399
5.1 Blocking SSTs of Diameter at Most 3 Is Insufficient......Page 400
6 The Converse Direction......Page 401
References......Page 403
1 Introduction......Page 404
2 Preliminaries......Page 406
3 Clean Circle Graphs......Page 407
4 Chromatic Number of K4-Free Circle Graphs......Page 413
References......Page 419
1 Introduction......Page 420
3 Geometric Facts......Page 422
4 The Algorithm......Page 425
4.1 The Goal......Page 426
4.3 Methodology......Page 427
4.4 Initializing and Growing Configurations......Page 429
5 Results: Proof of Theorem 4......Page 430
6 Abstract Tightness......Page 431
7 Future Directions......Page 432
References......Page 433
1 Basic Definitions and Motivations......Page 434
2.1 The Case n = 2......Page 437
2.2 Other ``Small'' Dimensions......Page 438
2.3 Higher Dimensions......Page 439
2.4 Ideas of Lower Estimates in Small Dimensions......Page 440
2.5 Ideas of Lower Estimates in Higher Dimensions......Page 441
2.6 Ideas of Upper Estimates......Page 443
3.1 A General Definition......Page 444
3.2 The Chromatic Numbers of the Spaces (Qn,l2)......Page 445
3.3 The Chromatic Numbers of the Spaces (Rn,lq) , (Qn,lq)......Page 446
3.4.1 Finite Sets of Forbidden Distances......Page 448
3.4.2 Infinite Sequences of Forbidden Distances......Page 449
3.5 The Chromatic Numbers of Spheres......Page 450
4 High Girth/Small Clique Number and High Chromatic Number......Page 452
5 Random Distance Graphs Related to the Chromatic Number......Page 453
6.1 A Possible Way to Improve Lower Bounds for the Chromatic Numbers......Page 454
6.2 Independent Sets and Measurable Chromatic Numbers......Page 455
7 Conditional Results on the Chromatic Numbers......Page 456
8.2 Some General Results......Page 457
8.4 Counterexamples on Spheres of Small Radii......Page 458
8.6 Coming Back to Small Dimensions......Page 460
References......Page 461
1 Introduction......Page 466
1.1 The Existential Theory of the Real Numbers......Page 467
1.2 Stretchability and -Completeness......Page 468
2 Realizability of Graphs......Page 469
2.1 Graph Realizability......Page 470
2.3 Issues of Precision......Page 474
2.4 Plane Realizations and Matchstick Graphs......Page 475
3.1 Linkage Realizability......Page 476
3.2 Rigidity......Page 481
4 Open Questions......Page 484
References......Page 485
1 Introduction......Page 488
2 Proof of Theorem 1......Page 489
3 k-Distance Sets......Page 490
References......Page 491
1 Introduction......Page 493
2 Strongly Crossing Edges in the Plane......Page 495
2.1 Convex Geometric 3-Hypergraphs......Page 499
3 Disjoint Edges in 3-Space......Page 500
References......Page 501
1.1 Overview......Page 504
2 Asymptotics......Page 505
3 Extremal Configurations......Page 508
4 Stability......Page 509
5 Proof of Theorem C......Page 510
6 Proof of Theorem B......Page 517
References......Page 522
1 Introduction......Page 524
1.2 d-Representable Complexes......Page 525
1.3 What Is in the Survey?......Page 526
2 d-Collapsible and d-Leray Complexes......Page 527
3.1 Every Finite Simplicial Complex Is d-Representable for d Big Enough......Page 529
3.2 The Gap Between Representability and Collapsibility......Page 531
3.3 The Gap Between Collapsibility and Leray Number......Page 532
4.3 Leray Number......Page 533
5 Good Covers......Page 534
5.2 Good Covers Versus Collections of Convex Sets......Page 535
6.1 The Helly Theorem......Page 536
6.2 The Colorful Helly Theorem......Page 537
6.4 The (p,q) Theorem......Page 538
6.5 The Amenta Theorem......Page 539
References......Page 541
1 Introduction......Page 544
2.1 Heavy Paths......Page 547
2.2 Fast and Slow Walks......Page 548
2.3 Longer Forbidden Walks......Page 553
2.4 k-Flat Graphs......Page 556
3.1 Construction of 3-Locally Plane Graphs in PPTT......Page 558
3.2 Self-Intersecting Paths in Gd......Page 559
4 Discussion on Optimality of Thinning......Page 562
References......Page 564
1 Introduction......Page 566
3 Proof of Theorem......Page 567
References......Page 570
1 Introduction......Page 571
2.1 Simplicial Complexes......Page 577
2.2 Maps and Embeddings......Page 578
2.3 Homology and Cohomology......Page 580
2.4 Deleted Products and Obstructions......Page 582
2.6 Random Complexes and Collapsibility......Page 586
3.1 Higher-Dimensional Crossing Lemmas......Page 588
3.2 The Upper Bound Theorem and Beyond......Page 589
4 The Forbidden Minor Approach......Page 591
5.1 Subdivision and Topological Minors......Page 592
5.2 Deletions and Arbitrary Contractions......Page 594
5.3 Admissible Contractions According to Nevo......Page 595
5.4 Homological Minors......Page 597
6 Higher-Dimensional Expansion......Page 598
7 Partitions and Colorful Homological Minorsand Cominors......Page 600
7.1 Partitions and Colorful Chain Maps......Page 601
7.2 Cominors......Page 603
7.3 Minors in Expanding Complexes......Page 604
References......Page 606
Erratum
......Page 610