Research in 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.