# Genus#

This file contains a moderately-optimized implementation to compute the genus of simple connected graph. It runs about a thousand times faster than the previous version in Sage, not including asymptotic improvements.

The 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.

We make several optimizations to the naive algorithm, which are described throughout the file.

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)[source]#

Compute the genus of a simple connected graph.

Warning

THIS MAY SEGFAULT OR HANG ON:
• DISCONNECTED GRAPHS

• DIRECTED GRAPHS

• LOOPED GRAPHS

• MULTIGRAPHS

DO NOT CALL WITH check = False UNLESS YOU ARE CERTAIN.

EXAMPLES:

sage: import sage.graphs.genus
sage: from sage.graphs.genus import simple_connected_graph_genus as genus
sage: [genus(g) for g in graphs(6) if g.is_connected()].count(1)
13
sage: G = graphs.FlowerSnark()
sage: genus(G)  # see [1]
2
sage: G = graphs.BubbleSortGraph(4)
sage: genus(G)
0
sage: G = graphs.OddGraph(3)
sage: genus(G)
1

>>> from sage.all import *
>>> import sage.graphs.genus
>>> from sage.graphs.genus import simple_connected_graph_genus as genus
>>> [genus(g) for g in graphs(Integer(6)) if g.is_connected()].count(Integer(1))
13
>>> G = graphs.FlowerSnark()
>>> genus(G)  # see [1]
2
>>> G = graphs.BubbleSortGraph(Integer(4))
>>> genus(G)
0
>>> G = graphs.OddGraph(Integer(3))
>>> genus(G)
1


REFERENCES: