Author | Felsner, Stefan. author |
---|---|

Title | Geometric Graphs and Arrangements [electronic resource] : Some Chapters from Combinatorial Geometry / by Stefan Felsner |

Imprint | Wiesbaden : Vieweg+Teubner Verlag, 2004 |

Connect to | http://dx.doi.org/10.1007/978-3-322-80303-0 |

Descript | X, 170 p. online resource |

SUMMARY

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 partly very recent results from the intersection of geometry, graph theory and combinatorics

CONTENT

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โ{128}{153}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

Mathematics
Algebra
Geometry
Mathematics
Geometry
Algebra