Recap (some facts about maps and coloring):

- All regular maps (3-regular planar graphs) can be topologically transformed (represented) as circular or rectangular maps
- In searching for a solution of the four color problem, it is possible to exclude maps with faces that have less then five neighbours
- Simplified maps (no faces with less than five neighbours) of 13 faces do not exist!
- The nunber of proper colorings (not considering permulations of colors) can be count using the “Chromatic polynomial” and dividing the result by 4! (factorial that counts the permutations). Chromatic polynomial is only known for few types of graphs (Triangle K3, Complete graph Kn, Petersen graph, …)
- Dual graphs derived from maps can be arranged with vertices positioned on a grid (see “Rectangular grid drawings of plane graphs” by Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki)
- …

To implement on the Java application (http://sourceforge.net/projects/maps-coloring):

- Force faces to have fixed colors
- Change swixml2 (http://code.google.com/p/swixml2) to swixml (https://github.com/swixml)
- Change the graphic library G to JTS (http://www.vividsolutions.com/jts/jtshome.htm)
- …

Advertisements