30 Search Results for "Chaplick, Steven"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.6
How Many Slopes Does Polynomial Area Cost?

Authors: Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In this work, we study the interplay between the number of slopes, the number of bends per edge, and the area requirements for planar drawings of bounded-degree graphs. Our motivation stems from the fact that, while numerous algorithms produce planar drawings with few slopes for graphs of relatively small degree in polynomial area, existing approaches for higher-degree graphs often require super-polynomial area. We address this gap in the literature by presenting new constructions that yield polynomial-area drawings with few bends per edge while slightly increasing the required number of slopes, thereby providing the first systematic study of slopes, bends and area trade-offs.
Cite as

Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi. How Many Slopes Does Polynomial Area Cost?. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SWAT.2026.6,
  author =	{Bekos, Michael A. and Katsanou, Eleni and Kindermann, Philipp and Pavlidi, Maria Eleni},
  title =	{{How Many Slopes Does Polynomial Area Cost?}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.6},
  URN =		{urn:nbn:de:0030-drops-260424},
  doi =		{10.4230/LIPIcs.SWAT.2026.6},
  annote =	{Keywords: k-bend planar drawings, planar slope number, area requirements}
}
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.STACS.2026.32
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Authors: Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values of these parameters can be determined by performing costly queries. The goal is to design an adaptive query strategy that minimizes the query cost incurred in computing an optimal solution. Solving such problems generally requires that we be able to solve the associated verification problem: given the answers to all queries in advance, find a minimum-cost set of queries that certifies an optimal solution to the combinatorial optimization problem. We present a polynomial-time algorithm for verifying a minimum-weight basis of a matroid, where each weight lies in a given uncertainty area. These areas may be finite sets, real intervals, or unions of open and closed intervals, strictly generalizing previous work by Erlebach and Hoffman which only handled the special case of open intervals. Our algorithm introduces new techniques to address the resulting challenges. Verification problems are of particular importance in the area of explorable uncertainty, as the structural insights and techniques used to solve the verification problem often heavily influence work on the corresponding online problem and its stochastic variant. In our case, we use structural results from the verification problem to give a best-possible algorithm for a promise variant of the corresponding adaptive online problem. Finally, we show that our algorithms can be applied to two learning-augmented variants of the minimum-weight basis problem under explorable uncertainty.
Cite as

Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{diwan_et_al:LIPIcs.STACS.2026.32,
  author =	{Diwan, Haya and Hellerstein, Lisa and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.32},
  URN =		{urn:nbn:de:0030-drops-255216},
  doi =		{10.4230/LIPIcs.STACS.2026.32},
  annote =	{Keywords: Matroid verification, minimum-weight basis, query strategy, uncertainty matroid, explorable uncertainty}
}
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.21
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Authors: Parinya Chalermsook, Ly Orgo, and Minoo Zarsav

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

Abstract
This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.
Cite as

Parinya Chalermsook, Ly Orgo, and Minoo Zarsav. On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.GD.2025.21,
  author =	{Chalermsook, Parinya and Orgo, Ly and Zarsav, Minoo},
  title =	{{On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-250074},
  doi =		{10.4230/LIPIcs.GD.2025.21},
  annote =	{Keywords: Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.24
String Graph Obstacles of High Girth and of Bounded Degree

Authors: Maria Chudnovsky, David Eppstein, and David Fischer

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

Abstract
A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for which any edge contraction or vertex deletion produces a string graph. Kratochvíl’s obstacles contain arbitrarily large cliques, so they have girth three and unbounded degree. We extend this line of working by studying obstacles among graphs of restricted girth and/or degree. We construct an infinite family of obstacles of girth four; in addition, our construction is K_{2,3}-subgraph-free and near-planar (planar plus one edge). Furthermore, we prove that there is a subcubic obstacle of girth three, and that there are no subcubic obstacles of high girth. We characterize the subcubic string graphs as having a matching whose contraction yields a planar graph, and based on this characterization we find a linear-time algorithm for recognizing subcubic string graphs of bounded treewidth.
Cite as

Maria Chudnovsky, David Eppstein, and David Fischer. String Graph Obstacles of High Girth and of Bounded Degree. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.GD.2025.24,
  author =	{Chudnovsky, Maria and Eppstein, David and Fischer, David},
  title =	{{String Graph Obstacles of High Girth and of Bounded Degree}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-250108},
  doi =		{10.4230/LIPIcs.GD.2025.24},
  annote =	{Keywords: string graphs, induced minors, forbidden minors, sparsity, triangle-free graphs, near-planar graphs}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.10
The Bend Number of Cocomparability Graphs

Authors: Todor Antić, Vit Jelínek, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr

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

Abstract
We introduce a new complexity measure for cocomparability graphs of posets or in other words, intersection graphs of piecewise linear functions, the bend number. We prove that cocomparability graphs of bounded bend number are not too plentiful and give two hierarchies of classes of cocomparability graphs, depending on whether the piecewise linear functions are restricted to slopes of ±1 (diagonal case) or not (general case). These hierarchies give a gradation between permutation graphs and cocomparability graphs.
Cite as

Todor Antić, Vit Jelínek, Martin Pergel, Felix Schröder, Peter Stumpf, and Pavel Valtr. The Bend Number of Cocomparability Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.10,
  author =	{Anti\'{c}, Todor and Jel{\'\i}nek, Vit and Pergel, Martin and Schr\"{o}der, Felix and Stumpf, Peter and Valtr, Pavel},
  title =	{{The Bend Number of Cocomparability Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{10:1--10:23},
  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.10},
  URN =		{urn:nbn:de:0030-drops-249963},
  doi =		{10.4230/LIPIcs.GD.2025.10},
  annote =	{Keywords: Intersection Graphs, Bend Number, Piecewise Linear Functions, Graph Class Hierarchy, Cocomparability Graphs, Permutation Graphs, Poset Dimension}
}
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.29
Stabbing Faces by a Convex Curve

Authors: David Eppstein

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

Abstract
We prove that, for every plane graph G and every smooth convex curve C not on a single line, there exists a straight-line drawing of G for which every face is crossed by C.
Cite as

David Eppstein. Stabbing Faces by a Convex Curve. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 29:1-29:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.GD.2025.29,
  author =	{Eppstein, David},
  title =	{{Stabbing Faces by a Convex Curve}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{29:1--29:8},
  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.29},
  URN =		{urn:nbn:de:0030-drops-250155},
  doi =		{10.4230/LIPIcs.GD.2025.29},
  annote =	{Keywords: planar graphs, convex curves, stabbing, transversal}
}
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.7
Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Authors: Sayan Bandyapadhyay and Eli Mitchell

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

Abstract
We study the Discrete Covering with Two Types of Radii problem motivated by its application in wireless networks. In this problem, the goal is to assign either small-range high frequency or large-range low frequency to each access point, maximizing the number of users in high-frequency regions while ensuring that each user is in the range of an access point. Unlike other weighted covering problems, our problem requires satisfying two simultaneous objectives, which calls for novel approaches that leverage the underlying geometry of the problem. In our work, we present two new algorithms: the first is a polynomial-time (2.5 + ε)-approximation, and the second is an exact algorithm for sparse instances, which is fixed-parameter tractable (FPT) in the number of large-radius disks. We also prove that such an FPT algorithm is impossible for general instances lacking sparsity, assuming the Exponential Time Hypothesis. Before our work, the best-known polynomial-time approximation factor was 4 for the problem. Our approximation algorithm results from a fine-grained classification of points that can contribute to the gain of a solution. Based on this classification, we design two sub-algorithms with interdependent guarantees to recover the respective class of points as gain. Our algorithm exploits further properties of Delaunay triangulations to achieve the improved bound. The FPT algorithm is based on branching that utilizes the sparsity of the instances to limit the overall search space.
Cite as

Sayan Bandyapadhyay and Eli Mitchell. Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.WADS.2025.7,
  author =	{Bandyapadhyay, Sayan and Mitchell, Eli},
  title =	{{Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{7:1--7:14},
  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.7},
  URN =		{urn:nbn:de:0030-drops-242386},
  doi =		{10.4230/LIPIcs.WADS.2025.7},
  annote =	{Keywords: Covering, Disks, Approximation, FPT}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.35
Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage

Authors: Meng He and Kaiyu Wu

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

Abstract
We improve the recent succinct data structure result of Balakrishnan et al. for chordal graphs with bounded vertex leafage (SWAT 2024). A chordal graph is a widely studied graph class which can be characterized as the intersection graph of subtrees of a host tree, denoted as a tree representation of the chordal graph. The vertex leafage and leafage parameters of a chordal graph deal with the existence of a tree representation with a bounded number of leaves in either the subtrees representing the vertices or the host tree itself. We simplify the lower bound proof of Balakrishnan et al. which applied to only chordal graphs with bounded vertex leafage, and extend it to a lower bound proof for chordal graphs with bounded leafage as well. For both classes of graphs, the information-theoretic lower bound we (re-)obtain for k = o(n) is (k-1)nlog n - knlog k - o(knlog n) bits, where the leafage or vertex leafage of the graph is at most k = o(n). We further extend the range of the parameter k to Θ(n) as well. Then we give a succinct data structure using (k-1)nlog (n/k) + o(knlog n) bits to answer adjacent queries, which test the adjacency between pairs of vertices, in O((log k)/(log log n) + 1) time compared to the O(klog n) time of the data structure of Balakrishnan et al. For the neighborhood query which lists the neighbours of a given vertex, our query time is O((log n)/(log log n)) per neighbour compared to O(k²log n) per neighbour. We also extend the data structure ideas to obtain a succinct data structure for chordal graphs with bounded leafage k, answering an open question of Balakrishnan et al. Our succinct data structure, which uses (k-1)nlog (n/k) + o(knlog n) bits, has query time O(1) for the adjacent query and O(1) per neighbour for the neighborhood query. Using slightly more space (an additional (1+ε)nlog n bits for any ε > 0) allows distance queries, which compute the number of edges in the shortest path between two given vertices, to be answered in O(1) time as well.
Cite as

Meng He and Kaiyu Wu. Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 35:1-35:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.WADS.2025.35,
  author =	{He, Meng and Wu, Kaiyu},
  title =	{{Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{35:1--35:23},
  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.35},
  URN =		{urn:nbn:de:0030-drops-242660},
  doi =		{10.4230/LIPIcs.WADS.2025.35},
  annote =	{Keywords: Chordal Graph, Leafage, Vertex Leafage, Succinct Data Structure}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.35
A Note on the Complexity of Defensive Domination

Authors: Steven Chaplick, Grzegorz Gutowski, and Tomasz Krawczyk

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In a graph G, a k-attack A is any set of at most k vertices and 𝓁-defense D is a set of at most 𝓁 vertices. We say that defense D counters attack A if each a ∈ A can be matched to a distinct defender d ∈ D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and 𝓁 given on input, if there exists an 𝓁-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class Σ^𝖯₂. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note, we prove that the defensive domination problem is Σ^𝖯₂-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also Σ^𝖯₂-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs.
Cite as

Steven Chaplick, Grzegorz Gutowski, and Tomasz Krawczyk. A Note on the Complexity of Defensive Domination. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.MFCS.2025.35,
  author =	{Chaplick, Steven and Gutowski, Grzegorz and Krawczyk, Tomasz},
  title =	{{A Note on the Complexity of Defensive Domination}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.35},
  URN =		{urn:nbn:de:0030-drops-241420},
  doi =		{10.4230/LIPIcs.MFCS.2025.35},
  annote =	{Keywords: graph domination, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.26
Computational Complexity of Covering Regular Trees

Authors: Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990’s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that H-Cover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d ≥ 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.
Cite as

Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Regular Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2025.26,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Regular Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-241338},
  doi =		{10.4230/LIPIcs.MFCS.2025.26},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity, constrained homomorphisms, trees}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.8
Identifying Approximate Minimizers Under Stochastic Uncertainity

Authors: Hessa Al-Thani and Viswanath Nagarajan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study a fundamental stochastic selection problem involving n independent random variables, each of which can be queried at some cost. Given a tolerance level δ, the goal is to find a δ-approximately minimum (or maximum) value over all the random variables, at minimum expected cost. A solution to this problem is an adaptive sequence of queries, where the choice of the next query may depend on previously-observed values. Two variants arise, depending on whether the goal is to find a δ-minimum value or a δ-minimizer. When all query costs are uniform, we provide a 4-approximation algorithm for both variants. When query costs are non-uniform, we provide a 5.83-approximation algorithm for the δ-minimum value and a 7.47-approximation for the δ-minimizer. All our algorithms rely on non-adaptive policies (that perform a fixed sequence of queries), so we also upper bound the corresponding "adaptivity" gaps. Our analysis relates the stopping probabilities in the algorithm and optimal policies, where a key step is in proving and using certain stochastic dominance properties.
Cite as

Hessa Al-Thani and Viswanath Nagarajan. Identifying Approximate Minimizers Under Stochastic Uncertainity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{althani_et_al:LIPIcs.ICALP.2025.8,
  author =	{Al-Thani, Hessa and Nagarajan, Viswanath},
  title =	{{Identifying Approximate Minimizers Under Stochastic Uncertainity}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.8},
  URN =		{urn:nbn:de:0030-drops-233854},
  doi =		{10.4230/LIPIcs.ICALP.2025.8},
  annote =	{Keywords: Approximation algorithms, stochastic optimization, selection problem}
}
  • Refine by Type
  • 30 Document/PDF
  • 19 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 15 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 13 Chaplick, Steven
  • 4 Angelini, Patrizio
  • 3 Cornelsen, Sabine
  • 3 Da Lozzo, Giordano
  • 3 Frati, Fabrizio
  • Show More...

  • Refine by Series/Journal
  • 29 LIPIcs
  • 1 DagRep

  • Refine by Classification
  • 8 Mathematics of computing → Graph theory
  • 8 Theory of computation → Computational geometry
  • 5 Human-centered computing → Graph drawings
  • 5 Mathematics of computing → Graph algorithms
  • 4 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 3 FPT
  • 3 NP-hardness
  • 2 approximation scheme
  • 2 balanced separators
  • 2 geometric approximation algorithms
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact