**Contemporary Mathematics**

Volume: 342;
2004;
283 pp;
Softcover

MSC: Primary 05;
Secondary 57; 90; 68

Print ISBN: 978-0-8218-3484-8

Product Code: CONM/342

List Price: $92.00

Individual Member Price: $73.60

**Electronic ISBN: 978-0-8218-7932-0
Product Code: CONM/342.E**

List Price: $92.00

Individual Member Price: $73.60

# Towards a Theory of Geometric Graphs

Share this page *Edited by *
*János Pach*

The early development of graph theory was heavily motivated and
influenced by topological and geometric themes, such as the Königsberg
Bridge Problem, Euler's Polyhedral Formula, or Kuratowski's characterization of
planar graphs. In 1936, when Dénes König 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 König, *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*.

#### Table of Contents

# Table of Contents

## Towards a Theory of Geometric Graphs

- Contents vii8 free
- Preface ix10 free
- On the complexity of the linkage reconfiguration problem 114 free
- Falconer conjecture, spherical averages and discrete analogs 1528
- Tunin-type extremal problems for convex geometric hypergraphs 2538
- The thrackle conjecture for K5 and K3,3 3548
- Three-dimensional grid drawings with sub-quadratic volume 5568
- On a coloring problem for the integer grid 6780
- Separating thickness from geometric thickness 7588
- Direction trees in centered polygons 87100
- Path coverings of two sets of points in the plane 99112
- Length of sums in a Minkowski space 113126
- A new entropy inequality for the Erdos distance problem 119132
- Coloring intersection graphs of geometric figures with a given clique number 127140
- Convex quadrilaterals and k-sets 139152
- Distance graphs and rigidity 149162
- A Ramsey property of planar graphs 169182
- A generalization of quasi-planarity 177190
- Geometric incidences 185198
- Large sets must have either a k-edge or a (k + 2)-edge 225238
- Topological graphs with no self-intersecting cycle of length 4 233246
- A problem on restricted sumsets 245258
- The gap between the crossing numbers and the convex crossing numbers 249262
- Distinct distances in high dimensional homogeneous sets 259272
- The biplanar crossing number of the random graph 269282
- The unit distance problem on spheres 273286
- Short proof for a theorem of Pach, Spencer, and T6th 281294

#### Readership

Graduate students and research mathematicians interested in discrete mathematics.