Coverpage

Geometric Graphs and Arrangements

Stefan Felsner

Vieweg Verlag
Spring 2004. 170 pages.
ISBN:3-528-06972-4

The book at Vieweg (Springer)
After more than 15 years I have decided to publish this e-version of the book: [gga-book.pdf]
(This is not a copy of the version published by Vieweg. In fact the typos and errors mentioned in the errata are corrected in this version.)

There is a simpler proof for the implication (3 => 1) from Theorem 8.9. The new proof widely follows the approach taken by A.Frank and L.Szegö in [93]. [theorem8.9.pdf]

About the book

The questions posed and partly answered in this book are from the intersection of graph theory and discrete geometry. We discuss some graph theory with a geometric flavor and some combinatorial geometry of the plane. We don't claim to give a thorough introduction into the field. Instead the problems, ideas and results of each chapter are of a special character and beauty. The chapters are usable as stand alone surveys. In the combination, however, they should supplement each other to form an interesting and appealing whole.

Feedback

There will be something wrong. You may find errors of different nature. I may inadvertently not have given proper credit for some contribution. You may know of new work or have additional comments. In all these cases:
Please let me know. Link to errata

Contents

  1. Geometric Graphs: Turan Type Problems
    1. What is a Geometric Graph?
    2. Fundamental Concepts in Graph Theory
    3. Planar Graphs
    4. Outerplanar Graphs and Convex Geometric Graphs
    5. Geometric Graphs without (k+1)-Pairwise Disjoint Edges
    6. Geometric Graphs without Parallel Edges
    7. Notes and References
  2. Schnyder Woods or How to Draw a Planar Graph
    1. Schnyder Labelings and Woods
    2. Regions and Coordinates
    3. Geodesic Embeddings of Planar Graphs
    4. Dual Schnyder Woods
    5. Order Dimension of 3-Polytopes
    6. Existence of Schnyder Labelings
    7. Notes and References
  3. Topological Graphs: Crossing Lemma and Applications
    1. Bounds for the Crossing Number
    2. Improving the Crossing Constant
    3. Crossing Numbers and Incidence Problems
    4. Notes and References
  4. k-Sets and k-Facets
    1. k-Sets in the Plane
    2. Beyond the Plane
    3. The Rectilinear Crossing Number of K_n
    4. Notes and References
  5. Combinatorial Problems for Configurations of Points and Lines
    1. Arrangements, Planes, Duality
    2. Sylvester's Problem
    3. How many Lines are Spanned by n Points?
    4. Triangles in Arrangements
    5. Notes and References
  6. Combinatorial Representations of Arrangements of Pseudolines
    1. Marked Arrangements and Sweeps
    2. Allowable Sequences and Wiring Diagrams
    3. Local Sequences
    4. Zonotopal Tilings
    5. Triangle Signs
    6. Signotopes and their Orders
    7. Notes and References
  7. Triangulations and Flips
    1. Degrees in the Flip-Graph
    2. Delaunay Triangulations
    3. Regular Triangulations and Secondary Polytopes
    4. The Associahedron and Catalan Families
    5. The Diameter of G_n and Hyperbolic Geometry
    6. Notes and References
  8. Rigidity and Pseudotriangulations
    1. Rigidity, Motion and Stress
    2. Pseudotriangles and Pseudotriangulations
    3. Expansive Motions
    4. The Polytope of Pointed Pseudotriangulations
    5. Expansive Motions and Straightening Linkages
    6. Notes and References
Feb. 2004