Graph Theory and Geometry

点击翻译按钮获取中文摘要

This research project is devoted to investigating (a) crossing numbers of graphs and their relationships to other graph properties, and(b) extremal problems for geometric graphs.The crossing number of a graph is usually defined as the minimum number of edge crossings or the minimum number of crossing pairs of edges in a drawing of the graph in the plane. These two definitions are widely believed to be equivalent. However, there is no strong evidence that this would be the case. The investigator's goal is to clarify this question and to give new estimates for crossing numbers of graphs satisfying some special conditions. Some similar estimates turned out to be applicable to a number of classical open problems in discrete geometry, including the problem of bounding from above (resp. from below) the number of unit (resp. distinct) distances determined by a point set, the k-set problem of Erdos and Lovasz etc, and they are also related to some deep questions in algebraic geometry. Some existing bounds on crossing numbers have direct applications in the theory of geometric graphs (i.e., graphs drawn by straight-line segments), the other main subject of the present proposal. The investigator plans to develop some general theories for geometric graphs, analogous to the rich and fruitful fields of Extremal Graph Theory and Ramsey Theory for abstract graphs. Many basic problems in robotics and in computer graphics lead to deep mathematical questions about arrangements of segments in the plane. A system of segments (`edges') connecting n points in the plane is called a geometric graph on n vertices. Traditional graph theory is often incapable of providing satisfactory answers to questions on geometric graphs arising in practical applications. To address these problems, the investigator and his colleagues have developed some new techniques combining combinatorial and topological ideas. As a by-product, they obtained some surprising results to estimate the crossing number of a graph (network), a parameter known to be intimately related to the minimum chip area required for its VLSI layout. The aim of the proposed research is to better understand and to improve these estimates by utilizing more involved topological tools. This may have many important applications in discrete and computational geometry and in the theory and practice of graph drawing.