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:
objectA 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
- genus(style=1, cutoff=0, record_embedding=False)¶
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 2cutoff– integer (default:0); stop searching if search style is 1 andgenus\(\leq\)cutoff, or if style is 2 andgenus\(\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 withself.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
- get_embedding()¶
Return an embedding for the graph.
If
min_genus_backtrackhas been called withrecord_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() {}
- 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 = FalseUNLESS 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: