Graphs on Euclidean, spherical and hyperbolic surfaces

This thesis is on the interplay of surfaces and graphs embedded on them. In order to showcase the interactions between the two, it discusses a game commonly played on graphs and surfaces: The Cops and Robber game. The goal in studying this game is to find strategies for the robber to escape from one or more cops and for the cop(s) to catch the robber. This thesis discusses strategies of the players when the game is played on surfaces and higher dimensional manifolds of constant curvature. What properties of a manifold make it easy for the robber to escape the cops? The results in this thesis suggest that the number of cops needed to catch the robber is related to the dimension of the manifold, whereas the number of cops needed to come arbitrarily close to the robber is related to how uniform its curvature is. The relationship between topology and graph theory often stems from representations of graphs as points and curves in topological spaces. This thesis discusses parameters that influence the quality of representations, such as the number of edge crossings of graphs drawn in the plane. For example, we ask how we can decompose the edges of a drawing into two or more subdrawings such that the sum of the edge crossings in each subdrawing is as small as possible. To study this question, we consider random drawings of the complete graph, where vertices are points which are chosen uniformly at random from a Euclidean square, and the edges are straight lines. We show a strategy to decompose such a random graph drawing into two subdrawings, such that the sum of the crossings is small. More generally, this thesis studies intersection graphs of random geometric objects and properties of those intersection graphs such as the density of small substructures or the existence of spanning substructures. Finally, we consider representations of graphs in higher dimensional spaces and their energy as a measure of quality. The energy is a well-studied parameter since it is related to planar drawings of graphs as well as spectral drawings. We provide a new semidefinite graph drawing algorithm that minimises the energy of a representation with respect to a new set of constraints.