Book contents
- Frontmatter
- Contents
- Preface
- The Rado Lecture
- The Invited Lectures
- Polynomials in Finite Geometries
- Applications of Combinatorial Designs to Communications, Cryptography, and Networking
- Random Walks on Combinatorial Objects
- Bose–Burton Type Theorems for Finite Projective, Affine and Polar Spaces
- Geometric Graph Theory
- Recent Excluded Minor Theorems for Graphs
- Parity, Cycle Space, and K4-Subdivisions in Graphs
Geometric Graph Theory
Published online by Cambridge University Press: 05 May 2013
- Frontmatter
- Contents
- Preface
- The Rado Lecture
- The Invited Lectures
- Polynomials in Finite Geometries
- Applications of Combinatorial Designs to Communications, Cryptography, and Networking
- Random Walks on Combinatorial Objects
- Bose–Burton Type Theorems for Finite Projective, Affine and Polar Spaces
- Geometric Graph Theory
- Recent Excluded Minor Theorems for Graphs
- Parity, Cycle Space, and K4-Subdivisions in Graphs
Summary
Summary A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straight-line segments. The study of geometric graphs is a fairly new discipline abounding in open problems, but it has already yielded some striking results that have proved to be instrumental for the solution of various problems in combinatorial and computational geometry. These include the k-set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. This paper surveys some Turán-type and Ramsey-type extremal problems for geometric graphs, and discusses their generalizations and applications.
Introduction, basic definitions
Let G be a finite graph with no loops or multiple edges, whose vertex set and edge set are denoted by V(G) and E(G), respectively. By a drawing of G we mean a representation of G in the plane such that each vertex is represented by a distinct point and each edge by a simple (non-self-intersecting) continuous arc connecting the corresponding two points. If it is clear that we are referring to a drawing, and not to the underlying “abstract” graph, these points and arcs will also be called vertices and edges, respectively.
Two edges (arcs) cross each other if they have an interior point in common. This point is called a crossing. A crossing p is called proper if in a small neighbourhood of p one edge passes from one side of the other edge to the other side.
- Type
- Chapter
- Information
- Surveys in Combinatorics, 1999 , pp. 167 - 200Publisher: Cambridge University PressPrint publication year: 1999
- 14
- Cited by