String representation of trivalent 2-stratifolds with trivial fundamental group (Q6044472)

A trivalent \(2\)-stratifold \(X\) is obtained from a collection of compact surfaces with boundary by identifying the boundary curves with circles (the singular curves) via covering maps of degree \(\leq 3\). \(X\) may be described by a bicolored labelled graph \(\Gamma_X\), with white vertices corresponding to the surfaces, black vertices corresponding to the singular curves, and edge labels corresponding to the covering maps. (The labelled graph isomorphism class of) \(\Gamma_X\) determines \(X=X_\Gamma\) uniquely (up to homeomorphisms). Such a graph is called a \(2\)-stratifold graph. The authors develop an effective computer algorithm that effectively constructs all simply connected \(2\)-stratifold graphs up to a given number of white vertices. For such a graph they show that there is a unique vertex, the root, that is a labelled isomorphism invariant of \(\Gamma_X\). Using the root, they associate a unique string on four symbols to \(\Gamma_X\) and show that trivalent stratifold graphs are isomorphic if and only if they have the same string representation. To obtain an algorithm for constructing simply connected \(2\)-stratifold graphs, they use a set of three operations on a trivalent graph, developed in [\textit{J. C. Gómez-Larrañaga} et al., Bol. Soc. Mat. Mex., III. Ser. 26, No. 3, 1301--1312 (2020; Zbl 1456.57014)], where it is shown that all simply connected trivalent graphs may be constructed from a single white vertex using these operations. The authors apply a modified AHU algorithm to the string representation and write a Python program for constructing all distinct trivalent simply-connected \(2\)-stratifold graphs for a given number of white vertices. Furthermore the algorithm is in linear time and includes an optimization that reduces repetitions at generating the graphs.