Geometric Graphs and Arrangements

Die Graphentheorie gewinnt einen Teil ihres Reizes aus ihrer Anschaulichkeit, also aus Bezügen zu Visualisierung und Geometrie. Die Graphikfähigkeit moderner Computer hat neue Anstöße zur Untersuchung dieser Bezüge geliefert, insbesondere Geometrische Graphen sind zu einem aktuellen Forschungsgegenstand geworden. Arrangements von Geraden und Punkten sind die Objekte einer Fülle von oftmals schwierigen Problemen und überraschenden Lösungen. Dieses Buch, in englischer Sprache, stellt faszinierende und teils sehr aktuelle Themen aus dem Grenzbereich von Graphentheorie, Geometrie und Kombinatorik vor.

Graph theory, geometry and combinatorics brought together to generate a wealth of beauty in ideas

Préface
Graph theory, geometry and combinatorics brought together to generate a wealth of beauty in ideas

Auteur
Prof. Dr. Stefan Felsner, Institut für Mathematik, Technische Universität Berlin, Germany.

Contenu
1 Geometric Graphs: Turán Problems.- 1.1 What is a Geometric Graph?.- 1.2 Fundamental Concepts in Graph Theory.- 1.3 Planar Graphs.- 1.4 Outerplanar Graphs and Convex Geometric Graphs.- 1.5 Geometric Graphs without (k + 1)-Pairwise Disjoint Edges.- 1.6 Geometric Graphs without Parallel Edges.- 1.7 Notes and References.- 2 Schnyder Woods or How to Draw a Planar Graph?.- 2.1 Schnyder Labelings and Woods.- 2.2 Regions and Coordinates.- 2.3 Geodesic Embeddings of Planar Graphs.- 2.4 Dual Schnyder Woods.- 2.5 Order Dimension of 3-Polytopes.- 2.6 Existence of Schnyder Labelings.- 2.7 Notes and References.- 3 Topological Graphs: Crossing Lemma and Applications.- 3.1 Crossing Numbers.- 3.2 Bounds for the Crossing Number.- 3.3 Improving the Crossing Constant.- 3.4 Crossing Numbers and Incidence Problems.- 3.5 Notes and References.- 4 k-Sets and k-Facets.- 4.1 k-Sets in the Plane.- 4.2 Beyond the Plane.- 4.3 The Rectilinear Crossing Number of Kn.- 4.4 Notes and References.- 5 Combinatorial Problems for Sets of Points and Lines.- 5.1 Arrangements, Planes, Duality.- 5.2 Sylvester's Problem.- 5.3 How many Lines are Spanned by n Points?.- 5.4 Triangles in Arrangements.- 5.5 Notes and References.- 6 Combinatorial Representations of Arrangements of Pseudolines.- 6.1 Marked Arrangements and Sweeps.- 6.2 Allowable Sequences and Wiring Diagrams.- 6.3 Local Sequences.- 6.4 Zonotopal Tilings.- 6.5 Triangle Signs.- 6.6 Signotopes and their Orders.- 6.7 Notes and References.- 7 Triangulations and Flips.- 7.1 Degrees in the Flip-Graph.- 7.2 Delaunay Triangulations.- 7.3 Regular Triangulations and Secondary Polytopes.- 7.4 The Associahedron and Catalan families.- 7.5 The Diameter of Gn and Hyperbolic Geometry.- 7.6 Notes and References.- 8 Rigidity and Pseudotriangulations.- 8.1 Rigidity,Motion and Stress.- 8.2 Pseudotriangles and Pseudotriangulations.- 8.3 Expansive Motions.- 8.4 The Polyhedron of of Pointed Pseudotriangulations.- 8.5 Expansive Motions and Straightening Linkages.- 8.6 Notes and References.