Embeddings of Graphs in Surfaces

点击翻译按钮获取中文摘要

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.