references.md

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