Towards a Theory of Geometric Graphs

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

Contents

On the complexity of the linkage reconfiguration problem
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
Copyright

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