Upper embeddability in terms of boundary walks

Abstract

Topological graph theory is the branch of graph theory that investigates graphs as topological spaces and the embedding of graphs in surfaces. An embedding of a graph 𝐺 into a surface is a representation of the graph on the surface such that the edges only intersect at their shared vertices. If each face of the embedded graph is homeomorphic to an open disk, the embedding is called a 2-cell embedding. The maximal genus of a graph 𝐺 is the largest integer 𝑛 such that 𝐺 can be 2-cell embedded into a connected sum of 𝑛 tori. An embedding of the graph corresponds to a rotation system that we impose on the graph, and to each rotation system, we associate a set of boundary walks. A boundary walk corresponds to a walk around the border of the face of the embedding and is made up of directed edges in the graph. In this research, the relationship between the maximal embedding genus of a graph 𝐺(𝑉, 𝐸) and the number of boundary walks 𝐵 needed for this embedding was studied with respect to some rotation system. 2-cell embeddings of hypercube and complete graphs were studied, and the findings have been generalized to any simple connected graph. More specifically, we characterise the upper embeddability of a simple connected graph 𝐺 in terms of the number of boundary walks corresponding to a specific rotation system of 𝐺. That is, a graph 𝐺 is upper embeddable if and only if there exists a rotation system that generates either a single boundary walks if |𝐸| − |𝑉| is odd or two boundary walks if |𝐸| − |𝑉| is even. As a corollary, we derive the inequality, 1 ≤ 𝐵 ≤ |𝐸| − |𝑉| + 2.