Search Results

Documents authored by Liotta, Giuseppe

Document
DOI: 10.4230/LIPIcs.GD.2025.8
Tangling and Untangling Trees on Point-Sets

Authors: Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, and Ioannis G. Tollis

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set S of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let T be a tree, ϑ(T) be its thrackle number, and χ be any integer in the interval [0,ϑ(T)]. In the tangling phase we compute a topological linear embedding of T with ϑ(T) edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach χ crossings. The computed linear embedding is used to construct a drawing of T on S with χ crossings and constant curve complexity. Our approach gives rise to an O(n²)-time algorithm for general trees and an O(n log n)-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are π/2.
Cite as

Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, and Ioannis G. Tollis. Tangling and Untangling Trees on Point-Sets. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dibattista_et_al:LIPIcs.GD.2025.8,
  author =	{Di Battista, Giuseppe and Liotta, Giuseppe and Patrignani, Maurizio and Symvonis, Antonios and Tollis, Ioannis G.},
  title =	{{Tangling and Untangling Trees on Point-Sets}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.8},
  URN =		{urn:nbn:de:0030-drops-249947},
  doi =		{10.4230/LIPIcs.GD.2025.8},
  annote =	{Keywords: Tree drawings, Prescribed edge crossings, Thrackle, Curve complexity, Point-set embeddings, RAC drawings, Topological linear embeddings}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.13
Separability of Witness Gabriel Drawings

Authors: Carolina Haase, Philipp Kindermann, William Lenhart, and Giuseppe Liotta

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A witness Gabriel drawing Γ is a straight-line drawing of a graph in which any two vertices of Γ are adjacent if and only if the disk having these vertices as antipodal points contains no element of a special set of points called witnesses. A witness Gabriel drawing is linearly separable if the vertices and the witnesses lie in opposite half-planes. We prove that every outerplanar graph has a linearly separable witness Gabriel drawing by introducing and studying a new type of drawing that we call a border parabola drawing. We then use border parabola drawings to characterize those triangle-free graphs that admit a linearly separable witness Gabriel drawing. We also consider witness Gabriel drawings where no witness lies in the interior of the convex hull of the vertex set, which we call convexly separable drawings. We construct witness Gabriel drawable graphs for which any witness Gabriel drawing must be convexly separable and that do not admit any linearly separable witness Gabriel drawing.
Cite as

