L-Drawings of Directed Graphs

DOI10.1007/978-3-662-49192-8_11MaRDI QIDQ2794352zbMATH OpenOpenAlexFDO

Authors Patrizio Angelini, Giordano Da Lozzo, Marco di Bartolomeo, Valentino Di Donato, Maurizio Patrignani, Vincenzo Roselli, Ioannis G. Tollis

Publication date 10 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00684

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

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 heuristics 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 heuristics which confirms its effectiveness.

Recommendations

Cited in

(7)

This page was built for publication: L-Drawings of Directed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2794352)