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

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, implementation='c_graph', 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, implementation='c_graph', 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, implementation='c_graph', sparse=False)
sage: bt = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: bt.genus()
2
genus(style=1, cutoff=0, record_embedding=0)

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 millenia to finish, with the exception of graphs with max degree 3.

INPUT:

  • style – int, find minimum genus if 1, maximum genus if 2
  • cutoff – int, stop searching if search style is 1 and genus <= cutoff, or if style is 2 and genus >= cutoff. This is useful where the genus of the graph has a known bound.
  • record_embedding – bool, 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), implementation='c_graph', 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(implementation='c_graph', sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.genus()
0
get_embedding()

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), implementation='c_graph', 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(implementation='c_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(implementation='c_graph', sparse=False)
sage: gb = sage.graphs.genus.simple_connected_genus_backtracker(G._backend.c_graph()[0])
sage: gb.get_embedding()
{}
sage.graphs.genus.simple_connected_graph_genus(G, set_embedding=False, check=True, minimal=True)

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

REFERENCES:

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