Carolina Haase, Philipp Kindermann, William Lenhart, and Giuseppe Liotta. Separability of Witness Gabriel Drawings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haase_et_al:LIPIcs.GD.2025.13,
  author =	{Haase, Carolina and Kindermann, Philipp and Lenhart, William and Liotta, Giuseppe},
  title =	{{Separability of Witness Gabriel Drawings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.13},
  URN =		{urn:nbn:de:0030-drops-249998},
  doi =		{10.4230/LIPIcs.GD.2025.13},
  annote =	{Keywords: Proximity Drawings, Witness Gabriel Graphs, Geometric Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.18
Internally-Convex Drawings of Outerplanar Graphs in Small Area

Authors: Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Giuseppe Liotta, and Antonios Symvonis

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A well-known result by Kant [Algorithmica, 1996] implies that n-vertex outerplane graphs admit embedding-preserving planar straight-line grid drawings where the internal faces are convex polygons in O(n²) area. In this paper, we present an algorithm to compute such drawings in O(n¹·⁵) area. We also consider outerplanar drawings in which the internal faces are required to be strictly-convex polygons. In this setting, we consider outerplanar graphs whose weak dual is a path and give a drawing algorithm that achieves Θ(nk²) area, where k is the maximum size of an internal facial cycle.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Giuseppe Liotta, and Antonios Symvonis. Internally-Convex Drawings of Outerplanar Graphs in Small Area. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.18,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Frati, Fabrizio and Liotta, Giuseppe and Symvonis, Antonios},
  title =	{{Internally-Convex Drawings of Outerplanar Graphs in Small Area}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.18},
  URN =		{urn:nbn:de:0030-drops-250042},
  doi =		{10.4230/LIPIcs.GD.2025.18},
  annote =	{Keywords: Grid drawings, convexity, area bounds, outerplanar graphs}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.45
TReView: Visualizing the European Union Transparency Register (Poster Abstract)

Authors: Cristiano Bernardini, Davide Campanelli, Walter Didimo, Luca Grilli, Giuseppe Liotta, and Benedetto Ponti

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We present TReView, the first visual analytics system for the exploration of the European Union (EU) Transparency Register, a large repository that aims to enhance transparency around lobbying activities within the EU, by enabling public oversight of meetings between lobbyists and EU officials.
Cite as

Cristiano Bernardini, Davide Campanelli, Walter Didimo, Luca Grilli, Giuseppe Liotta, and Benedetto Ponti. TReView: Visualizing the European Union Transparency Register (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 45:1-45:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bernardini_et_al:LIPIcs.GD.2025.45,
  author =	{Bernardini, Cristiano and Campanelli, Davide and Didimo, Walter and Grilli, Luca and Liotta, Giuseppe and Ponti, Benedetto},
  title =	{{TReView: Visualizing the European Union Transparency Register}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{45:1--45:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.45},
  URN =		{urn:nbn:de:0030-drops-250310},
  doi =		{10.4230/LIPIcs.GD.2025.45},
  annote =	{Keywords: Transparency Registry, European Union, Graph Visualization, Interactive Visualization, Visual Analytics}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.52
Investigating Crossing Perception in 3D Graph Visualisation (Poster Abstract)

Authors: Ying Zhang, Niklas Gröne, Giuseppe Liotta, Falk Schreiber, and Karsten Klein

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Human perception and understanding of graph drawings is influenced by a variety of impact factors for which quality measures such as the number of crossings are used as a proxy indicator. For the more and more common stereoscopic 3D (S3D) graph visualisations, evidence is required to better understand graph perception and its relation to quality measures. We investigate the perception of crossing configurations in S3D graph visualisations and present the results of a study.
Cite as

Ying Zhang, Niklas Gröne, Giuseppe Liotta, Falk Schreiber, and Karsten Klein. Investigating Crossing Perception in 3D Graph Visualisation (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 52:1-52:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.GD.2025.52,
  author =	{Zhang, Ying and Gr\"{o}ne, Niklas and Liotta, Giuseppe and Schreiber, Falk and Klein, Karsten},
  title =	{{Investigating Crossing Perception in 3D Graph Visualisation}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{52:1--52:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.52},
  URN =		{urn:nbn:de:0030-drops-250381},
  doi =		{10.4230/LIPIcs.GD.2025.52},
  annote =	{Keywords: Graph Perception, Stereoscopic 3D Graph Visualisation, Crossing Configurations}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.15
Bundling-Aware Graph Drawing

Authors: Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Edge bundling algorithms significantly improve the visualization of dense graphs by reducing the clutter of many edges visible on screen by bundling them together. As such, bundling is often viewed as a post-processing step applied to a drawing, and the vast majority of edge bundling algorithms consider a graph and its drawing as input. Another way of thinking about edge bundling is to simultaneously optimize both the drawing and the bundling. In this paper, we investigate methods to simultaneously optimize a graph drawing and its bundling. We describe an algorithmic framework which consists of three main steps, namely Filter, Draw, and Bundle. We then propose two alternative implementations and experimentally compare them against the state-of-the-art approach and the simple idea of drawing and subsequently bundling the graph. The experiments confirm that bundled drawings created by our framework outperform previous approaches according to standard quality metrics for edge bundling.
Cite as

Daniel Archambault, Giuseppe Liotta, Martin Nöllenburg, Tommaso Piselli, Alessandra Tappini, and Markus Wallinger. Bundling-Aware Graph Drawing. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{archambault_et_al:LIPIcs.GD.2024.15,
  author =	{Archambault, Daniel and Liotta, Giuseppe and N\"{o}llenburg, Martin and Piselli, Tommaso and Tappini, Alessandra and Wallinger, Markus},
  title =	{{Bundling-Aware Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.15},
  URN =		{urn:nbn:de:0030-drops-212995},
  doi =		{10.4230/LIPIcs.GD.2024.15},
  annote =	{Keywords: Edge Bundling, Experimental Comparison, Graph Sparsification}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.16
GraphTrials: Visual Proofs of Graph Properties

Authors: Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer’s perception, in particular, pre-attentive processing (e. g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes.
Cite as

Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber. GraphTrials: Visual Proofs of Graph Properties. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.GD.2024.16,
  author =	{F\"{o}rster, Henry and Klesen, Felix and Dwyer, Tim and Eades, Peter and Hong, Seok-Hee and Kobourov, Stephen G. and Liotta, Giuseppe and Misue, Kazuo and Montecchiani, Fabrizio and Pastukhov, Alexander and Schreiber, Falk},
  title =	{{GraphTrials: Visual Proofs of Graph Properties}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.16},
  URN =		{urn:nbn:de:0030-drops-213005},
  doi =		{10.4230/LIPIcs.GD.2024.16},
  annote =	{Keywords: Graph Visualization, Theory of Visualization, Visual Proof}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.19
Weakly Leveled Planarity with Bounded Span

Authors: Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y-monotone curve. A graph is s-span weakly leveled planar if it admits such a drawing where the edges have span at most s; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n)-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Fabrizio Frati, Siddharth Gupta, Philipp Kindermann, Giuseppe Liotta, Ignaz Rutter, and Ioannis G. Tollis. Weakly Leveled Planarity with Bounded Span. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2024.19,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Frati, Fabrizio and Gupta, Siddharth and Kindermann, Philipp and Liotta, Giuseppe and Rutter, Ignaz and Tollis, Ioannis G.},
  title =	{{Weakly Leveled Planarity with Bounded Span}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.19},
  URN =		{urn:nbn:de:0030-drops-213035},
  doi =		{10.4230/LIPIcs.GD.2024.19},
  annote =	{Keywords: Leveled planar graphs, edge span, graph drawing, edge-length ratio}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.49
Introducing Fairness in Graph Visualization (Poster Abstract)

Authors: Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Information visualization tools are an essential component of many data-driven decision-making systems that rely on human feedback. The aim of this paper is to propose a novel research direction focused on fair visualizations of graphs.
Cite as

Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli. Introducing Fairness in Graph Visualization (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hong_et_al:LIPIcs.GD.2024.49,
  author =	{Hong, Seok-Hee and Liotta, Giuseppe and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Piselli, Tommaso},
  title =	{{Introducing Fairness in Graph Visualization}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{49:1--49:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.49},
  URN =		{urn:nbn:de:0030-drops-213338},
  doi =		{10.4230/LIPIcs.GD.2024.49},
  annote =	{Keywords: Network visualization, Fairness, Stress minimization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.26
Rectilinear-Upward Planarity Testing of Digraphs

Authors: Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
A rectilinear-upward planar drawing of a digraph G is a crossing-free drawing of G where each edge is either a horizontal or a vertical segment, and such that no directed edge points downward. Rectilinear-Upward Planarity Testing is the problem of deciding whether a digraph G admits a rectilinear-upward planar drawing. We show that: (i) Rectilinear-Upward Planarity Testing is NP-complete, even if G is biconnected; (ii) it can be solved in linear time when an upward planar embedding of G is fixed; (iii) the problem is polynomial-time solvable for biconnected digraphs of treewidth at most two, i.e., for digraphs whose underlying undirected graph is a series-parallel graph; (iv) for any biconnected digraph the problem is fixed-parameter tractable when parameterized by the number of sources and sinks in the digraph.
Cite as

Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali, and Maurizio Patrignani. Rectilinear-Upward Planarity Testing of Digraphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{didimo_et_al:LIPIcs.ISAAC.2023.26,
  author =	{Didimo, Walter and Kaufmann, Michael and Liotta, Giuseppe and Ortali, Giacomo and Patrignani, Maurizio},
  title =	{{Rectilinear-Upward Planarity Testing of Digraphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.26},
  URN =		{urn:nbn:de:0030-drops-193283},
  doi =		{10.4230/LIPIcs.ISAAC.2023.26},
  annote =	{Keywords: Graph drawing, orthogonal drawings, upward drawings, rectilinear planarity, upward planarity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.46
The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable

Authors: Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The problem of deciding whether a biconnected planar digraph G = (V,E) can be augmented to become an st-planar graph by adding a set of oriented edges E' ⊆ V × V is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set E'.
Cite as

Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov. The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{khazaliya_et_al:LIPIcs.ISAAC.2023.46,
  author =	{Khazaliya, Liana and Kindermann, Philipp and Liotta, Giuseppe and Montecchiani, Fabrizio and Simonov, Kirill},
  title =	{{The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.46},
  URN =		{urn:nbn:de:0030-drops-193483},
  doi =		{10.4230/LIPIcs.ISAAC.2023.46},
  annote =	{Keywords: st-planar graphs, parameterized complexity, upward planarity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.18
On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Authors: Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an st-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source s and a single sink t. Computing an st-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an st-orientation with at most k transitive edges is more challenging and it was recently proven to be NP-hard already when k = 0. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.
Cite as

Carla Binucci, Giuseppe Liotta, Fabrizio Montecchiani, Giacomo Ortali, and Tommaso Piselli. On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.MFCS.2023.18,
  author =	{Binucci, Carla and Liotta, Giuseppe and Montecchiani, Fabrizio and Ortali, Giacomo and Piselli, Tommaso},
  title =	{{On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.18},
  URN =		{urn:nbn:de:0030-drops-185524},
  doi =		{10.4230/LIPIcs.MFCS.2023.18},
  annote =	{Keywords: st-orientations, parameterized complexity, graph drawing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.39
Polyline Drawings with Topological Constraints

Authors: Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma partially preserves the topology of G if it has the same external boundary, the same rotation system, and the same set of crossings as G. Drawing Gamma fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We show that if the set of crossing-free edges of G forms a connected spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). Concerning drawings that fully preserve the topology, we show that if G has skewness k, it admits one such drawing with curve complexity at most 2k; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.
Cite as

Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani. Polyline Drawings with Topological Constraints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{digiacomo_et_al:LIPIcs.ISAAC.2018.39,
  author =	{Di Giacomo, Emilio and Eades, Peter and Liotta, Giuseppe and Meijer, Henk and Montecchiani, Fabrizio},
  title =	{{Polyline Drawings with Topological Constraints}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.39},
  URN =		{urn:nbn:de:0030-drops-99871},
  doi =		{10.4230/LIPIcs.ISAAC.2018.39},
  annote =	{Keywords: Topological graphs, graph drawing, curve complexity, skewness-k graphs, k-planar graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.9
A Universal Slope Set for 1-Bend Planar Drawings

Authors: Patrizio Angelini, Michael A. Bekos, Giuseppe Liotta, and Fabrizio Montecchiani

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We describe a set of Delta-1 slopes that are universal for 1-bend planar drawings of planar graphs of maximum degree Delta>=4; this establishes a new upper bound of Delta-1 on the 1-bend planar slope number. By universal we mean that every planar graph of degree Delta has a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges belong to the given set of slopes. This improves over previous results in two ways: Firstly, the best previously known upper bound for the 1-bend planar slope number was 3/2(Delta-1) (the known lower bound being 3/4(Delta-1)); secondly, all the known algorithms to construct 1-bend planar drawings with O(Delta) slopes use a different set of slopes for each graph and can have bad angular resolution, while our algorithm uses a universal set of slopes, which also guarantees that the minimum angle between any two edges incident to a vertex is pi/(Delta-1).
Cite as

Patrizio Angelini, Michael A. Bekos, Giuseppe Liotta, and Fabrizio Montecchiani. A Universal Slope Set for 1-Bend Planar Drawings. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SoCG.2017.9,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Liotta, Giuseppe and Montecchiani, Fabrizio},
  title =	{{A Universal Slope Set for 1-Bend Planar Drawings}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.9},
  URN =		{urn:nbn:de:0030-drops-71917},
  doi =		{10.4230/LIPIcs.SoCG.2017.9},
  annote =	{Keywords: Slope number, 1-bend drawings, planar graphs, angular resolution}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.19
On Visibility Representations of Non-Planar Graphs

Authors: Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NP-hard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
Cite as

Therese Biedl, Giuseppe Liotta, and Fabrizio Montecchiani. On Visibility Representations of Non-Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2016.19,
  author =	{Biedl, Therese and Liotta, Giuseppe and Montecchiani, Fabrizio},
  title =	{{On Visibility Representations of Non-Planar Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.19},
  URN =		{urn:nbn:de:0030-drops-59116},
  doi =		{10.4230/LIPIcs.SoCG.2016.19},
  annote =	{Keywords: Visibility Representations, 1-Planarity, Recognition Algorithm, Forbidden Configuration}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact