Cellular embeddability, properties and symmetries of leveled spatial graphs

Embedding graphs on surfaces is a widely studied topic. Mathematicians first studied planar graphs, which are graphs embedded on the plane or sphere. After Kuratowski, the focus shifted to graphs cellular embedded in orientable surfaces of higher genus. Even though many results have been obtained for the cellular embedding possibilities of abstract graphs, little is known about the cellular embeddability of spatial graphs. In this thesis, we focus on analyzing the cellular embedding possibilities in case the surface needs to be embedded in 3-space up to ambient isotopy. This restriction results in the most relevant setting for applications taking place in the 3-dimensional Euclidean world. In the first chapter, we introduce the leveled spatial graphs. We explore the cellular embedding possibilities of this newly introduced family of spatial graphs. We show that every leveled embedding with at most four levels can be cellular embedded and we give a construction for the surface where the spatial graph cellular embeds, together with a formula to compute the genus of the surface. Moreover, we provide an algorithm that, if successful, builds a surface where the levelled spatial graph given as input cellular embeds. Finally, we discuss the limits of our algorithm. In the second chapter, we analyze the family of leveled spatial graph in the broader context of topological graph theory. Namely, we compare the leveled embeddings with other two spatial graph properties: freeness and paneledness. We show that leveled spatial graphs are a subfamily of free embeddings and we find a sufficient condition for a paneled embedding to be leveled. Moreover, we introduce a new graph invariant related to levelled embeddings: the level number. We compare it with two existing similar graph invariants: the thickness and the book thickness of a graph. Finally, we characterize completely the level number of complete graphs and complete bipartite graphs. In the third chapter, we investigate a particular class of leveled spatial graphs: polyhedra. We analyze local symmetry-preserving operations on polyhedra, introduced by Brinkmann, Goetschalckx and Schein, and focus on which of these operations increase the symmetry of polyhedral maps. We give a complete solution to this problem for Goldberg-Coxeter operations and for local symmetry-preserving operations with inflation factor up to 6. For these operations, we find out in which genera they can increase symmetry. In the fourth chapter, we compare two well-known graph operations, the line graph and the edge-complement graph. After listing some of their properties, we show that there exist only two graphs up to isomorphism which have isomorphic line graph and edge-complement graph. We provide an alternative proof to the original one by Aigner.