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, Konstanz, Germany , pp. 62-67 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_6).

Full text not available from this repository.

Abstract

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
ID Code:1194

Repository Staff Only: item control page

References

Angelini, P., Cittadini, L., di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the perspectives opened by right angle crossing drawings. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 21–32. Springer, Heidelberg (2010)

Argyriou, E.N., Bekos, M.A., Symvonis, A.: Maximizing the total resolution of graphs. Technical Report arXiv:/106871 (2010)

Bárány, I., Tokushige, N.: The minimum area of convex lattice n-gons. Combinatorica 24(2), 171–185 (2004)

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. 4, 235–282 (1994)

Cheng, C.C., Duncanyz, C.A., Goodrichz, M.T., Kobourovz, S.G.: Drawing planar graphs with circular arcs. Discrete and Comp. Geometry 25, 117–126 (1999)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H.: Area, curve complexity, and crossing resolution of non-planar graph drawings. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 15–20. Springer, Heidelberg (2010)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009)

Eades, P.: A heuristic for graph drawing. Congressus Numerantium (42), 149–160 (1984)

Formann, M., Hagerup, T., Haralambides, J., Kaufmann, M., Leighton, F., Symvonis, A., Welzl, E., Woeginger, G.: Drawing graphs in the plane with high resolution. SIAM J. Comput. 22(5), 1035–1052 (1993)

Garg, A., Tamassia, R.: Planar drawings and angular resolution: Algorithms and bounds. In: Proc. 2nd Annu. Eur. Sympos. Alg., pp. 12–23 (1994)

Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167–182. Springer, Heidelberg (1999)

Huang, W.: Using eye tracking to investigate graph layout effects. In: Proc. Asia-Pacific Symp. on Visualization, pp. 97–100 (2007)

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: Proc. of the Pacific Visualization Symp., pp. 41–46 (2008)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs: Methods and Models. LNCS, vol. 2025. Springer, Heidelberg (2001)

Lin, C.-C., Yen, H.-C.: A new force-directed graph drawing method based on edge-edge repulsion. In: Proc. of the 9th Int. Conf. on Inf. Vis., pp. 329–334. IEEE, Los Alamitos (2005)

Malitz, S.M., Papakostas, A.: On the angular resolution of planar graphs. In: STOC, pp. 527–538 (1992)