Message Boards Message Boards

IGraph/M showcase: meshes, planarity, symmetry, colouring

Posted 5 years ago

This post showcases a few features of the IGraph/M graph theory and network analysis package. All examples are included in the attached notebook.

Installation

If you do not yet have IGraph/M installed (or don't have the latest version), just evaluate the following to do it automatically.

Get["https://raw.githubusercontent.com/szhorvat/IGraphM/master/IGInstaller.m"]

For more information on how to install or fully uninstall this package (leaving no trace), please go to http://szhorvat.net/mathematica/IGraphM

Loading

Before we can use it, we must load the package.

Needs["IGraphM`"]

Mesh/graph conversions

Let us take a polyhedral mesh.

mesh = PolyhedronData["TruncatedIcosahedron", "BoundaryMeshRegion"]

Truncated icosahedral mesh

It is easy to convert it to a graph.

g = IGMeshGraph[mesh]

Truncated icosahedron skeleton graph

We could also easily convert it to a face-adjacency graph, or an edge-adjacency graph.

(* face to face adjacency, preserving coordinates *)
IGMeshCellAdjacencyGraph[mesh, 2, VertexCoordinates -> Automatic]

Face-face adjacency graph

(* edge to edge adjacency *)
IGMeshCellAdjacencyGraph[mesh, 1]

Edge-edge adjacency graph

Graph symmetries

This is a very symmetric graph. The graph structure looks exactly the same when viewed from any vertex. In other words, the graph is vertex-transitive.

IGVertexTransitiveQ[g]
(* True *)

The same is not true for edges though.

IGEdgeTransitiveQ[g]
(* False *)

There are in fact two distinct types of edges: those separating a hexagonal face from a pentagonal one, and those separating two hexagonal faces. We can visualize them:

HighlightGraph[
 g,
 GroupOrbits[IGBlissAutomorphismGroup[g], EdgeList[g]]
 ]

Edge classes based on graph automorphism

How many symmetries (automorphisms) does the graph have? We can easily count with the IGBlissAutomorphismCount function.

IGBlissAutomorphismCount[g]
(* 120 *)

Planarity

This is also a planar graph.

IGPlanarQ[g]
(* True *)

We can find all its faces.

IGFaces[g]

(* {{1, 41, 47, 31, 6, 10}, {1, 10, 15, 27, 59}, {1, 59, 9, 23, 19, 
  41}, {2, 42, 20, 24, 11, 60}, {2, 60, 28, 16, 12}, {2, 12, 8, 32, 
  48, 42}, {3, 57, 5, 13, 25, 43}, {3, 43, 49, 15, 10, 6}, {3, 6, 31, 
  21, 57}, {4, 44, 26, 14, 7, 58}, {4, 58, 22, 32, 8}, {4, 8, 12, 16, 
  50, 44}, {5, 57, 21, 33, 29, 56}, {5, 56, 7, 14, 13}, {7, 56, 29, 
  34, 22, 58}, {9, 53, 11, 24, 23}, {9, 59, 27, 51, 30, 53}, {11, 53, 
  30, 52, 28, 60}, {13, 14, 26, 36, 35, 25}, {15, 49, 37, 39, 51, 
  27}, {16, 28, 52, 40, 38, 50}, {17, 18, 55, 46, 45, 54}, {17, 54, 
  47, 41, 19}, {17, 19, 23, 24, 20, 18}, {18, 20, 42, 48, 55}, {21, 
  31, 47, 54, 45, 33}, {22, 34, 46, 55, 48, 32}, {25, 35, 37, 49, 
  43}, {26, 44, 50, 38, 36}, {29, 33, 45, 46, 34}, {30, 51, 39, 40, 
  52}, {35, 36, 38, 40, 39, 37}} *)

Each list in the result contains the ordered vertices of a face.

We can also compute a Tutte layout of the graph, with an arbitrary choice of outer face. A planar graph can be drawn with any of its faces being the outer face.

IGLayoutTutte[g, "OuterFace" -> {4, 58, 22, 32, 8}]

Tutte layout

In a typical Tutte layout, the vertices are often closely packed in the middle. It would be nice to space them out. IGLayoutTutte supports edge weights. We can simply compute an initial layout, then assign the Euclidean distance of each edge's endpoints as its weight, finally compute a weighted Tutte layout.

IGLayoutTutte@IGDistanceWeighted@IGLayoutTutte[g]

Weighted Tutte layout

We can even transform the edge weights to adjust between a closely spaced and a loosely spaced layout. This is easy with IGEdgeMap.

Manipulate[
 IGLayoutTutte@
  IGEdgeMap[#^alpha &, EdgeWeight]@IGDistanceWeighted@IGLayoutTutte[g],
 {{alpha, 1}, 0.5, 2}
 ]

Manipulated Tutte layout

While Mathematica has GraphLayout->"TutteEmbedding" built in, selecting the desired outer face or using weights is only possible with IGraph/M.

We can not only find the faces of this planar graph, we can also compute its dual graph.

dualG = IGDualGraph[g]

Dual graph

Or find a combinatorial embedding, i.e. a counterclockwise ordering of neighbours around each vertex.

IGPlanarEmbedding[g]

(* <|1 -> {41, 10, 59}, 2 -> {42, 60, 12}, 3 -> {57, 43, 6}, 
 4 -> {44, 58, 8}, 5 -> {13, 57, 56}, 6 -> {3, 10, 31}, 
 7 -> {58, 14, 56}, 8 -> {4, 32, 12}, 9 -> {53, 23, 59}, 
 10 -> {6, 15, 1}, 11 -> {53, 60, 24}, 12 -> {8, 2, 16}, 
 13 -> {5, 14, 25}, 14 -> {13, 7, 26}, 15 -> {10, 49, 27}, 
 16 -> {12, 28, 50}, 17 -> {18, 54, 19}, 18 -> {17, 20, 55}, 
 19 -> {17, 41, 23}, 20 -> {18, 24, 42}, 21 -> {57, 31, 33}, 
 22 -> {32, 58, 34}, 23 -> {19, 9, 24}, 24 -> {23, 11, 20}, 
 25 -> {13, 35, 43}, 26 -> {14, 44, 36}, 27 -> {15, 51, 59}, 
 28 -> {16, 60, 52}, 29 -> {33, 34, 56}, 30 -> {52, 53, 51}, 
 31 -> {21, 6, 47}, 32 -> {22, 48, 8}, 33 -> {29, 21, 45}, 
 34 -> {29, 46, 22}, 35 -> {25, 36, 37}, 36 -> {35, 26, 38}, 
 37 -> {35, 39, 49}, 38 -> {36, 50, 40}, 39 -> {37, 40, 51}, 
 40 -> {39, 38, 52}, 41 -> {19, 47, 1}, 42 -> {20, 2, 48}, 
 43 -> {25, 49, 3}, 44 -> {26, 4, 50}, 45 -> {33, 54, 46}, 
 46 -> {45, 55, 34}, 47 -> {41, 54, 31}, 48 -> {42, 32, 55}, 
 49 -> {43, 37, 15}, 50 -> {44, 16, 38}, 51 -> {39, 30, 27}, 
 52 -> {40, 28, 30}, 53 -> {30, 11, 9}, 54 -> {47, 17, 45}, 
 55 -> {48, 46, 18}, 56 -> {29, 7, 5}, 57 -> {21, 5, 3}, 
 58 -> {22, 4, 7}, 59 -> {27, 9, 1}, 60 -> {28, 2, 11}|> *)

Combinatorial embeddings are the fundamental object used to compute things such as the faces of a planar graph. They can also represent embeddings in surfaces of a different topology, such as a torus.

We can compute an embedding from an arbitrary set of vertex coordinates of a non-planar graph such as $K_5$, e.g.

emb = IGCoordinatesToEmbedding@IGCompleteGraph[5]

(* <|1 -> {5, 4, 3, 2}, 2 -> {1, 5, 4, 3}, 3 -> {5, 4, 2, 1}, 4 -> {3, 2, 1, 5}, 5 -> {4, 3, 2, 1}|> *)

We can then get the faces: IGFaces[emb]. Using the number of faces, we can get the Euler characteristic and the genus of the corresponding surface:

The Euler characteristic:

With[{g = IGAdjacencyGraph[emb]},
 chi = VertexCount[g] - EdgeCount[g] + Length@IGFaces[emb] (* Euler's formula *)
 ]
(* -2 *)

The genus:

genus = 1 - chi/2
(* 2 *)

$K_5$ can be embedded in a surface of genus 1 as well, but this particular embedding is for a surface of genus 2.

Graph colouring

Let us compute a minimum vertex colouring of the dual graph of g. Since it is planar, we know that it is possible in at most 4 colours.

Graph3D[dualG, VertexSize -> Large] // 
 IGVertexMap[ColorData[100], VertexStyle -> IGMinimumVertexColoring]

Vertex colouring

It was indeed necessary to use 4 colours.

IGChromaticNumber[dualG]
(* 4 *)

The original graph, however, can be both vertex-coloured and edge-colored using only 3 colours.

{IGChromaticNumber[g], IGChromaticIndex[g]}
(* {3, 3} *)

The vertex colouring of the dual graph of a polyhedral skeleton is actually a face colouring of the polyhedron. Let us visualize the colouring like this.

SetProperty[{mesh, {2, All}}, 
 MeshCellStyle -> 
  ColorData[100] /@ 
   IGMinimumVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2]]

Face-coloured polyhedron

Proximity graphs

Earlier, we computed a nice layout for this graph. Can we reconstruct the graph from the coordinates of this layout?

pts = GraphEmbedding@IGLayoutTutte@IGDistanceWeighted@IGLayoutTutte[g];

ListPlot[pts, AspectRatio -> Automatic]

Vertex coordinates

The concept of the relative neighbourhood graph was developed to model human perception of a set of points. Let us compute both this graph, and the Gabriel graph.

{IGRelativeNeighborhoodGraph[pts], IGGabrielGraph[pts]}

Relative neighbourhood graph and Gabriel graph

The connections we get this way are not the same as the original graph, but at least in the middle of the point set, the connections are reconstructed well.

?-skeletons are proximity graphs that interpolate smoothly between the two graphs above, and beyond.

Manipulate[IGLuneBetaSkeleton[pts, beta], {beta, 0.5, 3}]

Beta skeleton

Let us construct a random maze from the Gabriel graph of these points by taking a random spanning tree.

With[{gg = IGGabrielGraph[pts]},
 IGRandomSpanningTree[gg, VertexCoordinates -> GraphEmbedding[gg],
  GraphStyle -> "ThickEdge"]
 ]

Random spanning tree

An exact definition of all of these proximity graphs used above is found in the IGraph/M documentation. Open it to see many more functions with many more examples by evaluating:

IGDocumentation[]

IGraph/M documentation

Attachments:
POSTED BY: Szabolcs Horvát
4 Replies

enter image description here -- you have earned Featured Contributor Badge enter image description here

Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team

This is a first experiment for me in inlining a notebook:

POSTED BY: Szabolcs Horvát

This is a small tiling explorer with IGraph/M, just for fun :-)

Needs["IGraphM`"]

colorMesh[colNum_][mesh_] := 
 SetProperty[{MeshRegion[mesh, 
    MeshCellStyle -> {1 -> Directive[White, Thick]}], {2, All}}, 
    MeshCellStyle -> ColorData[colNum] /@ IGMinimumVertexColoring@IGMeshCellAdjacencyGraph[mesh, 2]
]

Manipulate[
 colorMesh[colorScheme]@IGLatticeMesh[lattice, Disk[{0, 0}, 10.0], ImageSize -> Large],
 {lattice, IGLatticeMesh[]},
 {{colorScheme, 97}, 1, 114, 1}
]

enter image description here

POSTED BY: Szabolcs Horvát

Your passion for this project clearly shines through, Szabolcs! Thank you for sharing the fruits of your many (many, many) hours of labor. All the best!

POSTED BY: Todd Allen
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract