We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive x- and y-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristic based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristic which confirms its effectiveness.
Angelini, P., DA LOZZO, G., DI BARTOLOMEO, M., DI DONATO, V., Patrignani, M., Roselli, V., et al. (2016). L-drawings of directed graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.134-147). Springer Verlag [10.1007/978-3-662-49192-8_11].
L-drawings of directed graphs
ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;DI BARTOLOMEO, MARCO;DI DONATO, VALENTINO;PATRIGNANI, Maurizio;ROSELLI, VINCENZO;
2016-01-01
Abstract
We introduce L-drawings, a novel paradigm for representing directed graphs aiming at combining the readability features of orthogonal drawings with the expressive power of matrix representations. In an L-drawing, vertices have exclusive x- and y-coordinates and edges consist of two segments, one exiting the source vertically and one entering the destination horizontally. We study the problem of computing L-drawings using minimum ink. We prove its NP-completeness and provide a heuristic based on a polynomial-time algorithm that adds a vertex to a drawing using the minimum additional ink. We performed an experimental analysis of the heuristic which confirms its effectiveness.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
