DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.6

Upward-Planar Drawings with Bounded Span

Authors: Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Fabrizio Frati, Philipp Kindermann, Ignaz Rutter, and Johannes Zink

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head, and the y-coordinates of the vertices are integers. The span of an edge in such a drawing is the absolute difference between the y-coordinates of its endpoints, and the span of the drawing is the maximum span of any edge. The span of an upward-planar graph is the minimum span over all its upward-planar drawings. We study the problem of determining the span of upward-planar graphs and provide both combinatorial and algorithmic results. On the combinatorial side, we present upper and lower bounds for the span of directed trees. On the algorithmic side, we show that the problem of determining the span of an upward-planar graph is NP-complete already for directed trees and for biconnected single-source graphs. Moreover, we give efficient algorithms for several graph families with a bounded number of sources, including st-planar graphs and graphs where the planar or upward-planar embedding is prescribed. Furthermore, we show that the problem is fixed-parameter tractable with respect to the vertex cover number and the treedepth plus the span.

Cite as

Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo, Fabrizio Frati, Philipp Kindermann, Ignaz Rutter, and Johannes Zink. Upward-Planar Drawings with Bounded Span. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.WG.2026.6,
  author =	{Angelini, Patrizio and Cornelsen, Sabine and Da Lozzo, Giordano and Frati, Fabrizio and Kindermann, Philipp and Rutter, Ignaz and Zink, Johannes},
  title =	{{Upward-Planar Drawings with Bounded Span}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.6},
  URN =		{urn:nbn:de:0030-drops-261722},
  doi =		{10.4230/LIPIcs.WG.2026.6},
  annote =	{Keywords: graph drawing, directed graphs, upward planarity, span, level drawings}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.36

Upward Book Embeddings of Partitioned Digraphs

Authors: Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.

Cite as

Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter. Upward Book Embeddings of Partitioned Digraphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2026.36,
  author =	{Da Lozzo, Giordano and Frati, Fabrizio and Rutter, Ignaz},
  title =	{{Upward Book Embeddings of Partitioned Digraphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.36},
  URN =		{urn:nbn:de:0030-drops-258424},
  doi =		{10.4230/LIPIcs.SoCG.2026.36},
  annote =	{Keywords: upward book embeddings, partitioned digraphs, SPQ-trees, 2-trees}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.15

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.

Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.25

Structural Parameterizations of Simultaneous Planarity

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023].

Cite as

Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter. Structural Parameterizations of Simultaneous Planarity. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2025.25,
  author =	{Depian, Thomas and Fink, Simon D. and Firbas, Alexander and Ganian, Robert and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Structural Parameterizations of Simultaneous Planarity}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.25},
  URN =		{urn:nbn:de:0030-drops-249332},
  doi =		{10.4230/LIPIcs.ISAAC.2025.25},
  annote =	{Keywords: SEFE, Simultaneous Planarity, Fixed-Parameter Tractability, NP-hardness}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.23

The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

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

Abstract

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  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.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.27

Geometry Matters in Planar Storyplans

Authors: Alexander Dobler, Maximilian Holzmüller, and Martin Nöllenburg

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

Abstract

A storyplan visualizes a graph G = (V,E) as a sequence of 𝓁 frames Γ₁, … , Γ_𝓁, each of which is a drawing of the induced subgraph G[V_i] of a vertex subset V_i ⊆ V. Moreover, each vertex v ∈ V is contained in a single consecutive sequence of frames Γ_i, … , Γ_j, all vertices and edges contained in consecutive frames are drawn identically, and the union of all frames is a drawing of G. In GD 2022, the concept of planar storyplans was introduced, in which each frame must be a planar (topological) drawing. Several (parameterized) complexity results for recognizing graphs that admit a planar storyplan were provided, including NP-hardness. In this paper, we investigate an open question posed in the GD paper and show that the geometric and topological settings of the planar storyplan problem differ: We provide an instance of a graph that admits a planar storyplan, but no planar geometric storyplan, in which each frame is a planar straight-line drawing. Still, by adapting the reduction proof from the topological to the geometric setting, we show that recognizing the graphs that admit planar geometric storyplans remains NP-hard.

Cite as

Alexander Dobler, Maximilian Holzmüller, and Martin Nöllenburg. Geometry Matters in Planar Storyplans. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 27:1-27:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2025.27,
  author =	{Dobler, Alexander and Holzm\"{u}ller, Maximilian and N\"{o}llenburg, Martin},
  title =	{{Geometry Matters in Planar Storyplans}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{27:1--27:9},
  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.27},
  URN =		{urn:nbn:de:0030-drops-250135},
  doi =		{10.4230/LIPIcs.GD.2025.27},
  annote =	{Keywords: geometric storyplan, planarity, straight-line drawing, dynamic graph drawing}
}

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

