# 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: 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.