The orientable genus of bipartite graphs and their products

Abstract

The drawing of graphs on surfaces knows its birth in the 19th century, mainly with the four colour problem and the Heawood map colouring problem. The former problem claims that four colours are enough to properly colour the vertices of a planar graph (that is, in such a way that no two adjacent vertices receive the same colour), whereas the latter one asks for the minimum number of colours required to properly colour the vertices of a graph which is embeddable on a higher-order surface. A graph is embeddable on a surface if it can be drawn on that surface without edge crossings, and we say that the graph is planar if the surface used for the embedding is the sphere. There are two complementary perspectives that can be considered when embedding graphs on surfaces, namely fixing the graph and determining which surface allows an embedding of that graph, or fixing the surface and determining whether a graph is embeddable on that surface. In topological graph theory, we only consider a surface which is compact and without a boundary. A surface is characterised by whether it is orientable or nonorientable and by its genus. The sphere is the orientable surface with genus 0 and is denoted by S0. The genus g of an orientable surface Sg is the number of handles that are added to S0, whereas the genus g of a nonorientable surface Ng¯ is the number of Möbius bands (or crosscaps) that are added to S0. For instance, the torus is the surface S1 whereas the projective plane is the surface N1. For a graph G, the genus of G is the smallest genus of a surface which allows an embedding of G. More formally, a graph G has orientable genus g if it can be embedded on an orientable surface of genus g but not on an orientable surface of genus g − 1 (and similarly for the nonorientable genus of a graph). Determining the (orientable and nonorientable) genus of a graph is known to be NP-complete. A lot of work has been done to determine the genus of various families of graphs. Two of the initial results on these lines are given by Ringel and Youngs (1968) and by Ringel (1965), respectively determining the genus of the complete graphs and of the complete bipartite graphs. Since these initial results, other families of graphs were investigated for their genus, including the products of graphs belonging to the two aforementioned families. In this dissertation we find, collate, review and analyse the main results dispersed in literature on the orientable genus of bipartite graphs, the Cartesian product and the direct product of two or more bipartite graphs.