Research in Structural Graph Theory

结构图论研究

• 批准号: 9970514
• 负责人: Robin Thomas
• 金额: $ 8.79万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9970514&HistoricalAwards=false
• 关键词: Research; Structural; Graph; Theory

9970514The investigator conducts and supervises research in graph theory with emphasis on structural characterizations of various properties of graphs, and develops efficient practical algorithms based on this research. The major areas of interest are (i) Tutte's conjecture, Hadwiger's conjecture, and spatial embeddings of graphs and applications, (ii) Pfaffian orientations of graphs, (iii) Negami's planar cover conjecture, (iv) excluded minor theorems and tools to prove them (splitter theorems), (v) a theory of reducibility for the double cycle cover conjecture, and possible applications to the Four Color Theorem.Graph theory is a relatively young field that has applications in telecommunications, transportation, production, warehousing, storage allocation and many other applied areas. It deals with problems that are discrete in nature, such as how to optimally build a telephone network at the lowest possible cost. The project studies structural aspects of graph theory from a theoretical point of view, with the aim of converting theoretical results into fast and efficient algorithms. An example of the investigator's prior result is his solution (with Robertson and Seymour) of the `even directed cycle problem', a computer science question that has been open for the last quarter of a century, and has applications in mathematical physics, computer science and economics.

9970514研究者进行和监督图论研究，重点是图的各种属性的结构表征，并基于该研究开发高效的实用算法。 主要感兴趣的领域是（i）图特猜想、哈德维格猜想以及图的空间嵌入和应用，（ii）图的普法夫方向，（iii）Negami的平面覆盖猜想，（iv）排除次要定理和证明它们的工具（分裂定理），（v）双环覆盖猜想的可约性理论以及可能的应用 图论是一个相对年轻的领域，在电信、交通、生产、仓储、存储分配和许多其他应用领域都有应用。 它处理本质上离散的问题，例如如何以尽可能低的成本优化地构建电话网络。 该项目从理论角度研究图论的结构方面，旨在将理论结果转化为快速高效的算法。 研究者先前结果的一个例子是他（与 Robertson 和 Seymour 一起）对“偶向循环问题”的解决方案，这是一个在过去四分之一个世纪里一直开放的计算机科学问题，并且在数学物理、计算机科学和经济学中都有应用。