eBook ISBN:  9780821879320 
Product Code:  CONM/342.E 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 
eBook ISBN:  9780821879320 
Product Code:  CONM/342.E 
List Price:  $125.00 
MAA Member Price:  $112.50 
AMS Member Price:  $100.00 

Book DetailsContemporary MathematicsVolume: 342; 2004; 283 ppMSC: Primary 05; Secondary 57; 90; 68
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.
ReadershipGraduate students and research mathematicians interested in discrete mathematics.

Table of Contents

Articles

Helmut Alt, Christian Knauer, Günter Rote and Sue Whitesides — On the complexity of the linkage reconfiguration problem [ MR 2065248 ]

G. Arutyunyants and A. Iosevich — Falconer conjecture, spherical averages and discrete analogs [ MR 2065249 ]

Peter Brass — Turántype extremal problems for convex geometric hypergraphs [ MR 2065250 ]

Grant Cairns, Margaret McIntyre and Yury Nikolayevsky — The Thrackle conjecture for $K_5$ and $K_{3,3}$ [ MR 2065251 ]

Vida Dujmović and David R. Wood — Threedimensional grid drawings with subquadratic volume [ MR 2065252 ]

Adrian Dumitrescu and Radoš Radoičić — On a coloring problem for the integer grid [ MR 2065253 ]

David Eppstein — Separating thickness from geometric thickness [ MR 2065254 ]

Robert E. Jamison — Direction trees in centered polygons [ MR 2065255 ]

Atsushi Kaneko, M. Kano and Kazuhiro Suzuki — Path coverings of two sets of points in the plane [ MR 2065256 ]

Gyula O. H. Katona, Richard Mayer and Wojbor A. Woyczynski — Length of sums in a Minkowski space [ MR 2065257 ]

Nets Hawk Katz and Gábor Tardos — A new entropy inequality for the Erdős distance problem [ MR 2065258 ]

Alexandr Kostochka — Coloring intersection graphs of geometric figures with a given clique number [ MR 2065259 ]

László Lovász, Katalin Vesztergombi, Uli Wagner and Emo Welzl — Convex quadrilaterals and $k$sets [ MR 2065260 ]

Hiroshi Maehara — Distance graphs and rigidity [ MR 2065261 ]

Jaroslav Nešetřil, József Solymosi and Pavel Valtr — A Ramsey property of planar graphs [ MR 2065262 ]

János Pach, Radoš Radoičić and Géza Tóth — A generalization of quasiplanarity [ MR 2065263 ]

János Pach and Micha Sharir — Geometric incidences [ MR 2065264 ]

Micha A. Perles and Rom Pinchasi — Large sets must have either a $k$edge or a $(k+2)$edge [ MR 2065265 ]

Rom Pinchasi and Radoš Radoičić — Topological graphs with no selfintersecting cycle of length 4 [ MR 2065266 ]

Imre Z. Ruzsa — A problem on restricted sumsets [ MR 2065267 ]

F. Shahrokhi, O. Sýkora, L. A. Székely and I. Vrťo — The gap between crossing numbers and convex crossing numbers [ MR 2065268 ]

József Solymosi and Van Vu — Distinct distances in high dimensional homogeneous sets [ MR 2065269 ]

Joel Spencer — The biplanar crossing number of the random graph [ MR 2065270 ]

Konrad J. Swanepoel and Pavel Valtr — The unit distance problem on spheres [ MR 2065271 ]

László A. Székely — Short proof for a theorem of Pach, Spencer, and Tóth [ MR 2065272 ]


RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
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.
Graduate students and research mathematicians interested in discrete mathematics.

Articles

Helmut Alt, Christian Knauer, Günter Rote and Sue Whitesides — On the complexity of the linkage reconfiguration problem [ MR 2065248 ]

G. Arutyunyants and A. Iosevich — Falconer conjecture, spherical averages and discrete analogs [ MR 2065249 ]

Peter Brass — Turántype extremal problems for convex geometric hypergraphs [ MR 2065250 ]

Grant Cairns, Margaret McIntyre and Yury Nikolayevsky — The Thrackle conjecture for $K_5$ and $K_{3,3}$ [ MR 2065251 ]

Vida Dujmović and David R. Wood — Threedimensional grid drawings with subquadratic volume [ MR 2065252 ]

Adrian Dumitrescu and Radoš Radoičić — On a coloring problem for the integer grid [ MR 2065253 ]

David Eppstein — Separating thickness from geometric thickness [ MR 2065254 ]

Robert E. Jamison — Direction trees in centered polygons [ MR 2065255 ]

Atsushi Kaneko, M. Kano and Kazuhiro Suzuki — Path coverings of two sets of points in the plane [ MR 2065256 ]

Gyula O. H. Katona, Richard Mayer and Wojbor A. Woyczynski — Length of sums in a Minkowski space [ MR 2065257 ]

Nets Hawk Katz and Gábor Tardos — A new entropy inequality for the Erdős distance problem [ MR 2065258 ]

Alexandr Kostochka — Coloring intersection graphs of geometric figures with a given clique number [ MR 2065259 ]

László Lovász, Katalin Vesztergombi, Uli Wagner and Emo Welzl — Convex quadrilaterals and $k$sets [ MR 2065260 ]

Hiroshi Maehara — Distance graphs and rigidity [ MR 2065261 ]

Jaroslav Nešetřil, József Solymosi and Pavel Valtr — A Ramsey property of planar graphs [ MR 2065262 ]

János Pach, Radoš Radoičić and Géza Tóth — A generalization of quasiplanarity [ MR 2065263 ]

János Pach and Micha Sharir — Geometric incidences [ MR 2065264 ]

Micha A. Perles and Rom Pinchasi — Large sets must have either a $k$edge or a $(k+2)$edge [ MR 2065265 ]

Rom Pinchasi and Radoš Radoičić — Topological graphs with no selfintersecting cycle of length 4 [ MR 2065266 ]

Imre Z. Ruzsa — A problem on restricted sumsets [ MR 2065267 ]

F. Shahrokhi, O. Sýkora, L. A. Székely and I. Vrťo — The gap between crossing numbers and convex crossing numbers [ MR 2065268 ]

József Solymosi and Van Vu — Distinct distances in high dimensional homogeneous sets [ MR 2065269 ]

Joel Spencer — The biplanar crossing number of the random graph [ MR 2065270 ]

Konrad J. Swanepoel and Pavel Valtr — The unit distance problem on spheres [ MR 2065271 ]

László A. Székely — Short proof for a theorem of Pach, Spencer, and Tóth [ MR 2065272 ]