IGraph/M showcase

Installation

If you do not yet have IGraph/M installed, just evaluate the following cell to do it automatically.
In[]:=
Get["https://raw.githubusercontent.com/szhorvat/IGraphM/master/IGInstaller.m"]
The currently installed versions of IGraph/M are: {}
Installing IGraph/M is complete: PacletObject
Name: IGraphM
Version: 0.4
.
It can now be loaded using the command
<<IGraphM`
For more information on how to install or fully uninstall this package (leaving no trace), please go to http://szhorvat.net/mathematica/IGraphM

Showcase

Before we can use it, we must load the package.
In[]:=
Needs["IGraphM`"]
Out[]=
IGraph/M 0.4 (April 2, 2020)
Evaluate
IGDocumentation[]
to get started.

Mesh/graph conversions

Let us take a polyhedral mesh.
In[]:=
mesh=PolyhedronData["TruncatedIcosahedron","BoundaryMeshRegion"]
Out[]=
It is easy to convert it to a graph.
In[]:=
g=IGMeshGraph[mesh]
Out[]=
We could also easily convert it to a face-adjacency graph, or an edge-adjacency graph
In[]:=
(*facetofaceadjacency,preservingcoordinates*)​​IGMeshCellAdjacencyGraph[mesh,2,VertexCoordinatesAutomatic]
Out[]=
In[]:=
(*edgetoedgeadjacency*)​​IGMeshCellAdjacencyGraph[mesh,1]
Out[]=

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.
In[]:=
IGVertexTransitiveQ[g]
Out[]=
True
The same is not true for edges though.
In[]:=
IGEdgeTransitiveQ[g]
Out[]=
False
There are in fact two types of edges: those separating a hexagonal face from a pentagonal one, and those separating two hexagonal faces. We can visualize them:
In[]:=
HighlightGraph[​​g,​​GroupOrbits[IGBlissAutomorphismGroup[g],EdgeList[g]]​​]
Out[]=
How many symmetries (automorphisms) does the graph have?
In[]:=
IGBlissAutomorphismCount[g]
Out[]=
120

Planarity

This is also a planar graph.
We can find all its faces.
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.
We can not only find the faces of this planar graph, we can also compute its dual graph.
Or find a combinatorial embedding, i.e. a counterclockwise ordering of neighbours around each vertex.

Graph colouring

Let us compute a minimum vertex colouring of the dual graph. Since it is planar, we know that it is possible in at most 4 colours.
It was indeed necessary to use 4 colours.
The original graph, however, can be both vertex-coloured and edge-colored using only 3 colours.
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.

Proximity graphs

Earlier, we computed a nice layout for this graph. Can we reconstruct the graph from the coordinates of this layout?
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.
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.
Let us construct a random maze from the Gabriel graph of these points by taking a 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: