Modular Flip Graphs of Closed Orientable Surfaces

Contrary to flip graphs of planar triangulations like that of a convex polygon, the flip graph of a closed surface is generally infinitely large. Therefore, it is impossible to construct the whole flip graph. Not only are they infinitely large, but they also "grow" very fast. For this reason, it is more interesting and achievable to look at the modular flip graphs. These are graphs whose vertices are homotopy classes of triangulations on closed surfaces.

It turns out that the vertices of modular flip graphs are equivalent to the Δ-coplexes which we have already modeled in DeltaComplex.

Structures

A FlipGraph consists of vertices that represent homotopy classes of DeltaComplexes and edges between them. In order to be able to efficiently compute the whole flip graph, vertices are not DeltaComplexes but have their own structure (FGVertex) which consists of a DeltaComplex with additional information.

FlipGraphs.FlipGraph — Type
struct FlipGraph <: AbstractGraph{Int}

A graph representing the flip graph of a Δ-Complex.

Vertices are isotopy classes of triangulations of the same surface.
Two vertices are linked by an edge, if the respective triangulations differ only by a single flip.

FlipGraphs.FGVertex — Type
struct FGVertex

A vertex in a FlipGraph.

A FGVertex is composed of a representant (DeltaComplex) of the isotopy class of that vertex. The representant has been relabeled with one of the canonical labeling obtained by an adaptation of McKay's Algorithm. Additionally, the FGVertex contains the number of labeling that are output by the respective McKay's Algorithms.

Constructors

Currently, it is only possible to create the modular flip graph of a closed orientable surface. Non-orientable surfaces would need an adapted approach to solving, as the way they are modeled right now would require a lot more options to be checked just to determine if two DeltaComplexes are isomorphic to each other.

As even modular flip graphs become very large quite quickly, you have the possibility of only building a local portion of a flip graph. The way this works is, by giving it a DeltaComplex, which forms the root vertex, and setting the depth, which will limit the vertices to only include those that are at a distance less or equal to this depth from the root.

FlipGraphs.flipgraph_modular — Function
flipgraph_modular(g::Integer, p::Integer; kwargs..) :: FlipGraph

Construct the modular flip graph for a genus g closed orientable surface with p points on it.

Arguments

  • labeled_points :: Bool = true : If set to false, the isomorphism also includes a renaming of the points. 
flipgraph_modular(D::DeltaComplex; kwargs..)

Construct the modular flip graph for the closed orientable surface defined by the Δ-complex D.

Arguments

  • labeled_points :: Bool = true : If is set to false, then the isomorphism also includes a renaming of the points.
  • depth :: Integer = ∞ : Determines the depth to which the flip graph should be constructed. i.e. up to which distance from D.

Graph methods

As with FlipGraphPlanar, there are a bunch of methods which overload some of the main functions from the Graphs.jl package.

Graphs.nv — Method
nv(G::FlipGraph) :: Int

Return the number of vertices in G.

Graphs.ne — Method
ne(G::FlipGraph) :: Int

Return the number of edges in G.

Graphs.vertices — Method
vertices(G::FlipGraph) :: Vector{FGVertex}

Return the list of all the vertices that have been constructed in G.

FlipGraphs.vertices_deltacomplex — Function
vertices_deltacomplex(G::FlipGraph) :: Vector{DeltaComplex}

Construct a list of all the DeltaComplexs which form the vertices in G.

Graphs.edges — Method
edges(G::FlipGraph) :: Vector{Edge}

Construct a list containing all the edges in G.

Graphs.has_vertex — Method
has_vertex(G::FlipGraph, v::Integer) :: Bool

Return true if v is a valid index of a vertex in G.

FlipGraphs.get_vertex — Method
get_vertex(G::FlipGraph, id::Integer) :: Vector{FGVertex}

Return the id-th vertex of the FlipGraph G.

Graphs.has_edge — Method
has_edge(G::FlipGraph, e::Edge) :: Bool

Return true if e is an edge in G.

Graphs.has_edge — Method
has_edge(G::FlipGraph, s::Integer, d::Integer) :: Bool

Return true if there is an edge between the s-th and d-th vertex in G.

Graphs.has_edge — Method
has_edge(G::FlipGraph, v1::FGVertex, v2::FGVertex) :: Bool

Return true if there is an edge between v1 and v2 in G.

Graphs.neighbors — Method
neighbors(G::FlipGraph, v::Integer) :: Vector{Int32}

Return a list of the indices of all the neighboring vertices of the v-th vertex.

