Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry / Edition 1

by Stefan Felsner

Overview

Among the intuitively appealing aspects of graph theory is its close connection to drawings and geometry. The development of computer technology has become a source of motivation to reconsider these connections, in particular geometric graphs are emerging as a new subfield of graph theory. Arrangements of points and lines are the objects for many challenging problems and surprising solutions in combinatorial geometry. The book is a collection of beautiful and mostly very recent results from the intersection of geometry, graph theory and combinatorics.

Product Details

ISBN-13:	9783528069728
Publisher:	Vieweg+Teubner Verlag
Publication date:	02/24/2004
Series:	Advanced Lectures in Mathematics
Edition description:	Softcover reprint of the original 1st ed. 2004
Pages:	170
Product dimensions:	6.69(w) x 9.45(h) x 0.02(d)

About the Author

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

Table of Contents

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.

Preface

Click to read or download

Editorial Reviews

"The book is written in a pleasant and clear style, with generous pictures and lucid explanations. [...] I recommend this splendid litte book für PhD students and researchers who work or wish to work in discrete geometry".
Combinatorics, Probability and Computing (Cambridge University Press), 15/2006

"[The author] has contributed an introduction to this fascinating and mathematically challenging - yet intuitively accessible - field."
Monatshefte für Mathematik, 02/2006

From the Publisher