A Coloring Algorithm for Disambiguating Graph and Map Drawings - Graph Drawing - page 88

A Coloring Algorithm for Disambiguating Graph
and Map Drawings

Yifan Hu 1 and Lei Shi 2 ,

1

Yahoo Labs, 111 W 40th St, New York, NY 10018, USA
[e-mail]

2

SKLCS, Institute of Software, Chinese Academy of Sciences, China
[e-mail]

Abstract. Drawings of non-planar graphs always result in edge crossings. When
there are many edges crossing at small angles, it is often difficult to follow these
edges, because of the multiple visual paths resulted from the crossingsthatslow
down eye movements. In this paper we propose an algorithm that disambiguates
the edges with automatic selection of distinctive colors. Our proposed algorithm
computes a near optimal color assignment of a dual collision graph, using a
novel branch-and-bound procedure applied to a space decomposition of the color
gamut. We conduct a user study to establish the effectiveness and limitations of
this approach in clarifying drawings of real world graphs and maps.

Keywords: graph drawing, maps, edge coloring, branch-and-bound algorithm.

1 Introduction

Graphs are widely used for depicting relational information among objects. Typically,
graphs are visualized as node-link diagrams [1]. In such a representation, edges are
shown as straight lines, polylines or splines. Graphs that appear in real world applica-
tions are usually non-planar. For such graphs, edge crossings in the layoutareunavoid-
able. It is a commonly accepted principle that the number of edge crossingsshould be
minimized whenever possible, this principle was confirmed by user evaluations which
showed that human performance in path-following is negatively correlated to the num-
berofedge crossings [18,21]. Later studies found that the effect of edge crossingsvaries
with the crossing angle. In particular, the task response time decreases as the crossing
angle increases, and the rate of decrease levels off when the angle is close to 90 de-
gree [14,15]. This implies that it is important not only to minimize the number of edge
crossings, but also to maximize the angle of the crossings. Consequently, generating
drawingsthatgive large crossing angles, or even right crossing angles, became an ac-
tive area of research (e.g., [6]). Nevertheless, for general non-planar graphs, there is
no known algorithm that can guarantee large crossing angles for straight line drawings.
Therefore, techniques to mitigate the adverse visual effect of small angle crossingsare
important in practice.
In this paper we propose to use colors to help differentiate edges. Our starting point
is an existing layout, and our working assumption is that the graph is to be displayed as
Supported by China National 973 project 2014CB340301 and NSFC grant 61379088.