Towards a Theory of Geometric Graphs

Front Cover
American Mathematical Soc., 2004 - Mathematics - 283 pages
The 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.


On the complexity of the linkage reconfiguration problem
Falconer conjecture spherical averages and discrete analogs
Tunintype extremal problems for convex geometric hypergraphs
The thrackle conjecture for K5 and K33
Threedimensional grid drawings with subquadratic volume
On a coloring problem for the integer grid
Separating thickness from geometric thickness
Direction trees in centered polygons
Distance graphs and rigidity
A Ramsey property of planar graphs
A generalization of quasiplanarity
Geometric incidences
Large sets must have either a kedge or a k + 2edge
Topological graphs with no selfintersecting cycle of length 4
A problem on restricted sumsets
The gap between the crossing numbers and the convex crossing numbers

Path coverings of two sets of points in the plane
Length of sums in a Minkowski space
A new entropy inequality for the Erdos distance problem
Coloring intersection graphs of geometric figures with a given clique number
Convex quadrilaterals and ksets
Distinct distances in high dimensional homogeneous sets
The biplanar crossing number of the random graph
The unit distance problem on spheres
Short proof for a theorem of Pach Spencer and T6th

Other editions - View all

Common terms and phrases

About the author (2004)

About the authors JANOS PACH is Professor of Computer Science at City College of New York and Senior Research Fellow at the Mathematical Institute of the Hungarian Academy of Sciences. He received his PhD in mathematics from Eotvos University, Budapest, in 1980 and has had visiting positions at various universities, including the University College of London, McGill University, the Courant Institute of New York University, and Tel Aviv University. He serves on the editorial boards of three mathematical and computer science journals and has been an invited speaker at many conferences. He has published more than one hundred research papers, mostly in discrete and computational geometry and in combinatorics. He received the Lester R. Ford Award in 1990 and the Renyi Prize in 1993. PANKAJ K. AGARWAL is Associate Professor in the Computer Science Department of Duke University. He received his PhD in computer science from the Courant Institute of Mathematical Sciences, New York University, in 1989. He is the author of Intersection and Decomposition Algorithms for Planar Arrangements, and a coauthor of Davenport--Schinzel Sequences and Their Geometric Applications. He has published several research papers and has given talks at many conferences. He was awarded the National Young Investigator Award in 1992.

Bibliographic information