Graph Genus

State of the art practical algorithms for computing the minimum genus of graphs and the corresponding embeddings. Contains standalone C programs, python bindings, and a web version with 2D and 3D visualizations.

Motivation

A famous problem at the intersection of topology and combinatorial graph theory is the Utility Problem. Say you have three houses and three utilities and you need to connect each house to each utility via a wire. Is there a way to do this without the wires crossing? In terms of graph theory, this is asking whether K3,3 is planar. It is known that it is not. In fact K3,3 is toroidal meaning while it cannot be embedded on a plane without edges crossing, it can be embedded on a torus:

The characterizing property of a torus that allows us to embed K3,3 is that it has a hole (unlike surfaces such as a plane or a sphere). This motivates classifying surfaces by their number of holes, that is, their genus g. The genus of a graph G is then simply the genus of the minimum genus surface on which G can be embedded without edges crossing. For genus zero we use the special name planar and for genus one we use toroidal. Calculating the genus of a graph has a number of applications, particularly in the design of integrated circuits, study of graph minors, VLSI design, infrastructure planning, and more. For an interactive visualization of graph embedding check here.

Usage

The easiest way is to use the web version. This won't be as fast as running it locally and I can't guarantee it will always be up, but it should allow you to explore the algorithm. You can also self-host the web application by installing docker and running cd app followed by . ./run-dev.sh. This will start the web application on localhost:8080.

The easiest way to run locally, is with the graph-genus Python package. Make sure you have Python 3. Then pip install graph-genus and you can use the Python API:

import graph_genus as gg

adjacency_list = [[3, 4, 5], [3, 4, 5], [3, 4, 5],
                  [0, 1, 2], [0, 1, 2], [0, 1, 2]]
genus, rotation_system = gg.embed(adjacency_list)

• As an optional parameter to embed, you can use algorithm="page" (default), algorithm="multi_genus", and algorithm="none". "page" is especially fast for high girth graphs and scales well in general too. "multi_genus" is included with permission from Gunnar Brinkmann, is faster for some graph families, and uses less resources, but handles at most 128 vertices and 512 undirected edges. "none" treats adjacency_list as an already chosen rotation system.
• You can also use output_format="rotation_system" (default), output_format="drawing" for TikZ/LaTeX output of the fundamental polygon, and output_format="3D" for OBJ output of the 3D surface with the graph drawn on it.
• PAGE additionally allows the low_memory=True option for very large graphs with tens of thousands of edges.
• Use gg.cite(algorithm, output_format) to retrieve the relevant BibTeX entries.

For local development, install with make -C PAGE all && make -C MultiGenus all && pip install -e . then test with python tests/test_graph_genus_package.py (should take ~2 minutes). Build with source build_wheels.sh, check with source build_wheels_test.sh, and upload with pipx run twine upload dist/*.

To run the algorithms directly without the Python bindings, take a look at the instructions for PAGE and MultiGenus.

Acknowledgements

Austin contributed equally to the ideas behind PAGE. Professor Steinerberger provided guidance on the PAGE publication. Professor Brinkmann provided a fast alternative algorithm, multi_genus, and useful code for visualizing embeddings.

License

This project is licensed under the terms of the GNU General Public License v2.0 (GPLv2). See the LICENSE file for the full text.

Citation

If you use the PAGE algorithm or other code/visualizations from this repository, python package, or webapp, please cite:

@article{Metzger_2026,
   title={An efficient genus algorithm based on graph rotations},
   volume={349},
   ISSN={0012-365X},
   url={http://doi.org/10.1016/j.disc.2026.115308},
   DOI={10.1016/j.disc.2026.115308},
   number={12},
   journal={Discrete Mathematics},
   publisher={Elsevier BV},
   author={Metzger, Alexander and Ulrigg, Austin},
   year={2026},
   month=Dec, pages={115308}
}

If you use multi_genus, please cite

@article{article,
    author = {Brinkmann, Gunnar},
    year = {2022},
    month = {07},
    pages = {#P4.01},
    title = {A practical algorithm for the computation of the genus},
    volume = {22},
    journal = {Ars Mathematica Contemporanea},
    doi = {10.26493/1855-3974.2320.c2d}
}

And if you use the fundamental polygon drawings or 3D visualizations, please additionally cite

@misc{brinkmann2025drawingmapsorientedsurfaces,
    title={Drawing maps on oriented surfaces}, 
    author={Gunnar Brinkmann},
    year={2025},
    eprint={2505.01480},
    archivePrefix={arXiv},
    primaryClass={cs.CG},
    url={https://arxiv.org/abs/2505.01480}, 
}

You may also want to check out the literature this work is based on.