Embeddings of Graphs in Surfaces

埃林厄姆9622780 图是网络的抽象数学模型。很自然地，我们试图通过将图绘制或嵌入到一个表面上来表示一个图，这样图的边就不会交叉。试图嵌入一个图的自然表面是平面，在平面中的嵌入等价于在球面中的嵌入。许多图形不能嵌入到球体中，但可以嵌入到通过将手柄或称为十字形的数学设备附加到球体而获得的其他曲面中。 这项调查将处理三个方面的图嵌入表面。 (I)图在曲面中的某些嵌入比其他嵌入更好。特别地，嵌入的期望特征是图划分表面或面的每个区域都没有孔并且不接触顶点超过一次。具有此属性的嵌入称为强嵌入。强嵌入猜想（SEC）说任何满足必要条件（2-连通性）的图都有这样的嵌入。 这与图论中的另一个非常重要的问题--圈双覆盖猜想密切相关。调查将：首先，扩展SEC为真的图的范围;其次，考虑强嵌入的局部结构，以确定是什么使它们成为可能;第三，检查嵌入的其他参数，这些参数可能有助于将其他嵌入变为强嵌入。(II)在处理曲面上的嵌入时，能够将曲面切割成更小的块并研究图的块在这些不太复杂的曲面上的嵌入是非常有用的。切割必须遵循嵌入图的边才有帮助;每个切割的边形成嵌入图的分离电路。这项研究将增加目前的知识的情况下，分离电路存在。(III)图论中一个非常重要的问题是，在给定的限制条件下，是否有可能遍历一个图，使得每个顶点都被访问。如果限制是第一，结束于遍历开始的地方，第二，访问顶点不超过k次，结果被称为图中的k-行走。知道一个图可以嵌入到一个特定的曲面中，结合其他条件，可以保证对于某些k值存在k-行走。所提出的研究将确定嵌入在曲面上的图中存在k-行走的条件，特别是具有负欧拉特征的曲面，即， 至少有两个手柄或三个横盖。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。离散系统的行为对现代通信极为重要。例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。

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.