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 , pp. 441-442(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_43).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1278

Actions (login required)

View Item View Item