The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs

Van Kreveld, Marc (2011) The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 371-376 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_34).

Full text not available from this repository.

Abstract

We study how much better a right-angled crossing (RAC) drawing of a planar graph can be than any planar drawing of the same planar graph. We analyze the area requirement, the edge-length ratio, and the angular resolution. For the first two measures, a RAC drawing can be arbitrarily much better, whereas for the third measure a RAC drawing can be 2.75 times as good.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_34
Classifications:M Methods > M.600 Planar
ID Code:1222

Repository Staff Only: item control page

References

Angelini, P., Cittadini, L., Battista, G.D., 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)

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

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)

Garg, A., Tamassia, R.: Planar drawings and angular resolution: Algorithms and bounds (extended abstract). In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 12–23. Springer, Heidelberg (1994)

Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. SIAM J. Discrete Math. 7(2), 172–183 (1994)