Research in Structural Graph Theory

9970514研究者指导和指导图论的研究，重点是图的各种性质的结构表征，并在此基础上开发有效的实用算法。主要的兴趣领域是(i) Tutte猜想，Hadwiger猜想，以及图的空间嵌入和应用，（ii）图的Pfaffian取向，（iii） Negami的平面覆盖猜想，（iv）排除次要定理和证明它们的工具（分裂定理），(v)双循环覆盖猜想的可约性理论，以及四色定理的可能应用。图论是一个相对年轻的领域，在电信、运输、生产、仓储、仓储分配等许多应用领域都有应用。它处理本质上是离散的问题，例如如何以尽可能低的成本最优地建立一个电话网络。该项目从理论角度研究图论的结构方面，目的是将理论结果转化为快速有效的算法。研究人员先前成果的一个例子是他（与Robertson和Seymour）解决了“偶数有向循环问题”，这是一个在过去25年里一直开放的计算机科学问题，在数学物理、计算机科学和经济学中都有应用。

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.