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.

拓扑图论研究如何以不同的方式在表面上绘制图形。它的一个基本问题是确定每个曲面的极小图的集合F，这些极小图无论如何画在S上都有一个十字。这源于Robertson和Seymour关于Wagner的著名结果？S猜想F对每个曲面S都是有限的。然而，除了当S是球面或射影平面时，对F的元素一无所知。在过去的二十年里，许多研究人员做了许多尝试，但还没有一个新的F完全确定。PI提出了一种不同的方法来解决这个问题。由于F的其他成员是零星的不重要图，因此该结果可以得到每个F的核心成员的特征，这将本质上决定F。本项目的目标是了解当图很好地连通且较大时，拓扑图参数如亏格和交叉数的行为。为了实现这一目标，有必要研究连通性、亏格和图的大小之间的相互作用。很好地理解这种相互作用将给整个拓扑图理论带来重要的启示。由于曲面图是如此基本，这些结果可能在图论的许多领域中具有非常强的理论(关于图结构)和实践(对于图算法)的影响。