Flip Graphs of Convex Polygons

Flip Graphs, are obtained by considering triangulations on a fixed set of points as vertices, and connecting two vertices, if it is possible to get from one triangulation to the other by flipping a single edge.

Structures

The main structure for this part of the package is the FlipGraphPlanar structure. This implements the AbstractGraph interface from Graphs.jl. It is therefore possible to use it with other packages that work with Graphs.jl.

FlipGraphs.FlipGraphPlanar — Type
struct FlipGraphPlanar <: AbstractGraph{Int32}

A Graph representing the flip graph of a convex polygon.

Vertices are different triangulations of the same convex polygon. Two vertices are linked by an edge, if the respective graphs differ only by a single flip.

Constructors

To construct the flip graph of a convex polygon, you can either start from a TriangulatedPolygon or just set the number of vertices of the triangulated convex polygon.

FlipGraphs.flipgraph — Method
flipgraph(g::TriangulatedPolygon; kwargs..)

Construct the FlipGraph for the TriangulatedPolygon g.

Arguments

  • 'modular::Bool = false' : by default, the whole flip graph is constructed. If modular is set to true, then only the modular flip graph is constructed.

In a modular flip graph, vertices of the flip graph are classes of isomorphisms up to renaming the vertices. Each class is then represented by one of its elements.

FlipGraphs.flipgraph_planar — Function
flipgraph_planar(n::Integer; modular=false) :: FlipGraphPlanar

Construct the FlipGraphPlanar of a convex n-gon.

If modular=true, the flip graph is reduced to its modular form.

Examples

julia> flipgraph_planar(6)
FlipGraphPlanar with 14 vertices and 21 edges

Graph methods

The following methods overload some of the main functions from the Graphs.jl package.

Graphs.nv — Method
nv(G::FlipGraphPlanar)

Return the number of vertices in G.

Graphs.ne — Method
ne(G::FlipGraphPlanar)

Return the number of edges in G.

Graphs.vertices — Method
vertices(G::FlipGraphPlanar)

Return the List of all vertices in G.

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

Construct an array containing all the edges in G.

Graphs.has_vertex — Method
has_vertex(G::FlipGraphPlanar, g::TriangulatedPolygon) :: Bool

Return true if g is a vertex in G.

If G is a modular flip graph, this will only return true if g is the proper representant of the vertex.

Graphs.has_vertex — Method
has_vertex(G::FlipGraphPlanar, i::Integer) :: Bool

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

FlipGraphs.get_vertex — Method
get_vertex(G::FlipGraphPlanar, i::Integer) :: TriangulatedPolygon

Return the i-th vertex in the planar flip graph G.

Graphs.has_edge — Method
has_edge(G::FlipGraphPlanar, s, d)

Return true if there is an edge between s and d in G.

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

Return true if e is an edge in G.

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

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

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

Return a list of all the indices of vertices in G, that are adjacent to v.

Comparing Triangulations

To compute the flip graph, one needs to be able to determine if two triangulations are identical (if the points are labeled) or isomorphic to each other (if the points are unlabeled).
The first case is fairly simple, as two triangulations are identical if their adjacency lists are. The only difficulty here is that the order in the list of neighbors is not fixed.
The second case is more challenging, as there are $n!$ different ways to label $n$ points. The way it is done in this package is to use a variation of McKay's canonical graph labeling algorithm[1] to rattle the number of possible labelings down to a relatively small number.

FlipGraphs.is_isomorphic — Method
is_isomorphic(g1::TriangulatedPolygon, g2::TriangulatedPolygon)

Check if g1 and g2 are isomorphic up to a relabeling of the vertices.

FlipGraphs.is_isomorphic — Method
is_isomorphic(g1::TriangulatedPolygon, g2::TriangulatedPolygon, permutations::Vector{Vector{T}}) where T<:Integer

Check if g2 is isomorphic to g1 up to a relabeling of the vertices by one of the permutations.

The following methods are used to build the flip graph; However, they can also be useful elsewhere:

FlipGraphs.mcKay — Function
mcKay(g::TriangulatedPolygon) :: Vector{Vector{<:Integer}}

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

Return a list of all possible canonical point-relabeling permutations p such that the i-th point should be relabeled as the p[i]-th point

FlipGraphs.rename_vertices — Method
rename_vertices(g::TriangulatedPolygon, p::Vector{<:Integer}) :: TriangulatedPolygon

Return the TriangulatedPolygon obtained from renaming the vertices of the triangulated convex polygon g by applying the permutation p.

FlipGraphs.rename_vertices! — Method
rename_vertices!(g::TriangulatedPolygon, p::Vector{<:Integer}) :: TriangulatedPolygon

Rename the vertices of the triangulated convex polygon g by applying the permutation p.

  • 1Hartke, S.G., & Radcliffe, A.J. (2008). McKay ’ s Canonical Graph Labeling Algorithm.