Generalized map coloring for use in geographical information systems

We propose a new model for cartographic map coloring for use in Geographical Information Systems. Map coloring motivated the famous four-color problem in Mathematics. The published proofs of the four-color theorem yield impractical polynomial-time algorithms. Actual political maps often require generalizations to the standard four-coloring problem given the topology of some regions. We allow each region to have m disjoint pieces, which is Heawood's m -pire problem. We also count node adjacency between regions, i.e., two regions are adjacent if they share a common point. The adjacency graphs using node adjacency are known as map graphs. By combining m -pires with node and island adjacency, we formulate a new model to handle actual GIS instances. We implemented Brelaz's Dsatur heuristic, since no specific algorithm exists for coloring our resulting cartographic graphs . The choice works well in practice and we discuss the details of the implementation in TransCAD®.