Minimal Coloring of Planar Graphs

Find a minimal coloring of the faces of a planar graph, including or excluding the outer face

This example shows two methods for finding a minimal coloring of the faces of a planar graph. First, we review the built-in approach for finding a minimal coloring using

FindPlanarColoring

. This method includes the outer face of the graph, that is, the face that outlines the graph on the plane, in the computation. Then we implement custom functions to find a minimal coloring that ignores the outer face.

Define a planar graph:

In[1]:=

;

List the faces of the planar graph:

In[2]:=

faces=PlanarFaceList[g];faces//Shallow

Out[2]//Shallow=

{{1,2,10,11,3},{1,3,4,13,27,28,14,5},{1,5,6,9,2},{2,9,22,23,10},{3,11,24,12,4},{4,12,25,26,13},{5,14,29,15,6},{6,15,16,8,21,35,22,9},{7,8,16,30,17},{7,17,18,19,20},30}

Define an association pairing vertex names and coordinates:

In[3]:=

coords=AssociationThread[VertexList[g]GraphEmbedding[g]];coords//Shallow

Out[3]//Shallow=

1{0.12072,-0.202516},2{0.00247064,-0.167531},3{0.0827857,-0.251071},4{0.12631,-0.302022},5{0.183482,-0.161382},6{0.113648,-0.0786369},7{0.03642,0.0615696},8{0.0208982,0.00933036},9{0.00576321,-0.0981154},10{-0.118803,-0.202855},66

Find a minimal coloring of the graph, including the outer face:

In[4]:=

colors=FindPlanarColoring[g,ColorData[106,"ColorList"]]

Out[4]=





Apply the coloring to the graph:

In[5]:=

Graphics[ReverseSortBy[KeyValueMap[Style[Polygon[#1],#2]&,AssociationThread[faces/.coords,colors]],Area[First[#]]&]]

Out[5]=

We apply reverse sorting by area to prevent the outer face of the planar graph from overlapping with any other faces.

The fact that

FindPlanarColoring

accounts for the outer face by default can be a limitation. Suppose

is a 10×10 grid graph. When we ask for the minimal coloring of

, it's likely that we expect to color the checkerboard faces, and that we don't consider that the outer face (the outline of the board itself) is a face to be colored. Failing to consider this, and reusing the technique above to color

, the result appears sub-optimal:

Define a grid graph:

In[6]:=

g=GridGraph[{1,1}10,ImageSizeTiny]

Out[6]=

Find the faces of g, coordinates of g' s vertices and a planar coloring of g:

In[7]:=

faces=PlanarFaceList[g];coords=AssociationThread[VertexList[g]GraphEmbedding[g]];colors=FindPlanarColoring[g,ColorData[106,"ColorList"]];

Visualize the resulting colored graph:

In[8]:=

Graphics[ReverseSortBy[KeyValueMap[Style[Polygon[#1],#2]&,AssociationThread[faces/.coords,colors]],Area[First[#]]&],ImageSizeSmall]

Out[8]=

In fact, this result really is a minimal coloring only if one includes the outer face in the list of faces that must be colored. In the plot, that outer face is behind all the other faces, and is blue. With that said, it's still not the coloring we likely expected. And a checkerboard is obviously two-colorable, so how can we omit the outer face from the computation?

The first step is identifying the outer face on

. Since the outer face on any planar graph always contains all other (inner) faces, it must be the largest in area. We can easily write a function to retrieve the face with the largest area from a given planar graph, as follows:

In[9]:=

ClearAll[findOuterFace]findOuterFace[g_Graph?PlanarGraphQ]:=With {coords=AssociationThread[VertexList[g]GraphEmbedding[g]]}, First[TakeLargestBy[PlanarFaceList[g],Area[Polygon[#/.coords]]&,1]]

In[10]:=

findOuterFace[g]

Out[10]=

{1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100,99,98,97,96,95,94,93,92,91,81,71,61,51,41,31,21,11}

The dual of a planar graph

converts the faces of

to vertices. These vertices are connected wherever a pair of faces in

are separated from each other by an edge. Finding a minimal vertex coloring of the dual of

is therefore equivalent to finding a minimal coloring of the faces of

There is, therefore, a fairly straightforward solution to our problem: to find a minimal coloring of the faces of

, excluding the outer face, simply delete the vertex corresponding to the outer face from the dual of

, and find a minimal vertex coloring of the resulting graph. This coloring will fit the faces of

perfectly, excluding the outer face.

Visualize the dual of

and the dual of

after deleting the outer face vertex:

In[11]:=

GraphicsRow[{DualPlanarGraph[g,ImageSizeSmall,PlotLabel"Dual of g \n(3-colorable)"],VertexDelete[DualPlanarGraph[g,ImageSizeSmall],findOuterFace[g],PlotLabel"Dual of g with the outer face \nvertex removed (2-colorable)"]}]

Out[11]=

Let's define a simple function to perform the operation.

Define and use a function to find a minimal coloring of the graph, not including the outer face:

In[12]:=

findNoOuterFacePlanarColoring[g_Graph?PlanarGraphQ,colors_:ColorData[106,"ColorList"]]:=FindVertexColoring[VertexDelete[DualPlanarGraph[g],findOuterFace[g]],colors]

In[13]:=

findNoOuterFacePlanarColoring[g]

Out[13]=





Apply the coloring to the graph:

In[14]:=

Graphics[ReverseSortBy[KeyValueMap[Style[Polygon[#1],#2]&,AssociationThread[DeleteCases[faces,findOuterFace[g]]/.coords,findNoOuterFacePlanarColoring[g]]],Area[First[#]]&],ImageSizeSmall]

Out[14]=

We can package up the process of finding and applying a minimal coloring that does not include the outer face into a function like this:

In[15]:=

ClearAll[noOuterFacePlanarColoringPlot]noOuterFacePlanarColoringPlot[g_Graph?PlanarGraphQ]:=Graphics[ReverseSortBy[KeyValueMap[Style[Polygon[#1],#2]&,AssociationThread[DeleteCases[PlanarFaceList[g],findOuterFace[g]]/.AssociationThread[VertexList[g]GraphEmbedding[g]],findNoOuterFacePlanarColoring[g]]],Area[First[#]]&],ImageSizeSmall]

By mapping this function over a list of planar graphs, we can easily produce minimal colorings of any planar graph we choose:

Define a list of planar graphs:

Find and apply minimal face colorings to these graphs:

Publisher Information

Contributed by: Phileas Dazeley-Gaist

Wolfram Language Example Repository

Minimal Coloring of Planar Graphs

See Also

Publisher Information

Minimal Coloring of Planar Graphs

See Also

Related Symbols

Publisher Information