Local 7-coloring for planar subgraphs of unit disk graphs
We study the problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph. Each vertex knows its coordinates in the plane and can communicate directly 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 (201, to be exact) of hops away from it.
|Keywords||Coloring, Location-aware, Planar, Unit disk graph|
|Journal||Theoretical Computer Science|
Czyzowicz, J., Dobrev, S., Gonzlez-Aguilar, H., Kralovic, R., Kranakis, E, Opatrny, J., … Urrutia, J. (2011). Local 7-coloring for planar subgraphs of unit disk graphs. In Theoretical Computer Science (Vol. 412, pp. 1696–1704). doi:10.1016/j.tcs.2010.12.044