Towards a theory of geometric graphs
著者
書誌事項
Towards a theory of geometric graphs
（Contemporary mathematics, 342）
American Mathematical Society, c2004
大学図書館所蔵 件 / 全47件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references
内容説明・目次
内容説明
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.
目次
On the complexity of the linkage reconfiguration problem by H. Alt, C. Knauer, G. Rote, and S. Whitesides Falconer conjecture, spherical averages and discrete analogs by G. Arutyunyants and A. Iosevich Turan-type extremal problems for convex geometric hypergraphs by P. Brass The thrackle conjecture for $K_5$ and $K_{3,3}$ by G. Cairns, M. McIntyre, and Y. Nikolayevsky Three-dimensional grid drawings with sub-quadratic volume by V. Dujmovic and D. R. Wood On a coloring problem for the integer grid by A. Dumitrescu and R. Radoicic Separating thickness from geometric thickness by D. Eppstein Direction trees in centered polygons by R. E. Jamison Path coverings of two sets of points in the plane by A. Kaneko, M. Kano, and K. Suzuki Length of sums in a Minkowski space by G. O. H. Katona, R. Mayer, and W. A. Woyczynski A new entropy inequality for the Erdos distance problem by N. H. Katz and G. Tardos Coloring intersection graphs of geometric figures with a given clique number by A. Kostochka Convex quadrilaterals and $k$-sets by L. Lovasz, K. Vesztergombi, U. Wagner, and E. Welzl Distance graphs and rigidity by H. Maehara A Ramsey property of planar graphs by J. Nesetril, J. Solymosi, and P. Valtr A generalization of quasi-planarity by J. Pach, R. Radoicic, and G. Toth Geometric incidences by J. Pach and M. Sharir Large sets must have either a $k$-edge or a $(k+2)$-edge by M. A. Perles and R. Pinchasi Topological graphs with no self-intersecting cycle of length 4 by R. Pinchasi and R. Radoicic A problem on restricted sumsets by I. Z. Ruzsa The gap between crossing numbers and convex crossing numbers by F. Shahrokhi, O. Sykora, L. A. Szekely, and I. Vrto Distinct distances in high dimensional homogeneous sets by J. Solymosi and V. Vu The biplanar crossing number of the random graph by J. Spencer The unit distance problem on spheres by K. J. Swanepoel and P. Valtr Short proof for a theorem of Pach, Spencer, and Toth by L. Szekely.
「Nielsen BookData」 より