Visual coding by optimal graph-coloring

Abstract

A formal study of visual codings in user interface design is presented. Visual codings for maximum distinction of different objects in displayed images are formulated as a discrete optimization problem of maximum-distance graph-coloring. The formulation is a generalization of the classical coloring problem in graph theory. Having pointed out that maximum-distance graph-coloring is NP-complete, we develop new, fast approximation algorithms for optimal visual codings. The proposed algorthms run inO (M N) time, whereM is the number of visual codes used andN is the number of objects to be encoded. Besides being efficient, the algorithms are simple and easy to implement. Our experiments showed that geographic maps automatically colored by the new algorithms were preferred to those colored by the previous graph-theoretical approach and they are competitive, if not better, in terms of the visual distinction of different regions than those drawn by hand.