Four Color Theorem

[Stephen Woodbridge]

I think it might not be that hard to compute the polygon adjacency graph
for US Census Tiger data as you have the information about which edges
belong to which polygons, at least within a county. I forget is the
county boundary polygons use the same unique segment ids in adjacent
counties or if there is a duplicate segment with a different unique id.
If the later is the case, you can detect if a segment is a county
boundary, and then you would have to match cloned segment in the
adjacent county by its coordinates.

Darn, yet another interesting problem to code and so little time to code
them ....

-Steve W

Richard E. Roger wrote:
>
> 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.