String representation of trivalent 2-stratifolds with trivial fundamental group

Abstract

We give a Python program that is capable of computing and printing all distinct trivalent simple connected 2-stratifold graphs (see Gómez-Larrañaga et al. in Topol Proc 52:329–340, 2018) up to a chosen number of white vertices. Our algorithm uses the three basic operations described on (Gómez-Larrañaga et al. in Bol Soc Mat Mex 26:1301–1312, 2020) to construct new graphs from a set of graphs. We iterate this process to construct all the desired graphs. The algorithm includes an optimization that reduces repetitions at generating the graphs, this is done by recognizing equivalent white vertices of a graph under automorphism. We use a variation of the AHU algorithm to identify those vertices and as well to distinguish isomorphic graphs in linear time. The returned string from the AHU algorithm is also used as a hashing function to search for repeated graphs in amortized constant time.