Graph genus algorithms

This module integrates algorithms for the orientable genus of a simple connected graph. The built-in 'simple' algorithm is always available. The optional graph_genus package provides the 'page' and 'multi_genus' algorithms.

The simple algorithm works by enumerating combinatorial embeddings of a graph, and computing the genus of these via the Euler characteristic. We view a combinatorial embedding of a graph as a pair of permutations \(v,e\) which act on a set \(B\) of \(2|E(G)|\) “darts”. The permutation \(e\) is an involution, and its orbits correspond to edges in the graph. Similarly, The orbits of \(v\) correspond to the vertices of the graph, and those of \(f = ve\) correspond to faces of the embedded graph. The requirement that the group \(<v,e>\) acts transitively on \(B\) is equivalent to the graph being connected. We can compute the genus of a graph by \(2 - 2g = V - E + F\) where \(E\), \(V\), and \(F\) denote the number of orbits of \(e\), \(v\), and \(f\) respectively.

AUTHORS:

  • Tom Boothby (2010): original simple backtracking algorithm

  • Gunnar Brinkmann (2022): MultiGenus algorithm

  • Alexander Metzger and Austin Ulrigg (2026): PAGE algorithm

  • Alexander Metzger (2026): Sage integration of PAGE and MultiGenus

class sage.graphs.genus.simple_connected_genus_backtracker[source]

Bases: object

A class which computes the genus of a DenseGraph through an extremely slow but relatively optimized algorithm. This is “only” exponential for graphs of bounded degree, and feels pretty snappy for 3-regular graphs. The generic runtime is

\(|V(G)| \prod_{v \in V(G)} (deg(v)-1)!\)

which is \(2^{|V(G)|}\) for 3-regular graphs, and can achieve \(n(n-1)!^{n}\) for the complete graph on \(n\) vertices. We can handily compute the genus of \(K_6\) in milliseconds on modern hardware, but \(K_7\) may take a few days. Don’t bother with \(K_8\), or any graph with more than one vertex of degree 10 or worse, unless you can find an a priori lower bound on the genus and expect the graph to have that genus.

Warning

THIS MAY SEGFAULT OR HANG ON:

  • DISCONNECTED GRAPHS

  • DIRECTED GRAPHS

  • LOOPED GRAPHS

  • MULTIGRAPHS

EXAMPLES:

sage: import sage.graphs.genus
sage: G = graphs.CompleteGraph(6)
sage: G = Graph(G, sparse=False)
sage: bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: bt.genus() #long time
1
sage: bt.genus(cutoff=1)
1
sage: G = graphs.PetersenGraph()
sage: G = Graph(G, sparse=False)
sage: bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: bt.genus()
1
sage: G = graphs.FlowerSnark()
sage: G = Graph(G, sparse=False)
sage: bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: bt.genus()
2

>>> from sage.all import *
>>> import sage.graphs.genus
>>> G = graphs.CompleteGraph(Integer(6))
>>> G = Graph(G, sparse=False)
>>> bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> bt.genus() #long time
1
>>> bt.genus(cutoff=Integer(1))
1
>>> G = graphs.PetersenGraph()
>>> G = Graph(G, sparse=False)
>>> bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> bt.genus()
1
>>> G = graphs.FlowerSnark()
>>> G = Graph(G, sparse=False)
>>> bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> bt.genus()
2
genus(style=1, cutoff=0, record_embedding=False)[source]

Compute the minimal or maximal genus of self’s graph.

Note, this is a remarkably naive algorithm for a very difficult problem. Most interesting cases will take millennia to finish, with the exception of graphs with max degree 3.

INPUT:

  • style – integer (default: \(1\)); find minimum genus if 1, maximum genus if 2

  • cutoff – integer (default: \(0\)); stop searching if search style is 1 and genus \(\leq\) cutoff, or if style is 2 and genus \(\geq\) cutoff. This is useful where the genus of the graph has a known bound.

  • record_embedding – boolean (default: False); whether or not to remember the best embedding seen. This embedding can be retrieved with self.get_embedding().

OUTPUT: the minimal or maximal genus for self’s graph

EXAMPLES:

