Graph Structure Theory and Applications to Algorithms

这个提议的中心主题是图结构理论及其在算法中的应用。 更具体地说，PI将研究与图的子包含有关的图的结构，以及它在有向图中较少被理解的对应部分。 PI最近的工作表明，应该可以在图次项理论的关键结果中获得更好的边界。 这种改进的界限将直接应用于设计有效的算法。 对于有向图的主要问题是所谓的圆柱形网格猜想是否正确，以及目前已知的有界树宽有向图的算法是否可以改进为固定参数易处理。 圆柱网格猜想似乎既是一个基本的数学问题，也是一个可能解开许多算法应用的问题。 PI还提出了一种新的方法来攻击Negami的平面覆盖猜想，这个问题从1988年开始就受到了相当多的关注。 最初的动机来自计算机科学，其思想是如果一个图G覆盖一个图H，那么H的连接可以由G模拟，然而G可能具有更简单的结构。Negami猜想刻画了具有平面覆盖的图的特征。这项工作福尔斯属于图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于对网络进行建模，例如电话网络，交通网络或互联网。在研究这种网络的过程中会出现各种问题，而本建议关注的是结构性问题。 为什么有些网络具有某些特定的理想属性，而另一些则没有？一个令人满意的答案可以有许多应用，从更好地理解底层结构，到设计有效的算法，再到实际计算。 例如，PI之前回答的一个这样的问题解决了1913年的格鲁吉亚波利亚问题，它也解决了一个困扰理论计算机科学家四分之一个世纪世纪的不同问题，并在经济学中有应用。

The central theme of this proposal is graph structure theory and its applications to algorithms. More specifically, the PI will investigate the structure of graphs pertaining to the graph minor inclusion and its much less understood counterpart for directed graphs. Recent work of the PI suggests that it should be possible to obtain much improved bounds in key results of the Graph Minors theory. Such improved bounds will have immediate applications to the design of efficient algorithms. For directed graphs the main questions are whether the so-called cylindrical grid conjecture is true, and whether the algorithms for digraphs of bounded tree-width that are currently known can be improved to become fixed parameter tractable. The cylindrical grid conjecture seems to be both a fundamental mathematical problem as well as one that could potentially unlock many algorithmic applications. The PI also proposes a new approach to attacking Negami's planar cover conjecture, a problem from 1988 that has received a considerable amount of attention. The original motivation came from computer science, the idea being that if a graph G covers a graph H, then the connections of H can be simulated by G, and yet G could potentially have a simpler structure. Negami's conjecture would characterize graphs that have a planar cover.This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Various problems arise in the study of such networks, and this proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? A satisfactory answer can have many applications, ranging from better understanding of the underlying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered earlier by the PI settles a question of Georgia Polya from 1913, it also solves a different problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics.