Some problems in topological graph theory

拓扑图论的几个问题

• 批准号: 1001230
• 负责人: Guoli Ding
• 金额: $ 19.17万
• 依托单位: Louisiana State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1001230&HistoricalAwards=false
• 关键词: Some; problems; topological; graph; theory

Topological graph theory studies how graphs can be drawn on surfaces in different ways. One of its fundamental problems is to determine for each surface S the set F of minimal graphs that have a cross no matter how they are drawn on S. It follows from the celebrated result of Robertson and Seymour on Wagner?s conjecture that F is finite for every surface S. However, nothing is known about the elements of F, except when S is the sphere or the projective plane. Over the past twenty years, many attempts were made by many researchers yet no new F is completely determined. The PI proposes a different approach to this problem. Results generated from this proposal could lead to a characterization of core members of each F, which would essentially determine F since other members of F are sporadic unimportant graphs.The goal of this project is to understand the behavior of topological graph parameters such as genus and crossing number when the graph is well connected and is big. To achieve this goal, it will be necessary to study the interactions between connectivity, genus, and the size of the graph. A good understanding of such interactions would bring significant insights to the entire topological graph theory. Since surface graphs are so fundamental, these results could have very strong theoretical (on graph structures) and practical (on graph algorithms) impact in many areas of graph theory.

拓扑图理论研究如何以不同的方式在表面上绘制图。它的基本问题之一是为每个表面确定最小图的集合，无论它们是如何在S上绘制的，它们都取决于Robertson和Seymour对Wagner的著名结果，wagner的猜想是f是有限的。但是，除了何时是F，除了何时是F的元素，除了何时是F，除了何时或投影范围或投影范围。在过去的二十年中，许多研究人员进行了许多尝试，但没有完全确定新的F。 PI提出了针对此问题的不同方法。该提案产生的结果可能会导致每个F的核心成员的表征，这实际上将决定F，因为F的其他成员是零星的图形。该项目的目的是了解拓扑图参数（例如属）的行为，例如属和交叉数，当图形良好地连接并且连接且大。为了实现这一目标，有必要研究连通性，属和图形大小之间的相互作用。对这种互动的良好理解将为整个拓扑图理论带来重要的见解。由于表面图是如此基本，因此这些结果可能具有非常强大的理论（在图结构上）和实用性（在图算法上）在图理论的许多领域中的影响。