Algorithms for Coloring Quadtrees

Algorithms for Coloring Quadtrees

0.00 Avg rating0 Votes
Article ID: iaor20121074
Volume: 32
Issue: 1
Start Page Number: 87
End Page Number: 94
Publication Date: Jan 2002
Journal: Algorithmica
Authors: , ,
Keywords: graphical methods, graph coloring, trees
Abstract:

We describe simple linear time algorithms for coloring the squares of balanced and unbalanced quadtrees so that no two adjacent squares are given the same color. If squares sharing sides are defined as adjacent, we color balanced quadtrees with three colors, and unbalanced quadtrees with four colors; these results are both tight, as some quadtrees require this many colors. If squares sharing corners are defined as adjacent, we color balanced or unbalanced quadtrees with six colors; for some quadtrees, at least five colors are required.

Reviews

Required fields are marked *. Your email address will not be published.