Genus

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._cg)
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._cg)
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._cg)
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._cg)
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._cg)
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.

DOCTESTS:

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._cg)
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._cg)
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._cg)
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

REFERENCS:

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

Previous topic

Matching Polynomial

Next topic

Linear Extensions of Directed Acyclic Graphs.

This Page