A Practical Algorithm for Graph Embedding (PAGE)

A famous problem at the intersection of topology and combinatorial graph theory is the Utility Problem. Say you have three houses and three utilities and you need to connect each house to each utility via a wire. Is there a way to do this without the wires crossing? In terms of graph theory, this is asking whether K3,3 is planar. It is known that it is not. In fact K3,3 is toroidal meaning while it cannot be embedded on a plane without edges crossing, it can be embedded on a torus:

The characterizing property of a torus that allows us to embed K3,3 is that it has a hole (unlike surfaces such as a plane or a sphere). This motivates classifying surfaces by their number of holes, that is, their genus g. The genus of a graph G is then simply the genus of the minimum genus surface on which G can be embedded without edges crossing. For genus zero we use the special name planar and for genus one we use toroidal. Calculating the genus of a graph has a number of applications, particularly in the design of integrated circuits, study of graph minors, VLSI design, infrastructure planning, and more.

Properties of this algorithm

This repo contains a fast algorithm for calculating the genus of arbitrary graphs. It has a number of properties that make it practical for real-world use:

1. Verification: The algorithm outputs not only the genus but also the corresponding rotation system that defines the surface embedding that achieves this minimum genus. This allows for easy verification of the result both via a Python script and visually:

2. Progressively Narrowing Bounds: The algorithm iterates through possible embeddings and progressively narrows the bounds on the genus. This allows for early stopping if only an estimate is needed.

3. Simplicity of Implementation: While there exist more efficient algorithms for certain graph families (e.g., multi_genus does better on lower genus high degree graphs), this algorithm is much simpler to implement (can be done in a few dozen lines of Python or a few hundred lines of C).

4. Scales Well With Genus: The algorithm can handle graphs with high genus much better than existing algorithms. It can for instance complete the (3, 10) Cages in a few minutes whereas SageMath doesn't finish in weeks and multi_genus takes hours. It does not, however, scale as well with degree as multi_genus for low genus graphs, so there is a tradeoff and the optimal algorithm depends on both the genus and degree of the graph.

5. Easily Parallelizable: The algorithm can be easily parallelized since a parallelizable cycle finding algorithm is chosen and the search needs to go through each possible start cycle (which can be done in parallel). This allows for a speedup proportional to the number of cores available.

Usage

The easiest way is to use the hosted version. This won't be as fast as running it locally and I can't guarantee it will always be up, but it should allow you to explore the algorithm. You can also self-host the web application by installing docker and running cd WebApp followed by . ./run-dev.sh. This will start the web application on localhost:8080.

To run the python scripts you must have SageMath installed and select the SageMath kernel in Jupyter/VS Code/whatever you use.

To run the C program for any graph, cd CalcGenus and run S="0" DEG="3" ADJ="adjacency_lists/3-8-cage.txt" make run. This will compile the C program and run it. The output will be in CalcGenus.out. The format of the adjacency lists is the number of vertices and number of edges on the first line followed by the neighbors of each vertex on the following lines. See the examples in CalcGenus/adjacency_lists/. Use MallocStackLogging=1 S="0" DEG="3" ADJ="adjacency_lists/3-8-cage.txt" leaks -quiet -atExit -- ./CalcGenus to check for memory leaks on macOS.

Time Complexity

Let n be the size of the vertex set V and m the size of the edge set E. Let G be the girth of the graph.

The algorithm in this repository is roughly O(n(4^m/n)^(n/G)). It has some optimizations that allows it to stop early not captured in the below analysis.

• Upper bound on the number of directed trails of length k: 2m choose k = (2m)!/k!/(2m-k)! which is bounded above by \sqrt{\frac{1}{2\pi}}\frac{\left(2m\right)^{\left(2m+\frac{1}{2}\right)}}{k^{\left(k+\frac{1}{2}\right)}\left(2m-k\right)^{\left(2m-k+\frac{1}{2}\right)}} as seen in Bob Gallager's Information Theory and Reliable Communications. This is maximized for k=m where it simplifies to 4^m/\sqrt{\pi m}. A simpler but less tight bound is 2m choose k <= (2em/k)^k.

• The number of directed trails of any length is O(4^m) because it is the sum of the values in the 2mth row of Pascal's triangle.

• This can also be used to upper bound the number of non-backtracking closed directed trails which is what our trail finding algorithm enumerates. Let c be the number of trails enumerated by our trail finding algorithm.

• Organizing the c trails by vertex is O(2mc) < O(2m4^m) since each trail has at most 2m edges.

• Finding the most used vertex to explore: O(n) by iterating through the vertices (overall time complexity is better when write is kept O(1))

• Looking up the cycles that use a vertex: O(1) via hashset lookup

• Checking if a cycle is used: O(1) via hashset lookup

• Checking if the edges of a cycle are used: O(m) by storing the edges used in a hashset

• Checking if adding cycle breaks rotation system: O(m) by storing the current rotation with the adjacency list

• Search iteration (f = implied fit, b = cycles by vertex >= u = unused >= a = w/ edges available >= d = rotation valid): T(f) = O(n) + O(1) + b O(1) + u O(m) + a O(m) + d T(f-1); T(0) = 0 => O(d^f * (n + b + um + am)) = O(d^f * (n + b + m(u + a))) < O(b^(f + 2))

• All search iterations (h = number of start cycles to try out < 4^m): O(b^(f + 2) * h) < O((4^m / n)^(n/G) * 4^m) = O(n(4^m/n)^(n/G)).

The algorithm is particularly advantageous for high girth graphs such as the cage family of graphs.

Practical Performance

The genus for various cage graphs using the adjacency lists from win.tue.nl. Number (# links to adjacency list), valency (k), girth (g), vertices (v), edges (e), size of the automorphism group (|G|), genus, computation time for the genus (time), computation time for the genus using SageMath (SM time), and computation time using multi_genus.c (MG time).

#	k	g	v	e	|G|	genus	time (s)	SM time (s)	MG time (s)
1/1	3	3	4	6	24	0	0.008	0.004	0.006
1/1	3	4	6	9	72	1	0.008	0.039	0.006
1/1	3	5	10	15	120	1	0.008	0.027	0.006
1/1	3	6	14	21	336	1	0.008	0.010	0.006
1/1	3	7	24	36	32	2	0.010	1.737	0.006
1/1	3	8	30	45	1440	4	0.032	118.958	0.012
1/18	3	9	58	87	4	7	1.954	days	29.084
2/18	3	9	58	87	2	7	7.666	days	30.909
3/18	3	9	58	87	24	7	99.05	days	25.993
4/18	3	9	58	87	4	7	2.251	days	54.396
5/18	3	9	58	87	4	7	1.918	days	67.89
6/18	3	9	58	87	2	7	0.436	days	45.310
7/18	3	9	58	87	1	7	1.331	days	37.257
8/18	3	9	58	87	2	7	0.973	days	42.843
9/18	3	9	58	87	1	7	2.137	days	34.437
10/18	3	9	58	87	2	7	0.670	days	86.54
11/18	3	9	58	87	1	7	0.525	days	54.990
12/18	3	9	58	87	2	7	2.439	days	51.589
13/18	3	9	58	87	1	7	3.047	days	32.340
14/18	3	9	58	87	12	7	0.756	days	30.824
15/18	3	9	58	87	8	7	0.992	days	44.888
16/18	3	9	58	87	2	7	0.817	days	57.890
17/18	3	9	58	87	6	7	169.66	days	140.50
18/18	3	9	58	87	6	7	1.083	days	47.737
1/3	3	10	70	105	120	9	36.531	DNF	9354.14
2/3	3	10	70	105	24	9	44.043	DNF	9556.13
3/3	3	10	70	105	80	9	37.058	DNF	10680.89
1/1	3	11	112	168	64	[14, 19]	days	DNF	days
1/1	3	12	126	189	12096	17	254.45	DNF	days
1/1	4	5	19	38	24	4	0.047	days	0.019
1/1	4	6	26	52	11232	6	0.288	DNF	0.013
1/?	4	7	67	134	4	[16, 21]	days	DNF	days
1/1	4	8	80	160	51840	[21, 27]	days	DNF	days
1/?	4	12	728	1456	8491392	[244, 363]	DNF	DNF	too big for bit operations
1/4	5	5	30	75	120	[9, 10]	days	DNF	days
2/4	5	5	30	75	20	[9, 13]	days	DNF	days
3/4	5	5	30	75	30	[9, 14]	days	DNF	days
4/4	5	5	30	75	96	[9, 14]	days	DNF	days
1/1	5	6	42	105	241920	[15, 17]	days	DNF	days
1/1	5	8	170	425	3916800	[76, 126]	DNF	DNF	too big for bit operations
1/?	5	12	2730	6825	503193600	[1480, 2048]	OOM	DNF	too big for bit operations
1/1	6	5	40	120	480	[17, 22]	days	DNF	days
1/1	6	6	62	186	744000	[32, 60]	DNF	DNF	DNF
1/1	6	8	312	936	9360000	[196, 310]	DNF	DNF	too big for bit operations
1/?	6	12	7812	23436	5859000000	[5860, 7810]	OOM	DNF	too big for bit operations
1/1	7	5	50	175	252000	[29, 39]	DNF	DNF	DNF
1/1	7	6	90	315	15120	[61, 110]	DNF	DNF	DNF

The genus for various complete graphs generated using the CompleteGraph function in SageMath follows.

#	k	g	v	e	|G|	genus	time (s)	SM time (s)	MG time (s)
k2	1	Inf	2	1	2	0	---	0.004	---
k3	2	3	3	3	6	0	0.008	0.004	0.008
k4	3	3	4	6	24	0	0.008	0.003	0.008
k5	4	3	5	10	120	1	0.008	0.005	0.008
k6	5	3	6	15	720	1	0.008	0.023	0.008
k7	6	3	7	21	5040	1	0.009	days	0.009
k8	7	3	8	28	40320	2	2.885	DNF	0.008
k9	8	3	9	36	362880	3	days	DNF	0.008

The genus for various complete bipartite graphs generated using the CompleteBipartiteGraph function in SageMath follows. Number (# links to adjacency list), valency (k), girth (g), vertices (v), edges (e), size of the automorphism group (|G|), genus, computation time for the genus (time), and computation time for the genus using SageMath (SM time).

#	k	g	v	e	|G|	genus	time (s)	SM time (s)	MG time (s)
k3-3	3	4	6	9	72	1	0.009	0.047	0.006
k4-4	4	4	8	16	1152	1	0.009	0.010	0.010
k5-5	5	4	10	25	28800	3	0.073	DNF	0.008
k6-6	6	4	12	36	1036800	4	0.015	DNF	0.009

The genus for various complete n-partite graphs generated using the CompleteMultipartiteGraph function in SageMath follows.

#	v	e	genus	time (s)	MG time (s)
k2-2	4	4	0	0.007	0.008
k2-2-2	6	12	0	0.009	0.009
k2-2-2-2	8	24	1	0.008	0.009
k2-2-2-2-2	10	40	3	0.144	0.009

The genus for various Johnson graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
Johnson (5, 2)	10	30	2	0.112	0.009
Johnson (6, 2)	15	60	[4, 5]	hours	hours
Johnson (6, 3)	20	90	[7, 9]	hours	hours
Johnson (8, 4)	70	560	[60,238]	days	too big for bit operations
Johnson (9, 4)	70	560	[148,558]	days	too big for bit operations

The genus for various Circulant graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
C10_1,2,5	10	25	1	0.012	0.007
C10_1,2,4,5	10	35	3	9.164	0.023
C14_1,2,3,6	14	48	4	hours	0.896
C15_1,5	15	30	1	hours	0.006
C16_1,7	16	32	1	0.008	0.014
C18_1,3,9	18	45	4	hours	0.021
C20_1,3,5	20	60	6	0.443	13.698
C20_1,6,9	20	60	6	0.031	20.637
C21_1,4,5	21	63	1	0.008	0.008
C26_1,3,9	26	78	[8, 27]	hours	hours
C30_1,9,11	30	90	[9, 31]	hours	hours
C30_1,4,11,14	30	120	[16, 20]	hours	hours
C31_1,5,6	31	93	1	0.008	0.006
C20_*	20	110	[10, 17]	hours	hours

The genus for various Cyclotomic graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
16	16	40	4	0.513	0.042
19	19	57	1	0.008	0.010
31	31	155	[12,58]	hours	hours
61	61	610	[73,265]	days	too big for bit operations
67	67	737	[91,325]	days	too big for bit operations

The genus for various DifferenceSetIncidence graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
11,5,2	22	55	5	hours	1.770
40,13,4	80	520	[91,214]	hours	too big for bit operations

The genus for various Bipartite Kneser graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
Bipartite Kneser (6, 2)	30	90	[9,28]	days	days
Bipartite Kneser (7, 2)	42	210	[33,80]	days	days
Bipartite Kneser (8, 2)	56	420	[78,175]	days	days
Bipartite Kneser (8, 3)	112	560	[85,143]	days	too big for bit operations
Bipartite Kneser (9, 2)	72	756	[154,332]	days	too big for bit operations
Bipartite Kneser (9, 3)	168	1680	[337,338]	days	too big for bit operations
Bipartite Kneser (10, 2)	90	1260	[271,572]	days	too big for bit operations
Bipartite Kneser (10, 3)	240	4200	[931,1963]	days	too big for bit operations
Bipartite Kneser (10, 4)	420	3150	[579,1358]	days	too big for bit operations
Bipartite Kneser (11, 2)	110	1980	[441,918]	days	too big for bit operations
Bipartite Kneser (11, 3)	330	9240	[2146,4428]	days	too big for bit operations
Bipartite Kneser (11, 4)	660	11550	[2558,5428]	days	too big for bit operations
Bipartite Kneser (12, 2)	132	2970	[677,1397]	days	too big for bit operations
Bipartite Kneser (12, 3)	440	18480	[4401,8979]	days	too big for bit operations
Bipartite Kneser (12, 4)	990	34650	?	adjacency list too large to load	too big for bit operations

The genus for various miscellaneous graphs generated using Mathematica follows.

#	v	e	genus	time (s)	MG time (s)
Klein Bottle	9	27	2	0.152	0.006
TRC	84	126	3	hours	0.006

Acknowledgements

Austin did the main work in deciphering the math and checking the solutions manually. He also contributed intellectually to the ideas behind the algorithm.

The CalcCycles programs were written by Sam King and used to check the results of the algorithm for the Balaban 10 Cage.

Credit to the rest of the recreational math group at the University of Washington for input on the programs/math and for providing computational resources for experimentation.

Thanks to Professor Steinerberger for guidance on the project, and thanks to Professor Brinkmann for providing a fast SoTA algorithm multi_genus to compare against and recommendations for visualizing results.

References

• Adjacency Lists

  • Win.tue.nl
  • SageMath Generators
  • Mathematica
  • ROME and other practical graph datasets

• Genus problem is NP-Hard

  • The graph genus problem is NP-complete
    • The general problem of determining the genus of a graph is NP-hard
  • Triangulating a Surface with a Prescribed Graph
    • Determining the non-orientable genus of a graph is NP-hard

• Background Information

  • Rotation Systems
  • Pearls in Graph Theory - A Comprehensive Introduction - By Nora Hartsfield and Gerhard Ringel (particularly Chapter 10)
  • Topological Graph Theory - A Survey

• Existing Graph Embedding Algorithms

  • Planarity Testing (genus = 0)
    • Efficient Planarity Testing
      • O(V) linear time, successfully implemented in ALGOL and can handle 900+ vertices in less than 12 seconds on 1974 hardware
      • An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
        • Lists flaws and corrections to the original algorithm needed to actually implement it
    • Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
      • Also linear but introduces a cool datastructure called a PQ-tree that is good for handling permutations
    • Depth-First Search and Planarity
      • Linear time, good explanation
    • A Simple Test for Planar Graphs
      • O(V + E), good diagrams/explanation
    • Depth-First Search and Kuratowski Subgraphs
      • Extracts the Kuratowski subgraph in O(V) linear time
    • Graphes Planaires: Reconnaissance et Construction de Representations Planaires Topologiques
      • O(V^2) quadratic time but simple and practical to implement
  • Torus Embedding (genus = 1)
    • Embedding graphs in the torus in linear time
      • Linear time but near impossible to implement
      • Has complicated substeps that require entire papers to prove: Obstructions for simple embeddings
    • An algorithm for embedding graphs in the torus
      • Cubic time but hard to implement
    • A Practical Algorithm for Embedding Graphs on Torus
      • Exponential but has actually been implemented
    • Practical Toroidality Testing
      • Exponential but has actually been implemented in C and C++
      • Scales ok up to 10 vertices (11 with up to 24 edges)
      • Used to find a set of 2K forbidden minors for the torus (biggest at the time of publication)
    • A large set of torus obstructions and how they were discovered
      • Exponential but actually implemented in C. The best practical algorithm for torus embedding so far
  • Projective Plane Embedding (genus = 1, non-orientable)
    • Projective Planarity in Linear Time
      • Linear time but hard to implement
    • Simpler Projective Plane Embedding
      • O(n^2) but much easier to implement
  • Flawed Algorithms
    • Errors in graph embedding algorithms
      • Explains errors in many existing algorithms and how fixing them would make them exponential time
      • Only currently practical algorithms are exponential time
  • Less Efficient Algorithms for Arbitrary Surfaces/Genus
    • SageMath
      • Johnson Trotter to check all rotation systems (exhaustive search with a few optimizations)
      • O(V \prod_{v \in V(G)} (deg(v)-1)!)
    • SAT/ILP
      • A Practical Method for the Minimum Genus of a Graph: Models and Experiments
        • First SAT and ILP implementation
        • Cannot handle genus > 1
      • Stronger ILPs for the Graph Genus Problem
        • Solves most of ROME and NORTH graph datasets
        • 42 hours for the Gray graph (genus 7)
  • Similar Efficiency with Different Trade-Offs
    • A Practical Algorithm for the Computation of the Genus
      • Scales worse with Genus but better with Vertices
  • Theoretically more efficient but Nearly Impossible to Implement
    • A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
      • Linear for fixed genus
      • Has not been implemented correctly in multiple decades
    • A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width
      • Linear for bounded tree-width
      • Simpler than the general for fixed genus
      • Has not been implemented correctly in multiple decades
    • Graph Minors .XIII. The Disjoint Paths Problem
      • Cubic time for fixed genus since checking if one of finitely many obstructions is a minor is cubic time
      • The complete lists of forbidden minors is only known for the plane (genus 0) and projective plane (non-orientable genus 1)

• Obstructions and Forbiddden Minors

  • Graph Minor Theorem
    • The minors can be used to determine if a graph contains an obstruction
  • Kuratowski's theorem
    • 3 short proofs of Kuratowski's theorem
    • A graph is planar if and only if it has no subdivision of K5 or K3,3
  • Graph minors. VIII. A kuratowski theorem for general surfaces
    • Every surface has a finite list of forbidden minors
    • A graph is embeddable in the surface if and only if it has none of these minors
  • A Kuatowsky Theorem for the Projective Plane and 103 Graphs that are irreducible for the projective plan
    • The complete list of 103 forbidden minors for the projective plane
    • A graph is embeddable in the projective plane if and only if it has none of these minors
  • A Kuratowski theorem for nonorientable surfaces
    • Even nonorientable surfaces have a finite list of forbidden minors
    • A graph is embeddable in the nonorientable surface if and only if it has none of these minors
  • Hunting for torus obstructions
    • Largest set at the time ~16K minor order obstructions
    • Split delete method to non-exhaustively search for obstructions
  • A large set of torus obstructions and how they were discovered
    • Exponential but simple torus embedding algorithm based on DMP quardratic time planarity testing algorithm
    • Growing database of torus obstructions: https://webhome.cs.uvic.ca/~wendym/torus/torus_obstructions.html
      • 250,815 torus obstructions, 17,523 of which are minors
      • Possibly complete set for all 3 regular graphs, but likely not complete for all graphs
    • Overview of current progress (split delete, only 11 obstructions that don't have K3,3 as a subgraph)
  • On Computing Graph Minor Obstruction Sets
    • Stopping time of an obstruction algorithm is nonconstructive and other theoretical results

• Cycle Finding Algorithms

  • Finding All the Elementary Circuits of a Directed Graph
    • O((c + 1)(V + E)) = O(cV + cE) time to find all c elementary cycles of a graph
  • A new way to enumerate cycles in graph

• Visualization of Embedding

  • Non-Euclidean Spring Embedders