Changes in Genus Ranges of 4-Regular Graphs by Insertions of Certain Subgraphs

Abstract

A rigid vertex is a vertex with a prescribed cyclic order of its incident edges. An embedding of a rigid vertex graph preserves such a cyclic order in the surface at every vertex. A cellular embedding of a graph has the complementary regions homeomorphic to open disks.

The genus range of a $4$-regular rigid vertex graph $\mathrm{\Gamma }$ is the set of genera of closed surfaces that $\mathrm{\Gamma }$ can be cellularly embedded into. Inspired by models of DNA rearrangements, we study the change in the genus range of a graph $\mathrm{\Gamma }$ after the insertion of subgraph structures that correspond to intertwining two edges. We show that such insertions can increase the genus at most by $2$ and decrease by at most $1$, regardless of the number of new vertices inserted.