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:

[1] http://www.springerlink.com/content/0776127h0r7548v7/