Implement coloring algorithm for planar graph

[gwlucastrig]

The Tinfour project would benefit from a class that would assign distinct colors to a planar graph. Currently, the package includes a class for applying Kempe's 6-color assignment algorithm. But appropriate palettes with 6 colors are hard to find (especially when coupled with requirements for printable, grayscale, or color-blind compatibility). Five and four-color palettes are much more common. So an implementation of a 5 color algorithm would be a useful addition to the Tinfour library.

The Tinfour library is written in Java. A suitable solution would not introduce external dependencies beyond those provided by the Java standard API.

Coloring algorithms are a well-known topic (see https://en.wikipedia.org/wiki/Four_color_theorem). For more detail on the 5-color algorithm, see https://en.wikipedia.org/wiki/Five_color_theorem

Special Requirements: We need an algorithm that is compatible and works efficiently with the Tinfour Incremental TIN classes. The current VertexColorizerKempe6 class meets these requirements, but requires 6 distinct colors to complete its work. The original implementation used Kempe 6 because of its relative simplicity, but efficient algorithms for 5-colors are available in published literature. Four-color solutions are also attractive, but may be hard to implement due to their complexity and requirements processing time.

To see examples of suitable palettes for testing and implementation, see Color Brewer

A Caveat:
Having asked for help on this issue, I need to offer one caution. One challenge in this implementation has nothing to do with the actual problem itself, but is all about project management. To date, the Tinfour project has not accepted code from outside contributors. I do not have any experience in handling code contributions or integrating pull requests into the main code branch. So I am sure there will be a few bumps in the road in terms of accepting any contributions. If you are interested in working on this issue, you help is welcome, but I am concerned that there may be a few procedural frustrations for both of us. I apologize in advance for those and hope it won't deter you from working on what I consider a very interesting problem.

Gary

[gwlucastrig]

The image below illustrates the difficulty of coming up with a good six-color palette. It shows a Voronoi Diagram color coded using the VertexColorizerKempe6 class. The palette used to produce the image is from the Color Brewer2 website. The color-assignments works well in a full-color display. But when converted to grayscale (for printing or photocopying), some of the adjacent color areas are assigned similar gray values and are harder to discriminate.

The see why the number of colors in a palette is such an issue, consider the challenges that Cynthia Brewer must have faced when she created the Color Brewer palettes. She needed to balance a selection of colors that looked good together, that were easy for people with dichromatic color blindness to discriminate, that would work well in printed form or on a computer monitor display, and that would reduce well to a grayscale when printed in monochrome. The more colors in a palette, the harder it was for the selection to match all these criteria. You can see this effect when you run the Color Brewer because it lets the user specify different criteria for selecting palettes.

Thus algorithm that could color a set of adjacent features using fewer colors (5 or even 4) would make it easier to produce a palette that worked well when converted.

[micycle1]

Some thoughts:

• The Kempe6 coloriser colors vertices (which lends itself well to colouring voronoi diagrams). Can triangles be colored just as easily? It basically boils down to this: does each triangle have a vertex that is unique to that triangle only? I imagine the answer is no, so is there a way to produce a triangle colouring from a vertex-graph colouring or must the coloriser be applied to another graph whose vertices are triangle circumcenters/centroids?
• As of now, is it straightforward to navigate the tin as a undirected graph of vertices? Is there a need for another class that takes a tin and produces a more suitable graph object which colorizers then work off?
• Colorizers should implement an interface/abstract class.
• Should IncrementalTin support a colorize(Colorizer c) method (rather than calling assignColorsToVertices() on a colorizer object)?

[gwlucastrig]

A couple of quick notes....

I wrote the original Kempe6 graph colorizer in a hurry because I needed it to produce images for my article on Natural Neighbor Interpolation. So I wouldn't hold it up as an example of the best approach.

I think I would prefer a solution in a separate class from IncrementalTin (and SemiVirtualIncrementalTin) because the existing class is already quite large. I have gradually been trying to eliminate anything in that class that isn't intrinsic to managing a Delaunay triangulation. Thus the evolution of separate Interpolators, Neighbor Point Collectors, Point Locators, etc.

My other hope was that someone would come up with an implementation that might be appropriate for general-purpose applications (map coloring, etc.) rather than just Delaunay triangulations. Perhaps there would be a general purpose class that accepted an adjacency table and colorized from that. Tinfour would use that as the "engine" inside a class that operated over a Delaunay.

When I was looking at the problem, I found a couple of sites where people had implemented solutions in Java, but hadn't maintained them. That is part of the natural life span of a software project (I've abandoned one of my own, in fact, so I don't mean that as a condemnation). Initially, I thought that putting such a module into Tinfour would be a good fit. But as I've considered the problem, it looks like the scope of a colorizer would be large enough that it might be better served by its own project on Github.

In classic graph-colorization theory, the adjacency issue is based on connections across edges, not vertices. So the topology of a Delaunay is really quite simple. I suspect that it may have properties that make it very easy to colorize. So I might want to narrow the scope to having a colorizer that was specialized to the Tinfour problem space, simple to implement, and very efficient for the Delaunay.

I am working on a web article describing the Tinfour algorithm for Natural Neighbor Interpolation. To illustrate the connection between Delaunay and Voronoi graphs, I created a colorization for a Delaunay by building a companion graph from the circumcenters of the Delaunay, then used that to assign colors to the triangular faces. The results are shown below.

[micycle1]

I've had success using org.jgrapht.alg.color to produce 3/4/5-colorings of planar graphs. That could be a suitable candidate to introduce as a dependency or integrate the source code into TinFour.

(4-coloring)

(3-coloring)

[gwlucastrig]

Michael,

I am always so impressed by your work. This is just plain cool. I will definitely look at the JGraphT project you recommended.

On a personal note. When I was a kid, my favorite place to visit was the Yale Peabody Museum's hall of dinosaurs. They had a great stegosaurus skeleton. And, to this day, stegosaurus is my favorite dinosaur. So I am particularly pleased to see your "steogonometric mesh structure".