Algorithms for coloring quadtrees

DOI10.1007/S00453-001-0054-2MaRDI QIDQ5956834zbMATH OpenOpenAlexFDO

Authors David Eppstein, M. W. Bern, B. Hutchings

Publication date 23 October 2002

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/9907030

zbMATH Keywords

four-color theoremgraph coloringquadtrees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

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.

Recommendations

• scientific article; zbMATH DE number 2089998
• Approximation Algorithms for Path Coloring in Trees
• scientific article; zbMATH DE number 2089961
• COLORING ALGORITHMS ON SUBCUBIC GRAPHS
• Algorithmic aspects of the maximum colorful arborescence problem
• Algorithm for the cost edge-coloring of trees
• scientific article; zbMATH DE number 1796973
• scientific article; zbMATH DE number 3898919
• Graph colouring algorithms
• scientific article; zbMATH DE number 6724468

Cited in

(8)

• Cropped quad-tree based solid object colouring with CUDA
• A quadratic algorithm for road coloring
• Some results of Christos Papadimitriou on internet structure, network routing, and web information
• Computing and Combinatorics
• scientific article; zbMATH DE number 6724468 (Why is no real title available?)
• Efficient approximation algorithms for clustering point-sets
• Diamond-kite meshes: adaptive quadrilateral meshing and orthogonal circle packing
• Coloring octrees

This page was built for publication: Algorithms for coloring quadtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956834)