Thirty Essays on Geometric Graph TheoryJános Pach In many applications of graph theory, graphs are regarded as geometric objects drawn in the plane or in some other surface. The traditional methods of "abstract" graph theory are often incapable of providing satisfactory answers to questions arising in such applications. In the past couple of decades, many powerful new combinatorial and topological techniques have been developed to tackle these problems. Today geometric graph theory is a burgeoning field with many striking results and appealing open questions. This contributed volume contains thirty original survey and research papers on important recent developments in geometric graph theory. The contributions were thoroughly reviewed and written by excellent researchers in this field. |
Contents
| 1 | |
| 5 | |
| 19 | |
Thirty Essays on Geometric Graph Theory | 31 |
Constrained TriConnected Planar Straight Line Graphs | 49 |
Topological Hypergraphs | 71 |
On EdgeDisjoint Empty Triangles of Point Sets | 83 |
Universal Sets for StraightLine Embeddings of Bicolored Graphs | 101 |
Plane Geometric Graph Augmentation A Generic Perspective | 327 |
Discrete Geometry on Red and Blue Points in the Plane Lattice | 355 |
RamseyType Problems for Geometric Graphs | 370 |
Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs | 383 |
Coloring Clean and K4Free Circle Graphs | 399 |
Counting Large Distances in Convex Polygons A Computational Approach | 415 |
Coloring Distance Graphs and Graphs of Diameters | 429 |
Realizability of Graphs and Linkages | 461 |
Drawing Trees Outerplanar Graphs SeriesParallel Graphs and Planar Graphs in a Small Area | 120 |
The CrossingAngle Resolution in Graph Drawing | 167 |
Mover Problems | 185 |
Rectangle and Square Representationsof Planar Graphs | 212 |
Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs | 249 |
HananiTutte Monotone Drawings and LevelPlanarity | 263 |
On Disjoint Crossing Families in Geometric Graphs | 288 |
Counting Plane Graphs Flippability and Its Applications | 303 |
Equilateral Sets in pd | 483 |
A Note on Geometric 3Hypergraphs | 488 |
Favorite Distances in High Dimensions | 499 |
Intersection Patterns of Convex Sets via Simplicial Complexes A Survey | 521 |
Construction of Locally Plane Graphs with Many Edges | 541 |
A Better Bound for the PairCrossing Number | 563 |
Minors Embeddability and Extremal Problems for Hypergraphs | 568 |
Other editions - View all
Common terms and phrases
2-color 3-connected algorithm arbitrary assume augmentation bipartite graph boundary chromatic number color class combinatorial Computational Geometry configuration conjecture connected consider construction contains convex hull convex position convex sets cr(Kn crossing edges crossing number crossing-free curve cycle d-collapsible define denote Discr Discrete disjoint disks distance graphs edge coloring embedding endpoints Erd˝os Euclidean finite Geom Geometric Graph Theory Graph Drawing graph G implies induction integer interior intersection intersection graph interval least Lemma Let G linear lower bound Math maximum minimum number noncrossing NP-hard number of edges O(nlogn obstacle obtain Open Problem outerplanar graphs Pach pair pairwise path planar drawing planar graphs plane point set polygon polynomial proof of Theorem proved PSLG RAC drawing realization reconfiguration rectangles rectangular representation result Sect series-parallel graphs simplicial complex spanning trees Springer Springer Science+Business Media straight-line drawings subgraph subset T´oth triangles upper bound vertex vertex set vertices x-monotone