Local 7-coloring for planar subgraphs of unit disk graphs Conference Paper

•  
• Overview
•  
• Research
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

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. © 2008 Springer-Verlag Berlin Heidelberg.

authors

• Czyzowicz J.
• Dobrev S.
• González Aguilar Hernán
• Kralovic R.
• Kranakis E.
• Opatrny J.
• Stacho L.
• Urrutia J.

publication date

• 2008-01-01

funding provided via

• Consejo Nacional de Ciencia y Tecnología, CONACYT  Grant
• Mitacs  Grant
• Natural Sciences and Engineering Research Council of Canada, NSERC  Grant

published in

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  Journal

Research

keywords

• Computation theory; Graph algorithms; Graphic methods; Information use; Number of hops; Planar graph; Planar subgraphs; SIMPLE algorithm; Subgraphs; Unit disk graphs; Graph theory

Identity

Digital Object Identifier (DOI)

• 10.1007/978-3-540-79228-4_15

Additional Document Info

start page

• 170

end page

• 181

volume

• 4978 LNCS