Maximizing the Total Resolution of Graphs

Argyriou, Evmorfia and Bekos, Michael and Symvonis, Antonios (2011) Maximizing the Total Resolution of Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 62-67(Official URL:

Full text not available from this repository.


A major factor affecting the readability of a graph drawing is its resolution. In the graph drawing literature, the resolution of a drawing is either measured based on the angles formed by consecutive edges incident to a common node (angular resolution) or by the angles formed at edge crossings (crossing resolution). In this paper, we evaluate both by introducing the notion of total resolution , that is, the minimum of the angular and crossing resolution. To the best of our knowledge, this is the first time where the problem of maximizing the total resolution of a drawing is studied. The main contribution of the paper consists of drawings of asymptotically optimal total resolution for complete graphs (circular drawings) and for complete bipartite graphs (2-layered drawings). In addition, we present and experimentally evaluate a force-directed based algorithm that constructs drawings of large total resolution.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_6
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.720 Straight-line

Actions (login required)

View Item View Item