Embeddings of Graphs in Surfaces

Ellingham 9622780图是网络的抽象数学模型。试图通过在曲面中绘制或嵌入图形来表示图形是很自然的，以使图形的任何边都不相交的方式。尝试在其中嵌入图形的自然曲面是平面，在平面中嵌入等同于在球面中嵌入。许多图形不能嵌入到球体中，但可以嵌入到通过将手柄或称为交叉盖的数学设备附加到球体获得的其他曲面中。本研究将讨论图在曲面中嵌入的三个方面。(I)图在曲面上的某些嵌入比其他嵌入更好。具体地说，嵌入的一个理想特征是图形将表面或面分割成的每个区域都没有洞，并且不接触任何顶点超过一次。具有此属性的嵌入称为强嵌入。强嵌入猜想(SEC)指出，任何满足必要条件(2-连通性)的图都有这样的嵌入。这与图论中的另一个非常重要的问题--圈双覆盖猜想密切相关。调查将：第一，扩大已知SEC为真的图的范围；第二，考虑强嵌入的局部结构，以期确定是什么使它们成为可能；第三，检查嵌入的其他参数，这些参数可能有助于将其他嵌入改变为强嵌入。(Ii)在处理曲面上的嵌入时，能够将曲面切割成更小的片段并研究图的片段在这些不太复杂的曲面上的嵌入将是非常有用的。切割必须跟随嵌入图形的边才有帮助；每个切割的边形成嵌入图形的分离回路。这项调查将增加关于分离电路存在的情况的现有知识。(Iii)图论中一个非常重要的问题是，在给定的限制下，是否可能以访问每个顶点的方式遍历一个图。如果限制是，首先，在遍历开始的地方结束，第二，不访问不超过k次的顶点，结果称为图中的k-遍历。已知一个图可以嵌入到一个特定的曲面上，结合其他条件，可以保证k的某些值存在k-游程。所提出的研究将确定嵌入在曲面上的图中存在k-游程的条件，特别是具有负Euler特征的曲面，即至少有2个手柄或3个横帽。这项研究属于组合学的一般领域。组合学的目标之一是找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。

Ellingham 9622780 Graphs are abstract mathematical models of networks. It is natural to try to represent a graph by drawing, or embedding, it in a surface, in such a way that no edges of the graph cross. The natural surface in which to try to embed a graph is the plane, and embedding in the plane is equivalent to embedding in the surface of a sphere. Many graphs cannot be embedded in a sphere, but can be embedded in other surfaces obtained by attaching handles, or mathematical devices known as crosscaps, to a sphere. This investigation will deal with three facets of graph embeddings in surfaces. (I) Certain embeddings of a graph in a surface are nicer than others. In particular, a desirable feature of an embedding is that each of the regions into which the graph divides the surface, or faces, has no hole and touches no vertex more than once. Embeddings with this property are called strong embeddings. The Strong Embedding Conjecture (SEC) says that any graph satisfying a necessary condition (2-connectivity) has such an embedding. This is closely related to another very important problem in graph theory, the Cycle Double Cover Conjecture. The investigation will: first, extend the range of graphs for which the SEC is known to be true; second, consider the local structure of strong embeddings with a view to determining what makes them possible, and third, examine other parameters of an embedding which may be useful for changing other embeddings into strong ones.(II) In working with embeddings on a surface, it would be very useful to be able to cut the surface into smaller pieces and investigate embeddings of pieces of the graph on these less complicated surfaces. The cut must follow edges of the embedded graphs to be helpful; the edges of each cut form a separating circuit of the embedded graph. This investigation will increase current knowledge about the circumstances under which separating circuits exist. (III) A very important question in graph theory is whether it is poss ible to traverse a graph in such a way that every vertex is visited, under given restrictions. If the restrictions are first, to end up where the traversal began, and second, to visit no vertex no more than k times, the result is called a k-walk in the graph. Knowing that a graph can be embedded in a particular surface can, in conjunction with other conditions, guarantee the existence of a k-walk for certain values of k. The proposed research will determine conditions for the existence of k-walks in graphs embedded on surfaces, in particular surfaces of negative Euler characteristic, i.e., with at least 2 handles or 3 crosscaps. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.