Some problems in topological graph theory

拓扑图理论研究如何以不同的方式在曲面上绘制图。它的一个基本问题是为每个曲面S确定最小图的集合F，无论它们是如何在S上绘制的，这些最小图都有一个交叉。它遵循了Robertson和Seymour关于Wagner？我猜想F对每一个曲面s都是有限的。然而，对于F的元素我们一无所知，除非s是球面或投影平面。在过去的二十年里，许多研究者做了许多尝试，但没有一个新的F是完全确定的。PI提出了一种不同的方法来解决这个问题。从这个提议中产生的结果可能导致每个F的核心成员的特征，这将本质上决定F，因为F的其他成员是零星的不重要的图。这个项目的目标是理解当图连接良好且很大时，拓扑图参数（如属数和交叉数）的行为。为了实现这一目标，有必要研究连通性、属和图的大小之间的相互作用。对这种相互作用的良好理解将为整个拓扑图理论带来重要的见解。由于曲面图是如此基础，这些结果可能在图论的许多领域具有很强的理论（关于图结构）和实践（关于图算法）影响。

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.