Choosing Colors for Geometric Graphs via Color Space Embeddings

Dillencourt, Michael B. and Eppstein, David and Goodrich, Michael T. (2007) Choosing Colors for Geometric Graphs via Color Space Embeddings. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 294-305 (Official URL:

Full text not available from this repository.


Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional step that is often overlooked or ignored: assigning display colors to the graph's vertices. We study the additional aesthetic criterion of assigning distinct colors to vertices of a geometric graph so that the colors assigned to adjacent vertices are as different from one another as possible. We formulate this as a problem involving perceptual metrics in color space and we develop algorithms for solving this problem by embedding the graph in color space. We also present an application of this work to a distributed load-balancing visualization problem.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_29
Classifications:P Styles > P.001 General
ID Code:784

Repository Staff Only: item control page


N. Alon and P. Erdös. Disjoint edges in geometric graphs. Discrete Comput. Geom., 4:287-290, 1989.

M. W. Bern, D. Eppstein, and B. Hutchings. Algorithms for coloring quadtrees. Algorithmica, 32(1):87-94, 2002.

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Macmillan, London, 1976.

C. A. Brewer. Color use guidelines for data representation. In Proc. Section on Statistical Graphics, American Statistical Association, pages 55-60, 1999.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

D. Eppstein. Testing bipartiteness of geometric intersection graphs. In Proc. 15th Symp. Discrete Algorithms, pages 853-861. ACM and SIAM, 2004.

S. Felsner, F. Hurtado, M. Noy, and I. Streinu. Hamiltonicity and colorings of arrangement graphs. In Proc. 11th Symp. Discrete Algorithms, pages 155-164. ACM and SIAM, 2000.

C. G. Healey. Choosing effective colours for data visualization. In R. Yagel and G. M. Nielson, editors, IEEE Visualization '96, pages 263-270, 1996.

M. Jünger and P. Mutzel. Graph Drawing Software. Springer, 2003.

M. Kaufmann and D. Wagner. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

P. Lee and Z. M. Kedem. Automatic data and computation decomposition on distributed memory parallel computers. ACM Trans. Programming Languages and Systems, 24(1):1-50, 2002.

H. Levkowitz and G. T. Herman. Color scales for image data. IEEE Computer Graphics and Applications, 12(1):72-80, 1992.

T. Nishizeki. Planar Graph Drawing, volume 12 of LNSC. World Scientific, 2004.

L. Pan, M. K. Lai, K. Noguchi, J. J. Huseynov, L. F. Bic, and M. B. Dillencourt. Distributed parallel computing using Navigational Programming. Int. J. Parallel Programming, 32(1):1-37, 2004.

L. Pan, J. Xue, M. K. Lai, L. Bic, M. B. Dillencourt, and L. Bic. Toward automatic data distributions for migrating computations. Submitted for publication, 2006.

P. Rheingans and B. Tebbs. A tool for dynamic explorations of color mappings. Computer Graphics, 24(2):145-146, 1990.

P. K. Robertson. Visualizing color gamuts: A user interface for the effective use of perceptual color spaces in data displays. IEEE Computer Graphics and Applications, 8(5):50-64, 1988.

Y. Rubner, J. Puzicha, C. Tomasi, and J. M. Buhmann. Empirical evaluation of dissimilarity measures for color and texture. Computer Vision and Image Understanding, 84:25-43, 2001.

M. Stokes, M. Anderson, S. Chandrasekar, and R. Motta. A Standard Default Color Space for the Internet - sRGB. Available online at, 1996.

M. Stone. A Field Guide to Digital Color. Morgan Kaufmann, 2nd edition, 2003.

E. R. Tufte. The Visual Display of Quantative Information. Graphics Press, Cheshire, Connecticut, 1983.

E. R. Tufte. Envisioning Information. Graphics Press, Cheshire, Connecticut, 1990.

C. Ware. Color sequences for univariate maps: Theory, experiments, and principles. IEEE Computer Graphics and Applications, 8(5):41-49, 1988.