DOI: 10.4230/LIPIcs.GD.2025.17

Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

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

Abstract

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  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.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.39

Optimizing Wiggle in Storylines

Authors: Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff

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

Abstract

A storyline visualization shows interactions between characters over time. Each character is represented by an x-monotone curve. Time is mapped to the x-axis, and groups of characters that interact at a particular point t in time must be ordered consecutively in the y-dimension at x = t. The predominant objective in storyline optimization so far has been the minimization of crossings between (blocks of) characters. Building on this work, we investigate another important, but less studied quality criterion, namely the minimization of wiggle, i.e., the amount of vertical movement of the characters over time. Given a storyline instance together with an ordering of the characters at any point in time, we show that wiggle count minimization is NP-complete. In contrast, we provide algorithms based on mathematical programming to solve linear wiggle height minimization and quadratic wiggle height minimization efficiently. Finally, we introduce a new method for routing character curves that focuses on keeping distances between neighboring curves constant as long as they run in parallel. We have implemented our algorithms, and we conduct a case study that explores the differences between the three optimization objectives. We use existing benchmark data, but we also present a new use case for storylines, namely the visualization of rolling stock schedules in railway operation.

Cite as

Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff. Optimizing Wiggle in Storylines. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2025.39,
  author =	{Dobler, Alexander and Hegemann, Tim and N\"{o}llenburg, Martin and Wolff, Alexander},
  title =	{{Optimizing Wiggle in Storylines}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{39:1--39: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.39},
  URN =		{urn:nbn:de:0030-drops-250252},
  doi =		{10.4230/LIPIcs.GD.2025.39},
  annote =	{Keywords: Storyline visualization, wiggle minimization, NP-complete, linear programming, quadratic programming, experimental analysis}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.32

Planar Stories of Graph Drawings: Algorithms and Experiments

Authors: Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf

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

Abstract

We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.

Cite as

Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf. Planar Stories of Graph Drawings: Algorithms and Experiments. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.GD.2025.32,
  author =	{Binucci, Carla and Cornelsen, Sabine and Didimo, Walter and Hong, Seok-Hee and Katsanou, Eleni and Patrignani, Maurizio and Symvonis, Antonios and Wolf, Samuel},
  title =	{{Planar Stories of Graph Drawings: Algorithms and Experiments}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{32:1--32:19},
  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.32},
  URN =		{urn:nbn:de:0030-drops-250182},
  doi =		{10.4230/LIPIcs.GD.2025.32},
  annote =	{Keywords: Graph Drawing, Dynamic Graphs, Graph Stories, Heuristics, ILP}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.28

Treewidth of Outer k-Planar Graphs

Authors: Rafał Pyzik

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

Abstract

Treewidth is an important structural graph parameter that quantifies how closely a graph resembles a tree-like structure. It has applications in many algorithmic and combinatorial problems. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs admitting a convex drawing (a straight-line drawing where all vertices lie on a circle) in which every edge crosses at most k other edges. We also consider the more general class of outer min-k-planar graphs, which are graphs admitting a convex drawing where for every crossing of two edges at least one of these edges is crossed at most k times. Firman, Gutowski, Kryven, Okada and Wolff [GD 2024] proved that every outer k-planar graph has treewidth at most 1.5k+2 and provided a lower bound of k+2 for even k. We establish a lower bound of 1.5k+0.5 for every odd k. Additionally, they showed that every outer min-k-planar graph has treewidth at most 3k+1. We improve this upper bound to 3⋅⌊k/2⌋+4. Our approach also allows us to upper bound the separation number, a parameter closely related to treewidth, of outer min-k-planar graphs by 2⋅⌊k/2⌋+4. This improves upon the previous bound of 2k+1 and achieves a bound with an optimal multiplicative constant.

Cite as

Rafał Pyzik. Treewidth of Outer k-Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pyzik:LIPIcs.GD.2025.28,
  author =	{Pyzik, Rafa{\l}},
  title =	{{Treewidth of Outer k-Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{28:1--28:16},
  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.28},
  URN =		{urn:nbn:de:0030-drops-250141},
  doi =		{10.4230/LIPIcs.GD.2025.28},
  annote =	{Keywords: treewidth, outer k-planar graphs, outer min-k-planar graphs, separation number}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.34

Layered Polyline Drawings of Planar Graphs

Authors: Debajyoti Mondal

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

Abstract

A k-layer polyline drawing of a planar graph G is a planar drawing of G on a set L of k parallel lines such that each vertex is mapped to a point on L and each edge is mapped to a polygonal chain with the endpoints and bends lying on L. In the fixed embedding setting, the output drawing maintains the given planar embedding, whereas in the variable embedding setting, the embedding may change. Every n-vertex planar graph admits a polyline drawing on 2n/3 layers, which is the best known upper bound for both settings. We improve this bound in the variable embedding setting. We show that every planar graph can be drawn on 14n/27+O(√n) layers by choosing a proper planar embedding, breaking the long-standing 2n/3-layer barrier.

Cite as

Debajyoti Mondal. Layered Polyline Drawings of Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 34:1-34:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mondal:LIPIcs.GD.2025.34,
  author =	{Mondal, Debajyoti},
  title =	{{Layered Polyline Drawings of Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{34:1--34:10},
  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.34},
  URN =		{urn:nbn:de:0030-drops-250202},
  doi =		{10.4230/LIPIcs.GD.2025.34},
  annote =	{Keywords: Layered Drawing, Variable Embedding, Polyline Drawing, Cycle Separator}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.5

On Planar Straight-Line Dominance Drawings

Authors: Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.

Cite as

Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali. On Planar Straight-Line Dominance Drawings. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.WADS.2025.5,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Di Battista, Giuseppe and Frati, Fabrizio and Grilli, Luca and Ortali, Giacomo},
  title =	{{On Planar Straight-Line Dominance Drawings}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.5},
  URN =		{urn:nbn:de:0030-drops-242361},
  doi =		{10.4230/LIPIcs.WADS.2025.5},
  annote =	{Keywords: st-graphs, dominance drawings, planar straight-line drawings, upward planarity}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.29

Linear Layouts of Graphs with Priority Queues

Authors: Emilio Di Giacomo, Walter Didimo, Henry Förster, Torsten Ueckerdt, and Johannes Zink

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

A linear layout of a graph consists of a linear ordering of its vertices and a partition of its edges into pages such that the edges assigned to the same page obey some constraint. The two most prominent and widely studied types of linear layouts are stack and queue layouts, in which any two edges assigned to the same page are forbidden to cross and nest, respectively. The names of these two layouts derive from the fact that, when parsing the graph according to the linear vertex ordering, the edges in a single page can be stored using a single stack or queue, respectively. Recently, the concepts of stack and queue layouts have been extended by using a double-ended queue or a restricted-input queue for storing the edges of a page. We extend this line of study to edge-weighted graphs by introducing priority queue layouts, that is, the edges on each page are stored in a priority queue whose keys are the edge weights. First, we show that there are edge-weighted graphs that require a linear number of priority queues. Second, we characterize the graphs that admit a priority queue layout with a single queue, regardless of the edge-weight function, and we provide an efficient recognition algorithm. Third, we show that the number of priority queues required independently of the edge-weight function is bounded by the pathwidth of the graph, but can be arbitrarily large already for graphs of treewidth two. Finally, we prove that determining the minimum number of priority queues is NP-complete if the linear ordering of the vertices is fixed.

Cite as

Emilio Di Giacomo, Walter Didimo, Henry Förster, Torsten Ueckerdt, and Johannes Zink. Linear Layouts of Graphs with Priority Queues. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{digiacomo_et_al:LIPIcs.WADS.2025.29,
  author =	{Di Giacomo, Emilio and Didimo, Walter and F\"{o}rster, Henry and Ueckerdt, Torsten and Zink, Johannes},
  title =	{{Linear Layouts of Graphs with Priority Queues}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.29},
  URN =		{urn:nbn:de:0030-drops-242602},
  doi =		{10.4230/LIPIcs.WADS.2025.29},
  annote =	{Keywords: linear layouts, recognition and characterization, priority queue layouts}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.18

Finding a Shortest Curve That Separates Few Objects from Many

Authors: Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted objects. The input is a set of interior-disjoint simple polygons in the plane, where k of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the k required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if k is not fixed, even in very special cases. The runtime of our algorithm is O(3^k n³), where n is the number of vertices of the input polygons. We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are k required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the k required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.

Cite as

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a Shortest Curve That Separates Few Objects from Many. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2025.18,
  author =	{Biedl, Therese and Colin de Verdi\`{e}re, \'{E}ric and Frati, Fabrizio and Lubiw, Anna and Rote, G\"{u}nter},
  title =	{{Finding a Shortest Curve That Separates Few Objects from Many}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.18},
  URN =		{urn:nbn:de:0030-drops-231701},
  doi =		{10.4230/LIPIcs.SoCG.2025.18},
  annote =	{Keywords: Enclosure, curve, separation, weakly simple polygon, Euler tour}
}

23 Search Results for "Frati, Fabrizio"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message