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 adjacency 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-hardness 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., Lozzo, G.D., Bartolomeo, M.D., Donato, V.D., Patrignani, M., Roselli, V., et al. (2018). Algorithms and Bounds for L-Drawings of Directed Graphs. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(4), 461-480 [10.1142/S0129054118410010].

Algorithms and Bounds for L-Drawings of Directed Graphs

Angelini, Patrizio;Lozzo, Giordano Da;Bartolomeo, Marco Di;Donato, Valentino Di;Patrignani, Maurizio
;
Roselli, Vincenzo;
2018-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 adjacency 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-hardness 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.
2018
Angelini, P., Lozzo, G.D., Bartolomeo, M.D., Donato, V.D., Patrignani, M., Roselli, V., et al. (2018). Algorithms and Bounds for L-Drawings of Directed Graphs. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 29(4), 461-480 [10.1142/S0129054118410010].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/337831
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 4
social impact