## Towards a Theory of Geometric GraphsThe early development of graph theory was heavily motivated and influenced by topological and geometric themes, such as the Konigsberg Bridge Problem, Euler's Polyhedral Formula, or Kuratowski's characterization of planar graphs. In 1936, when Denes Konig published his classical ""Theory of Finite and Infinite Graphs"", the first book ever written on the subject, he stressed this connection by adding the subtitle Combinatorial Topology of Systems of Segments. He wanted to emphasize that the subject of his investigations was very concrete: planar figures consisting of points connected by straight-line segments. However, in the second half of the twentieth century, graph theoretical research took an interesting turn. In the most popular and most rapidly growing areas (the theory of random graphs, Ramsey theory, extremal graph theory, algebraic graph theory, etc.), graphs were considered as abstract binary relations rather than geometric objects.Many of the powerful techniques developed in these fields have been successfully applied in other areas of mathematics. However, the same methods were often incapable of providing satisfactory answers to questions arising in geometric applications. In the spirit of Konig, geometric graph theory focuses on combinatorial and geometric properties of graphs drawn in the plane by straight-line edges (or more generally, by edges represented by simple Jordan arcs). It is an emerging discipline that abounds in open problems, but it has already yielded some striking results which have proved instrumental in the solution of several basic problems in combinatorial and computational geometry. The present volume is a careful selection of 25 invited and thoroughly refereed papers, reporting about important recent discoveries on the way Towards a Theory of Geometric Graphs. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Falconer conjecture spherical averages and discrete analogs | 15 |

Tunintype extremal problems for convex geometric hypergraphs | 25 |

The thrackle conjecture for K5 and K33 | 35 |

Threedimensional grid drawings with subquadratic volume | 55 |

On a coloring problem for the integer grid | 67 |

Separating thickness from geometric thickness | 75 |

Direction trees in centered polygons | 87 |

Distance graphs and rigidity | 149 |

A Ramsey property of planar graphs | 169 |

A generalization of quasiplanarity | 177 |

Geometric incidences | 185 |

Large sets must have either a kedge or a k + 2edge | 225 |

Topological graphs with no selfintersecting cycle of length 4 | 233 |

A problem on restricted sumsets | 245 |

The gap between the crossing numbers and the convex crossing numbers | 249 |

Path coverings of two sets of points in the plane | 99 |

Length of sums in a Minkowski space | 113 |

A new entropy inequality for the Erdos distance problem | 119 |

Coloring intersection graphs of geometric figures with a given clique number | 127 |

Convex quadrilaterals and ksets | 139 |

Distinct distances in high dimensional homogeneous sets | 259 |

The biplanar crossing number of the random graph | 269 |

The unit distance problem on spheres | 273 |

Short proof for a theorem of Pach Spencer and T6th | 281 |

### Other editions - View all

### Common terms and phrases

4-cycles Aronov assume block blue points chromatic number circles circular sequences collinear color combinatorial complete bipartite graph complete graph Computational Geometry configuration conjecture consider construction contains conv(R1 convex geometric hypergraph cşq cşq cşq Crossing Lemma crossing number curves defined denote direction tree Discrete Comput Discrete Math distinct distances elements Erdös Figure finite Geom geometric graph geometric thickness graph drawing graph G grid Hausdorff dimension Hence hypergraph integer intersection graphs label least left(l Lemma lower bound Maehara Mathematics Subject Classification minimum number Minkowski space number of edges number of incidences ş ş ş obtain Pach pairs partition permutation planar graph plane point set polygonal position problem proof of Theorem proved R U B red points result rigid segments Sharir singletons subgraph subset Szemerédi-Trotter theorem thrackle topological graph Tóth triangles tripletons unit-distance graph upper bound vertex vertices