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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/978-3-642-28076-4_19 | WALCOM'12 Proceedings of the 6th international conference on Algorithms and computation |
Keywords | DocType | Volume |
various result,planar case,recent experiment,point-set-embedding scenario,curve complexity,problem class,large angle,rac drawing,large-angle crossing,ac drawing,polyline drawing,point-set embeddings,essential requirement,pse problem,right angle,underlying grid,output drawing,drawing style,graph drawing,specified position,computational complexity,planar drawing,data structure | Journal | 7034 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.42 |
References | Authors | |
15 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Fink | 1 | 72 | 6.55 |
Jan-Henrik Haunert | 2 | 179 | 19.32 |
Tamara Mchedlidze | 3 | 136 | 25.56 |
Joachim Spoerhase | 4 | 112 | 14.12 |
Alexander Wolff | 5 | 56 | 5.54 |