Mercoledì 20 gennaio – Vincenzo Roselli – L-Drawings of Directed Graphs

Posted By on 19 gennaio 2016

=== Quando ===
Mercoledì 20 gennaio alle ore 17:00

=== Dove ===
Dipartimento di ingegneria
Sezione di informatica e automazione
Via della Vasca Navale, 79
Sala riunioni, primo piano

=== Titolo ===
L-Drawings of Directed Graphs

=== Speaker ===
Vincenzo Roselli
Postdoctoral Researcher at Department of Engineering
Roma Tre University
http://www.dia.uniroma3.it/~compunet/www/view/person.php?id=cionzo

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