Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. wireless networks 7, 609–616 (2001)
Caragiannis, I., Fishkin, A.V., Kaklamanis, C., Papaioannou, E.: A tight bound for online coloring of disk graphs. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 78–88. Springer, Heidelberg (2005)
Chavez, E., Dobrev, S., Kranakis, E., Opatrny, J., Stacho, L., Urrutia, J.: Local construction of planar spanners in unit disk graphs with irregular transmission ranges. In: Cardoso, J., Sheth, A.P. (eds.) SWSWPC 2004. LNCS, vol. 3387, pp. 286–297. Springer, Heidelberg (2005)
Dörre, P.: Every planar graph is 4-colourable and 5-choosable a joint proof. Fachhochschule Südwestfalen (University of Applied Sciences) (unpublished note)
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Systemic Zoology 18, 259–278 (1972)
Ghosh, S., Karaata, M.H.: A self-stabilizing algorithm for coloring planar graphs. Distributed Computing 7, 55–59 (1993)
Gräf, A., Stumpf, M., Weißenfels, G.: On coloring unit disk graphs. Algorithmica 20(3), 277–293 (1998)
Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. of 11th Canadian Conference on Computational Geometry, August 1999, pp. 51–54 (1999)
Linial, N.: Locality in distributed graph algorithms. SIAM J. COMP. 21(1), 193–201 (1992)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25(1), 59–68 (1995)
Miyamoto, Y., Matsui, T.: Multicoloring unit disk graphs on triangular lattice points. In: SODA, pp. 895–896. SIAM, Philadelphia (2005)
Thomassen, C.: Every planar graph is 5-choosable. Combinatorial Theory Series B 62(1), 180–181 (1994)
Tuza, Z., Voigt, M.: A note on planar 5-list colouring: non-extendability at distance 4. Discrete Mathematics 251(1), 169–172 (2002)
Wang, Y., Li, X.-Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czyzowicz, J. et al. (2008). Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2008. Lecture Notes in Computer Science, vol 4978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79228-4_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-79228-4_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79227-7
Online ISBN: 978-3-540-79228-4
eBook Packages: Computer ScienceComputer Science (R0)