Collaborative Research: Graphs on Surfaces and Related Problems

Mark N. Ellingham和Xiaoya Zha研究嵌入在表面上的图的性质，以及一些密切相关的问题。拟议的研究涉及五种类型的问题。首先，研究嵌入在曲面上或具有相关条件的图的可遍历性问题。特别地，研究了k-walks和k-trails的存在性，即遍历图中每个顶点至少访问一次和最多访问k次的方法。其次，研究人员研究了嵌入在表面上的图的谱半径（邻接矩阵的最大特征值），特别是平面；这是一个重要的参数，与图中的行走次数有关。第三，研究人员研究了一个表面和嵌入在该表面上的图的连通性之间的关系，这些图以特别自然的方式嵌入，如属嵌入。第四，研究了具有闭面同胚于闭盘等优良性质的图嵌入的存在性，以及这种嵌入与循环双盖猜想等分解问题的关系。第五，研究人员关注的问题是将嵌入图的表面沿图中的不可收缩循环切割成更小的非平凡块，因为该领域的结果将为研究图嵌入领域的许多问题提供一个非常有前途的工具。图是网络的抽象数学模型。在现代世界，对通信和交通网络的研究变得越来越重要。特别是，许多现实世界的网络是平面的，这意味着它们可以画在一张纸上，没有任何链接交叉。一个网络与平面的距离有多近与其许多有用的特性有关，数学家通过观察所谓的图在表面上的嵌入来研究这一点。这项研究检验的有用属性包括可穿越性（我们如何以或多或少有效的方式在网络中旅行，访问每个节点——这是旅行推销员问题等问题的动机），网络作为交通网络的工作效果如何（这涉及到一个被称为频谱半径的数字，地理学家对此很感兴趣），以及连通性（抵抗攻击的破坏）。除了研究网络的有用性质外，本研究还开发了研究这些性质的新工具。绘制在一个表面上的网络，如果划分表面的区域没有相互接触，就更容易处理。研究人员对网络是否总是能以这种漂亮的方式绘制的问题感兴趣。研究人员还对绘制在一个表面上的网络是否可以以一种自然的方式切割开来，以得到绘制在不那么复杂的表面上的网络的问题感兴趣。这两个问题都应该有助于更好地理解绘制在表面上的网络，从而找到检验这种网络有用属性的方法。

Collaborative Research: Graphs on Surfaces and Related Problems Mark N. Ellingham and Xiaoya Zha The investigators study properties of graphs embedded on surfaces, together with some closely related problems. The proposed research addresses five types of problems. First, traversability problems for graphs embedded on surfaces, or with related conditions, are studied. In particular, the existence of k-walks and k-trails, ways to traverse a graph visiting each vertex at least once and at most k times, are investigated. Second, the investigators study the spectral radius (largest eigenvalue of the adjacency matrix) of graphs embedded on surfaces, particularly the plane; this is an important parameter with connections to the number of walks in the graph. Third, the investigators examine the relationship between a surface and the connectivity of graphs that embed on that surface in particularly natural ways, as genus embeddings. Fourth, the existence of graph embeddings with nice properties, such as every closed face being homeomorphic to a closed disk, and the relationship of such embeddings to decomposition problems such as the Cycle Double Cover Conjecture, are studied. Fifth, the investigators are concerned with the problem of cutting a surface with an embedded graph into smaller nontrivial pieces along a noncontractible cycle in the graph, as results in this area would give a very promising tool for studying many problems in the area of graph embeddings. Graphs are abstract mathematical models of networks. In the modern world, the study of communication and transportation networks is becoming ever more important. In particular, many real-world networks are planar, meaning that they can be drawn on a piece of paper without any links crossing. How close a network is to being planar is related to many of its useful properties, and mathematicians study this by looking at so called embeddings of graphs on surfaces. The useful properties examined by this research include traversability (how can we travel around a network, visiting each node, in a more or less efficient way - this is the motivation for such problems as the Traveling Salesman Problem), how well a network works as a traffic network (this involves a number known as the spectral radius, which has been of interest to geographers), and connectivity (resistance to disruption by attack). Besides studying the useful properties of networks, this research also develops new tools for studying such properties. Networks drawn on a surface are easier to work with if none of the regions into which the drawing divides the surface touch themselves, and the investigators are interested in the question of whether networks can always be drawn in this nice way. The investigators are also interested in the question of whether networks drawn on a surface can be cut apart in a natural way to give networks drawn on less complicated surfaces. Both of these questions should lead to better understanding of networks drawn on surfaces, and hence to ways to examine useful properties of such networks.