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 usealgorithm="page"(default),algorithm="multi_genus", andalgorithm="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"treatsadjacency_listas 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, andoutput_format="3D"for OBJ output of the 3D surface with the graph drawn on it. - Higher-genus 3D output routes edges directly on a surface mesh and preserves the supplied rotations. See the layout algorithm and its limits.
- PAGE additionally allows the
low_memory=Trueoption 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.
Metadata
Release files for graph-genus 0.1.3
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| graph_genus-0.1.3.tar.gz | 124.6 kB | Without provenance | Details for graph_genus-0.1.3.tar.gz |
Built distributions (wheels)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| graph_genus-0.1.3-py3-none-win_amd64.whl | Python 3 | none | Windows x86-64 | Details for graph_genus-0.1.3-py3-none-win_amd64.whl |
| graph_genus-0.1.3-py3-none-manylinux2014_x86_64.manylinux_2_17_x86_64.whl | Python 3 | none | Linux glibc 2.17+ x86-64 | Details for graph_genus-0.1.3-py3-none-manylinux2014_x86_64.manylinux_2_17_x86_64.whl |
| graph_genus-0.1.3-py3-none-macosx_15_0_arm64.whl | Python 3 | none | macOS 15.0+ ARM64 | Details for graph_genus-0.1.3-py3-none-macosx_15_0_arm64.whl |
Total release size: 829.7 kB
Release files / graph_genus-0.1.3.tar.gz
| Download URL | graph_genus-0.1.3.tar.gz |
|---|---|
| Size | 124.6 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
2413f467e34dde1b3f196777c1e2068288fefdc38221c1154433e317ee4be7ba
|
|
BLAKE2b-256 checksum How to use checksums |
424569b8be96cae71d48d512bb7f544c6d5ce9db438f14126521a8e11e1ffe00
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.13.2
|
Release files / graph_genus-0.1.3-py3-none-win_amd64.whl
| Download URL | graph_genus-0.1.3-py3-none-win_amd64.whl |
|---|---|
| Size | 363.9 kB |
| Tags | Python 3 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
590f9d519bb68f22378f4b1ee5529cfe87c845198d3296a9e26e2e9289ef8554
|
|
BLAKE2b-256 checksum How to use checksums |
9f833b002cb6b58248d6909cb53518f77b6e3f1188b28a7fd7c1ec44e08a2a69
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.13.2
|
Release files / graph_genus-0.1.3-py3-none-manylinux2014_x86_64.manylinux_2_17_x86_64.whl
| Download URL | graph_genus-0.1.3-py3-none-manylinux2014_x86_64.manylinux_2_17_x86_64.whl |
|---|---|
| Size | 175.9 kB |
| Tags | Linux glibc 2.17+ x86-64 Python 3 |
|
SHA-256 checksum How to use checksums |
a35255512aa4c4aefe6114cca2df622cb583675dc429cb0c020551c3fd8bb437
|
|
BLAKE2b-256 checksum How to use checksums |
ab3a48638b60499af7979b3a3dd0ebf4aaf515a124fa51c91e11996eaa4d50dd
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.13.2
|
Release files / graph_genus-0.1.3-py3-none-macosx_15_0_arm64.whl
| Download URL | graph_genus-0.1.3-py3-none-macosx_15_0_arm64.whl |
|---|---|
| Size | 165.3 kB |
| Tags | Python 3 macOS 15.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
a99fd915aec9d288b9814139e7787eca84f2acc41347a616b5f5dcea8b27716c
|
|
BLAKE2b-256 checksum How to use checksums |
23e70b5c598a28d02ef3f0fc55d18567139291fa06eab3241dfa09bfbd41d836
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/7.0.0 CPython/3.13.2
|
Security for graph-genus 0.1.3
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.