Collaborative Research: Graphs on Surfaces and Related Problems

合作研究：曲面上的图和相关问题马克·N·埃林厄姆和查小雅研究嵌入在曲面上的图的性质，以及一些密切相关的问题。这项拟议的研究解决了五类问题。首先，研究了嵌入在曲面上的图或具有相关条件的图的可遍历性问题。特别地，研究了k-行走和k-路的存在性，即遍历一个图访问每个顶点至少一次且至多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.