FlipGraphs.degree — Method
degree(G::FlipGraph, v::Integer)

Return the degree of the v-th vertex in the graph G.

Comparing Triangulations

One problem in deciding if two triangulations are equivalent, is that the naming of the vertices, edges and points is completely arbitrary. In the act of flipping, DualEdges and TriFaces "move around". It is therefore possible to obtain two DeltaComplexes representing the same triangulation of a surface but with different labeled TriFaces and DualEdges.

The following method will determine if two DeltaComplexes are isomorphic to each other and therefore represent the same vertex in the modular flip graph:

FlipGraphs.is_isomorphic — Method
is_isomorphic(D1::DeltaComplex, D2::DeltaComplex; kwargs..) :: Bool

Return true if D1 is isomorph to D2 up to a renaming of the vertices, edges and if labeled_points=false also points.

Arguments

  • labeled_points :: Bool = true : If labeled_points is set to false, then the isomorphism also includes a renaming of the points.

Canonical labeling of DeltaComplexes

Checking every possible permutation of TriFace and DualEdge labeling was not an option, as the number of possibilities would blow up immediately.

What one can do instead is try to find a canonical labeling. This module uses a version of McKay's canonical graph labeling algorithm[1] to try and determine a unique labeling based on the relationship of vertices and edges to other vertices and edges. In general, it is not always possible to determine a unique labeling. However, with this method, we can reduce the number of labelings to a manageable number.

The mcKay methods each return a permutation vector p which can be interpreted as a Cauchy's one-line notation for permutations. For example, p = [3,5,1,2,6,4] would correspond to the following permutation:

\[σ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 5 & 1 & 2 & 6 & 4 \end{pmatrix} = (1\ 3)(2\ 5\ 6\ 4)\]

This algorithm has been adapted to find canonical labelings for points, vertices and edges. These are not independent from each other. In fact, only the point labelings depend on themselves. mcKayvertices will give different results basedon the point labelings, and mcKayedges will give different results based on both point and vertex labelings. Therefore, they are to be used in sequence.

FlipGraphs.mcKay_points — Function
mcKay_points(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}

Apply a version of McKay's canonical graph labeling algorithm to determine all possible permutations of the points which give a canonical isomorphism class representant.

Return a vector of permutation vectors p such that point 1 becomes point p[1], point 2 becomes point p[2],...

Arguments

  • only_one :: Bool = false, If set to true, the algorithm will stop after finding a single valid permutation.
FlipGraphs.mcKay_vertices — Function
mcKay_vertices(D::DeltaComplex; , A_deltacomplex::Matrix{<:Integer}, point_perm::Vector{<:Integer}) :: Vector{Vector{Int32}}

Apply a version of McKay's canonical graph labeling algorithm in order to determine all possible permutations of the TriFaces which give a canonical isomorphism class representant.

Return a vector of permutation vectors p such that TriFace 1 becomes TriFace p[1], TriFace 2 becomes TriFace p[2], ...
If only_one=true, the algorithm stops after finding one valid permutation.

The vectors point_perm determins how the points of D are implied to have been renamed, without actually having been changed.

mcKay_vertices(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}

Apply a version of McKay's canonical graph labeling algorithm in order to determine all possible permutations of the TriFaces which give a canonical isomorphism class representant.

Return a vector of permutation vectors p such that TriFace 1 becomes TriFace p[1], TriFace 2 becomes TriFace p[2], ...
If only_one=true, the algorithm stops after finding one valid permutation.

Arguments

  • only_one :: Bool = false, If set to true, the algorithm will stop after finding a single valid permutation.
  • A_deltacomplex :: Matrix{<:Integer} = Matrix{Int32}(adjacencymatrixdeltacomplex(D)). If provided, the algorithm will use the adjacency matrix of the DeltaComplex D. If not, the algorithm would have to compute it itself.
FlipGraphs.mcKay_edges — Function
mcKay_edges(D::DeltaComplex; kwargs..) :: Vector{Vector{Int32}}

Apply McKay's canonical graph labeling algorithm in order to determine all possible permutations of the DualEdges which give a canonical isomorphism class representant.

Return a vector of permutation vectors p such that DualEdge 1 becomes DualEdge p[1], DualEdge 2 becomes DualEdge p[2], ...

Arguments

  • only_one :: Bool = false, If set to true, the algorithm will stop after finding a single valid permutation.
  • 1Hartke, S.G., & Radcliffe, A.J. (2008). McKay ’ s Canonical Graph Labeling Algorithm.