Four Color Theorem

[Richard E. Roger]

I have used a program to "four-colour" a map.  You need to be a bit
careful.  The State of New South Wales in Australia has about 7500
parishes (for land administration purposes), and I wanted to colour a GIS
data set representing them.  The program I used first does a swift greedy
pass generating an approximate solution (this took about 30 seconds on a
Sun Ultra 2 with 167 MHz processor, showing how long ago I tried this).  I
thought I'd see how long it would take to generate the full four-colour
solution - in the end, I killed the process after about 3 weeks :-)

Camden, you're right about needing a table showing which polygons border
each other.  My base data set was in an ESRI Arc coverage format, which
meant I could generate and unload the Polygon Adjacency information (using
the "palinfo" command).  I had to sort and remove duplicates and adjust
polygon numbers to eliminate the universal polygon.  I ran this through
the four-colouring program, and ended up with a table listing polygon
numbers with a colour for each polygon (as an integer).  I then joined
this back to the original coverage's attribute data.

For the four-colouring program, I used Michael Trick's "trick.c" program
from

http://mat.gsia.cmu.edu/COLOR/solvers/ .

(Professor Trick is at Carnegie Mellon University.  For further
information, I'd suggest having a look at his home page
(http://mat.gsia.cmu.edu/trick/), and at the operations research site
(www.informs.org) .)

You might also like to look at Professor Joseph Culberson's page at the
University of Alberta (http://www.cs.ualberta.ca/~joe/).

In summary, I wouldn't try doing this for large data sets, and I would not
do it dynamically - add the colouring beforehand via an attribute.  And
consider just doing the initial swift greedy pass to get an approximate
solution - it might be good enough for your purposes.

Finally, does anyone have a program to compute the polygon adjacency
information for polygons in a shapefile ?

Cheers

Richard E. Roger


Dr. R. E. Roger                             NSW Department of
                                         Primary Industries
Spatial Information Officer Systems                    161 Kite St
Resource Information Unit                     Locked Bag 21
                                           ORANGE NSW 2800
ph: (02) 6391 3697                               fax: (02) 6391 3740

------------------------------

Date:    Thu, 6 Jan 2005 10:52:55 -0800
From:    Paul Ramsey <pramsey at REFRACTIONS.NET>
Subject: Re: Four Color Theorem

Google gives a pretty good answer right away, and even an algorithm.

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

Sadly, it is quadratic.

P

Camden Daily wrote:

> Does anyone have any experience in dynamically coloring a map with
> only 4 colors?  I know that it would be easier to just pick out the
> colors myself, but I thought perhaps someone out there might have come
> up with a good mapscript algorithm to do this.
>
> I'd imagine the first step would be constructing a table defining
> which polygons on the map border each other.  Anyone have a good
> method of doing that?
>
> -Camden Daily

This message is intended for the addressee named and may contain
confidential information. If you are not the intended recipient or
received it in error, please delete the message and notify sender. Views
expressed are those of the individual sender and are not necessarily the
views of their organisation.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/mapserver-users/attachments/20050111/15bca27f/attachment.html