Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles

Fink, Martin and Haunert, Jan-Henrik and Mchedlidze, Tamara and Spoerhase, Joachim and Wolff, Alexander (2012) Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 441-442 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_43).

Full text not available from this repository.


In point-set-embeddability (PSE) problems one is given not just a graph that is to be drawn, but also a set of points in the plane that specify where the vertices of the graph can be placed. The problem class was introduced by Gritzmann et al. [3] twenty years ago. In their work and most other works on PSE problems, however, planarity of the output drawing was an essential requirement. Recent experiments on the readability of drawings [4] showed that polyline drawings with angles at edge crossings close to 90°. and a small number of bends per edge are just as readable as planar drawings. Motivated by these findings, Didimo et al. [2] recently introduced RAC drawings where pairs of crossing edges must form a right angle and, more generally, αAC drawings (for α ∈ (0, 90°]) where the crossing angle must be at least α. As usual, edges may not overlap and may not go through vertices. We investigate the intersection of PSE and RAC/αAC.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_43
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:1278

Repository Staff Only: item control page


Di Giacomo, E., Frati, F., Fulek, R., Grilli, L., Krug, M.: Orthogeodesic point-set embedding of trees. In: Speckmann, B., van Kreveld, M. (eds.) GD 2011. LNCS, vol. 7034, pp. 52–63. Springer, Heidelberg (2011)

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)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Mon. 98, 165–166 (1991)

Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: Proc. 7th Int. IEEE Asia-Pacific Symp. Inform. Visual (APVIS), pp. 41–46 (2008)