Dipartimento d'Ingegneria

Non-planar drawings with large crossing angles In evidenza

Scritto da  Venerdì, 28 Dicembre 2012 18:31
Crossings are considered one of the major factors that reduce the readability of the drawing of a graph. This is not only suggested by intuition but also confirmed by cognitive experiments showing that human performances degrade in the presence of edge crossings. For this reasons the study of planar drawings is a classical subject of investigation in the Graph Drawing field. Unfortunately, the graphs arising from real-world applications are often non-planar and crossings are therefore unavoidable.


On the other hand, recent cognitive experiments have shown that the human understanding of a graph drawing is not inhibited if edge crossings form large angles. These experiments suggest a new and fascinating research scenario in which the goal is to compute non-planar drawings where the smallest angle formed by two crossing edges is maximized. Based on these new ideas, Didimo, Eades and Liotta (WADS 2009, TCS 2011) introduced and studied RAC (Right Angle Crossing) drawings, i.e., drawings of graphs where edges cross forming right angles. After their definition, many papers have been published about RAC drawings, both from the combinatorial and the algorithmic point of view. Relaxations and generalizations of RAC drawings have also been introduced and studied.

Related publications:

- Peter Eades, Giuseppe Liotta, "Right Angle Crossing Graphs and 1-planarity," Discrete Applied Mathematics, on print.

- Emilio Di Giacomo, Walter Didimo, Peter Eades, Seok-Hee Hong, Giuseppe Liotta: Bounds on the crossing resolution of complete geometric graphs. Discrete Applied Mathematics 160(1-2): 132-139 (2012)

- Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, Salvatore Agostino Romeo: Heuristics for the Maximum 2-layer RAC Subgraph Problem. WALCOM 2012: 211-216

- Patrizio Angelini, Luca Cittadini, Walter Didimo, Fabrizio Frati, Giuseppe Di Battista, Michael Kaufmann, Antonios Symvonis: On the Perspectives Opened by Right Angle Crossing Drawings. J. Graph Algorithms Appl. 15(1): 53-78 (2011)

- Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer: Area, Curve Complexity, and Crossing Resolution of Non-Planar Graph Drawings. Theory Comput. Syst. 49(3): 565-575 (2011)

- Walter Didimo, Peter Eades, Giuseppe Liotta: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39): 5156-5166 (2011)

- Emilio Di Giacomo, Walter Didimo, Peter Eades, Giuseppe Liotta: 2-Layer Right Angle Crossing Drawings. IWOCA 2011: 156-169

- Walter Didimo, Peter Eades, Giuseppe Liotta: A characterization of complete bipartite RAC graphs. Inf. Process. Lett. 110(16): 687-691 (2010)

- Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer: Area, Curve Complexity, and Crossing Resolution of Non-planar Graph Drawings. Graph Drawing 2009: 15-20

- Patrizio Angelini, Luca Cittadini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Michael Kaufmann, Antonios Symvonis: On the Perspectives Opened by Right Angle Crossing Drawings. Graph Drawing 2009: 21-32

- Walter Didimo, Peter Eades, Giuseppe Liotta: Drawing Graphs with Right Angle Crossings. WADS 2009: 206-217
Letto 164492 volte Ultima modifica il Giovedì, 17 Luglio 2014 12:39

Lascia un commento

Assicurati di inserire (*) le informazioni necessarie ove indicato.
Codice HTML non è permesso.

NOTA:

Questo sito utilizza i cookies, anche di terze parti, per le statistiche e per agevolare la navigazione nelle pagine del sito. Maggiori informazioni disponibili nell’informativa sulla privacy. Per saperne di piu'

Approvo