Classification of Minimal Separating Sets of Low Genus Surfaces

A minimal separating set in a connected topological space $X$ is a subset $L\subset X$ with the property that $X\setminus L$ is disconnected, but if $L^{\mathrm{\prime }}$ is a proper subset of $L$, then $X\setminus L^{\mathrm{\prime }}$ is connected. Such sets show up in a variety of contexts. For example, in a wide class of metric spaces, if we choose distinct points p and q, then the set of points x satisfying d(x, p) = d(x, q) is a minimal separating set. In this paper we classify which topological graphs can be realized as minimal separating sets in surfaces of low genus. In general the question of whether a graph can be embedded at all in a surface is a difficult one, so our work is partly computational. We classify graphs embeddings which are minimal separating in a given genus and write a computer program to find all such embeddings and their underlying graphs.