Contemporary Mathematics 2004; 283 pp; softcover Volume: 342 ISBN10: 0821834843 ISBN13: 9780821834848 List Price: US$87 Member Price: US$69.60 Order Code: CONM/342
 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 straightline 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 straightline 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. Readership Graduate students and research mathematicians interested in discrete mathematics. Table of Contents  H. Alt, C. Knauer, G. Rote, and S. Whitesides  On the complexity of the linkage reconfiguration problem
 G. Arutyunyants and A. Iosevich  Falconer conjecture, spherical averages and discrete analogs
 P. Brass  Turántype extremal problems for convex geometric hypergraphs
 G. Cairns, M. McIntyre, and Y. Nikolayevsky  The thrackle conjecture for \(K_5\) and \(K_{3,3}\)
 V. Dujmović and D. R. Wood  Threedimensional grid drawings with subquadratic volume
 A. Dumitrescu and R. Radoičić  On a coloring problem for the integer grid
 D. Eppstein  Separating thickness from geometric thickness
 R. E. Jamison  Direction trees in centered polygons
 A. Kaneko, M. Kano, and K. Suzuki  Path coverings of two sets of points in the plane
 G. O. H. Katona, R. Mayer, and W. A. Woyczynski  Length of sums in a Minkowski space
 N. H. Katz and G. Tardos  A new entropy inequality for the Erdős distance problem
 A. Kostochka  Coloring intersection graphs of geometric figures with a given clique number
 L. Lovász, K. Vesztergombi, U. Wagner, and E. Welzl  Convex quadrilaterals and \(k\)sets
 H. Maehara  Distance graphs and rigidity
 J. Nešetřil, J. Solymosi, and P. Valtr  A Ramsey property of planar graphs
 J. Pach, R. Radoičić, and G. Tóth  A generalization of quasiplanarity
 J. Pach and M. Sharir  Geometric incidences
 M. A. Perles and R. Pinchasi  Large sets must have either a \(k\)edge or a \((k+2)\)edge
 R. Pinchasi and R. Radoičić  Topological graphs with no selfintersecting cycle of length 4
 I. Z. Ruzsa  A problem on restricted sumsets
 F. Shahrokhi, O. Sýkora, L. A. Székely, and I. Vrťo  The gap between crossing numbers and convex crossing numbers
 J. Solymosi and V. Vu  Distinct distances in high dimensional homogeneous sets
 J. Spencer  The biplanar crossing number of the random graph
 K. J. Swanepoel and P. Valtr  The unit distance problem on spheres
 L. Székely  Short proof for a theorem of Pach, Spencer, and Tóth
