Geodesic
On the Perspectives Opened by Right Angle Crossing Drawings
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009 , Tome 15 (2011) no. 1, pp. 53-78.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Right Angle Crossing (RAC) drawings are polyline drawings where each crossing forms four right angles. RAC drawings have been introduced because cognitive experiments provided evidence that increasing the number of crossings does not decrease the readability of a drawing if edges cross at right angles. We investigate to what extent RAC drawings can help in overcoming the limitations of widely adopted planar graph drawing conventions, providing both positive and negative results. First, we prove that there exist acyclic planar digraphs not admitting any straight-line upward RAC drawing and that the corresponding decision problem is NP-hard. Also, we show digraphs whose straight-line upward RAC drawings require exponential area. Exploiting the techniques introduced for studying straight-line upward RAC drawings, we also show that there exist planar undirected graphs requiring quadratic area in any straight-line RAC drawing. Second, we study whether RAC drawings allow us to draw bounded-degree graphs with lower curve complexity than the one required by more constrained drawing conventions. We prove that every graph with vertex-degree at most six (at most three) admits a RAC drawing with curve complexity two (resp. one) and with quadratic area. Third, we consider a natural non-planar generalization of planar embedded graphs. Here we give bounds for curve complexity and area different from the ones known for planar embeddings.
DOI : 10.7155/jgaa.00217
Keywords: graph drawing, right angle crossing drawings, upward drawings, non-planar drawings, bounded-degree graphs 
@article{JGAA_2011_15_1_a3,
     author = {Patrizio Angelini and Luca Cittadini and Walter Didimo and Fabrizio Frati and Giuseppe Di Battista and Michael Kaufmann and Antonios Symvonis},
     title = {On the {Perspectives} {Opened} by {Right} {Angle} {Crossing} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {53--78},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2011},
     doi = {10.7155/jgaa.00217},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00217/}
}
TY  - JOUR
AU  - Patrizio Angelini
AU  - Luca Cittadini
AU  - Walter Didimo
AU  - Fabrizio Frati
AU  - Giuseppe Di Battista
AU  - Michael Kaufmann
AU  - Antonios Symvonis
TI  - On the Perspectives Opened by Right Angle Crossing Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2011
SP  - 53
EP  - 78
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00217/
DO  - 10.7155/jgaa.00217
LA  - en
ID  - JGAA_2011_15_1_a3
ER  - 
%0 Journal Article
%A Patrizio Angelini
%A Luca Cittadini
%A Walter Didimo
%A Fabrizio Frati
%A Giuseppe Di Battista
%A Michael Kaufmann
%A Antonios Symvonis
%T On the Perspectives Opened by Right Angle Crossing Drawings
%J Journal of Graph Algorithms and Applications
%D 2011
%P 53-78
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00217/
%R 10.7155/jgaa.00217
%G en
%F JGAA_2011_15_1_a3
Patrizio Angelini; Luca Cittadini; Walter Didimo; Fabrizio Frati; Giuseppe Di Battista; Michael Kaufmann; Antonios Symvonis. On the Perspectives Opened by Right Angle Crossing Drawings. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009
					, Tome 15 (2011) no. 1, pp. 53-78. doi : 10.7155/jgaa.00217. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00217/

Cité par Sources :