sage: import sage.graphs.genus
sage: G = Graph(graphs.CompleteGraph(5), sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.genus(cutoff=2, record_embedding=True)
2
sage: E = gb.get_embedding()
sage: gb.genus(record_embedding=False)
1
sage: gb.get_embedding() == E
True
sage: gb.genus(style=2, cutoff=5)
3
sage: G = Graph(sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.genus()
0

>>> from sage.all import *
>>> import sage.graphs.genus
>>> G = Graph(graphs.CompleteGraph(Integer(5)), sparse=False)
>>> gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> gb.genus(cutoff=Integer(2), record_embedding=True)
2
>>> E = gb.get_embedding()
>>> gb.genus(record_embedding=False)
1
>>> gb.get_embedding() == E
True
>>> gb.genus(style=Integer(2), cutoff=Integer(5))
3
>>> G = Graph(sparse=False)
>>> gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> gb.genus()
0
get_embedding()[source]

Return an embedding for the graph.

If min_genus_backtrack has been called with record_embedding = True, then this will return the first minimal embedding that we found. Otherwise, this returns the first embedding considered.

EXAMPLES:

sage: import sage.graphs.genus
sage: G = Graph(graphs.CompleteGraph(5), sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.genus(record_embedding=True)
1
sage: gb.get_embedding()
{0: [1, 2, 3, 4], 1: [0, 2, 3, 4], 2: [0, 1, 4, 3], 3: [0, 2, 1, 4], 4: [0, 3, 1, 2]}
sage: G = Graph(sparse=False)
sage: G.add_edge(0,1)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.get_embedding()
{0: [1], 1: [0]}
sage: G = Graph(sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.get_embedding()
{}

>>> from sage.all import *
>>> import sage.graphs.genus
>>> G = Graph(graphs.CompleteGraph(Integer(5)), sparse=False)
>>> gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> gb.genus(record_embedding=True)
1
>>> gb.get_embedding()
{0: [1, 2, 3, 4], 1: [0, 2, 3, 4], 2: [0, 1, 4, 3], 3: [0, 2, 1, 4], 4: [0, 3, 1, 2]}
>>> G = Graph(sparse=False)
>>> G.add_edge(Integer(0),Integer(1))
>>> gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> gb.get_embedding()
{0: [1], 1: [0]}
>>> G = Graph(sparse=False)
>>> gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[Integer(0)])
>>> gb.get_embedding()
{}
sage.graphs.genus.simple_connected_graph_genus(G, set_embedding=False, check=True, minimal=True, algorithm=None)[source]

Compute the genus of a simple connected graph.

INPUT:

  • G – a simple connected graph

  • set_embedding – boolean (default: False); whether to store a minimum-genus combinatorial embedding on G

  • check – boolean (default: True); whether to validate and simplify the graph before the computation

  • minimal – boolean (default: True); whether to compute minimum genus. If False, only algorithm='simple' is supported.

  • algorithm – string or None (default: None); one of 'page', 'multi_genus', or 'simple'. If None, Sage uses 'page' when the optional graph_genus package is installed and otherwise uses 'simple'.

OUTPUT: integer; the orientable genus of G

EXAMPLES:

sage: import sage.graphs.genus
sage: from sage.graphs.genus import simple_connected_graph_genus as genus
sage: graphs.CompleteGraph(5).genus()
1
sage: graphs.CompleteGraph(5).genus(algorithm='simple')
1
sage: graphs.CompleteGraph(5).genus(algorithm='page')      # optional - graph_genus
1
sage: graphs.CompleteGraph(5).genus(algorithm='multi_genus')  # optional - graph_genus
1
sage: G = graphs.PetersenGraph()
sage: genus(G, algorithm='simple')
1
sage: genus(G, algorithm='page')                            # optional - graph_genus
1
sage: genus(G, algorithm='multi_genus')                     # optional - graph_genus
1

>>> from sage.all import *
>>> import sage.graphs.genus
>>> from sage.graphs.genus import simple_connected_graph_genus as genus
>>> graphs.CompleteGraph(Integer(5)).genus()
1
>>> graphs.CompleteGraph(Integer(5)).genus(algorithm='simple')
1
>>> graphs.CompleteGraph(Integer(5)).genus(algorithm='page')      # optional - graph_genus
1
>>> graphs.CompleteGraph(Integer(5)).genus(algorithm='multi_genus')  # optional - graph_genus
1
>>> G = graphs.PetersenGraph()
>>> genus(G, algorithm='simple')
1
>>> genus(G, algorithm='page')                            # optional - graph_genus
1
>>> genus(G, algorithm='multi_genus')                     # optional - graph_genus
1

ALGORITHM:

The 'simple' algorithm is always available and is the fallback default when the optional graph_genus package is not installed. It is a direct rotation-system enumeration; it is useful for maximum genus and as a compact reference implementation, but has much worse scaling.

The optional 'page' algorithm is provided by graph_genus and is based on the cycle-fitting method of [MetUlr2026]. It is usually the best choice for low-degree sparse graphs. For example, PAGE solves 3-cages through many girth-9 examples in seconds where the simple enumerator takes days or does not finish. The optional 'multi_genus' algorithm is also provided by graph_genus and wraps Brinkmann’s implementation [Bri2022], which is often extremely fast on complete, complete multipartite, and many dense/small examples, but has fixed C integer-size limits.