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

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 \( \Gamma \) is the set of genera of closed surfaces that \( \Gamma \) can be cellularly embedded into. Inspired by models of DNA rearrangements, we study the change in the genus range of a graph \( \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.