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

Posted 2 years ago
5551 Views
|
4 Replies
|
22 Total Likes
|

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

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"] It is easy to convert it to a graph.

g = IGMeshGraph[mesh] We could also easily convert it to a face-adjacency graph, or an edge-adjacency graph.

(* face to face adjacency, preserving coordinates *) (* edge to edge adjacency *) ## 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]]
] 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}] 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] 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}
] 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] 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

(* <|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, VertexStyle -> IGMinimumVertexColoring] 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 /@ ## 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] 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]} 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}] 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"]
] 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[]  Attachments: Answer
4 Replies
Sort By:
Posted 2 years ago
 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! Answer
Posted 1 year ago
 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} ]  Answer
Posted 1 year ago
 This is a first experiment for me in inlining a notebook: Answer
Posted 1 year ago -- you have earned Featured Contributor Badge 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! Answer