Codes of Rotation Systems of a Cell-Embedded Graph in an Oriented Surface

Abstract

This software generates, counts, and classifies codes of rotation systems of cell-embedded graphs in oriented surfaces with a fixed root vertex and a fixed oriented sector. For a given number kk of edges, a code is a finite sequence over the alphabet {0,1,…,k}. Each number 1,…,k occurs exactly twice, while 0 may occur an arbitrary number of times. The codes satisfy additional canonical conditions that determine the order of first occurrences and the positions of zeros. The program provides algorithms for: generating all admissible codes; counting codes without explicitly generating them, using memoization; computing the distribution of codes by genus; determining equivalence classes when the root vertex and the orientation are fixed but the choice of the root sector is free; determining cyclic symmetries of the root vertex; computing the number of equivalence classes with a prescribed symmetry order; producing summary statistics by genus; exporting enumerative sequences to JSON; computing the number of ways to choose prescribed numbers of vertices and faces up to symmetry. Two codes are considered equivalent if they represent the same cell-embedded graph with the same root vertex and the same orientation of the surface, and differ only in the choice of the oriented sector at that vertex. The program uses a depth-first search algorithm for code generation and a memoized recursive algorithm for fast enumeration. For example, for k=5k=5, the program produces 8162 admissible codes, distributed by genus as follows:genus 0: 2916,genus 1: 4280,genus 2: 966. These codes form 2286 equivalence classes:genus 0: 1032,genus 1: 1100,genus 2: 154. The software is intended for computational enumeration and classification of rotation systems and may be used in research on graph embeddings, topological graph theory, and dynamical systems on surfaces. Author: Alexandr PrishlyakORCID: 0000-0002-7164-807X Software version: 1.0.0