Wednesday, Jan 20th – Vincenzo Roselli – L-Drawings of Directed Graphs

=== When ===
Wednesday, Jan 20th at 5:00 PM

=== Where ===
Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor

=== Title ===
L-Drawings of Directed Graphs

=== Speaker ===
Vincenzo Roselli
Postdoctoral Researcher at Department of Engineering
Roma Tre University

=== 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.

Joint work with Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Valentino Di Donato, Maurizio Patrignani and Ioannis Tollis.

The paper will be presented at the forthcoming Sofsem 2016 – 42nd International Conference on Current Trends in Theory and Practice of Computer Science – January 23–28, 2016 – Harrachov, Czech Republic