The topic of this master's thesis is set in the field of graph theory, which deals, among other things, with graph embeddings on different surfaces. The most straightforward embeddings are so called planar embeddings, for which the only requirement is that the edges of the graph must not intersect each other. For a planar embedding of a graph we have the Euler's formula, which describes the relationship between the number of vertices, edges and faces of a graph. Also, we have the well-known theorem of Kuratowski which gives a necessary and sufficient condition for the existence of a planar embedding of a given graph. This theorem tells us that there are only two so-called minimal non-embeddable graphs on the plane, in the sense that a given graph is not planar if and only if in some way (which we will not explain here) it contains at least one of these two graphs.
In this thesis we focus on the analysis of graph embeddings on the torus. Although the torus is a relatively simple surface, we have to be much more careful when giving definitions concerning embeddings on the torus than on the plane. Firstly we present the requirements of a toroidal embedding and why we need to be so precise in its definition. We also consider the Euler's formula for toroidal embeddings. We will not be able to give an analogue of the theorem of Kuratowski on the torus, since we don't yet know how many minimal non-embeddable graphs there are on the torus. Nevertheless, we present some of these
graphs and show why we call them minimal non-embeddable. In the last part we investigate whether some planar graphs can be embedded on the torus, which non-planar graphs can be embedded on the torus, and which graphs are not embeddable on the torus.
|
