The problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph is studied. Each vertex knows its coordinates in the plane, can directly communicate with all its neighbors within unit distance. Using this setting, first a simple algorithm is given whereby each vertex can compute its color in a 9-coloring of the planar graph using only information on the subgraph located within at most 9 hops away from it in the original unit disk graph. A more complicated algorithm is then presented whereby each vertex can compute its color in a 7-coloring of the planar graph using only information on the subgraph located within a constant number of hops away from it.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-540-79228-4-15
Citation
Czyzowicz, J., Dobrev, S., González-Aguilar, H., Kralovic, R., Kranakis, E, Opatrny, J., … Urrutia, J. (2008). Local 7-coloring for planar subgraphs of unit disk graphs. doi:10.1007/978-3-540-79228-4-15