21 Search Results for "Chaplick, Steven"

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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.65
Recognizing 2-Layer and Outer k-Planar Graphs

Authors: Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff

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

Abstract
The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. In both cases, edges are drawn as straight-line segments. Both variants are NP-hard, but admit FPT-algorithms with respect to the natural parameter. In recent years, in the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention. A graph is k-planar if it admits a drawing with at most k crossings per edge. In contrast to the crossing number, recognizing k-planar graphs is NP-hard even if k = 1 and hence not likely to be FPT with respect to the natural parameter k. In this paper, we consider the two above variants in the local setting. The k-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer k-planar and outer k-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to the natural parameter k. For k = 0, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. Two groups of researchers independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked explicitly whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer k-planar graphs and outer k-planar graphs, which implies that both recognition problems can be solved in polynomial time for every fixed k. We complement these results by showing that recognizing 2-layer k-planar graphs is XNLP-complete and that recognizing outer k-planar graphs is XNLP-hard. This implies that both problems are W[t]-hard for every t and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer k-planar graphs where the order of the vertices on one layer is specified.
Cite as

Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-Layer and Outer k-Planar Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.SoCG.2025.65,
  author =	{Kobayashi, Yasuaki and Okada, Yuto and Wolff, Alexander},
  title =	{{Recognizing 2-Layer and Outer k-Planar Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{65:1--65: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.65},
  URN =		{urn:nbn:de:0030-drops-232170},
  doi =		{10.4230/LIPIcs.SoCG.2025.65},
  annote =	{Keywords: 2-layer k-planar graphs, outer k-planar graphs, recognition algorithms, local crossing number, bandwidth, FPT, XNLP, XP, W\lbrackt\rbrack}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.9
Geometric Realizations of Dichotomous Ordinal Graphs

Authors: Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis

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

Abstract
A dichotomous ordinal graph consists of an undirected graph with a partition of the edges into short and long edges. A geometric realization of a dichotomous ordinal graph G in a metric space X is a drawing of G in X in which every long edge is strictly longer than every short edge. We call a graph G pandichotomous in X if G admits a geometric realization in X for every partition of its edge set into short and long edges. We exhibit a very close relationship between the degeneracy of a graph G and its pandichotomic Euclidean or spherical dimension, that is, the smallest dimension k such that G is pandichotomous in ℝ^k or the sphere 𝒮^k, respectively. First, every d-degenerate graph is pandichotomous in ℝ^d and 𝒮^{d-1} and these bounds are tight for the sphere and for ℝ² and almost tight for ℝ^d, for d ≥ 3. Second, every n-vertex graph that is pandichotomous in ℝ^k has at most μ kn edges, for some absolute constant μ < 7.23. This shows that the pandichotomic Euclidean dimension of any graph is linearly tied to its degeneracy and in the special case k ∈ {1,2} resolves open problems posed by Alam, Kobourov, Pupyrev, and Toeniskoetter. Further, we characterize which complete bipartite graphs are pandichotomous in ℝ²: These are exactly the K_{m,n} with m ≤ 3 or m = 4 and n ≤ 6. For general bipartite graphs, we can guarantee realizations in ℝ² if the short or the long subgraph is constrained: namely if the short subgraph is outerplanar or a subgraph of a rectangular grid, or if the long subgraph forms a caterpillar.
Cite as

Patrizio Angelini, Sabine Cornelsen, Carolina Haase, Michael Hoffmann, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis. Geometric Realizations of Dichotomous Ordinal Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.SoCG.2025.9,
  author =	{Angelini, Patrizio and Cornelsen, Sabine and Haase, Carolina and Hoffmann, Michael and Katsanou, Eleni and Montecchiani, Fabrizio and Steiner, Raphael and Symvonis, Antonios},
  title =	{{Geometric Realizations of Dichotomous Ordinal Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-231616},
  doi =		{10.4230/LIPIcs.SoCG.2025.9},
  annote =	{Keywords: Ordinal embeddings, geometric graphs, graph representations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.47
Shelling and Sinking Graphs on the Sphere

Authors: Jeff Erickson and Christian Howard

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

Abstract
We describe a promising approach to efficiently morph spherical graphs, extending earlier approaches of Awartani and Henderson [Trans. AMS 1987] and Kobourov and Landis [JGAA 2006]. Specifically, we describe two methods to morph shortest-path triangulations of the sphere by moving their vertices along longitudes into the southern hemisphere; we call a triangulation sinkable if such a morph exists. Our first method generalizes a longitudinal shelling construction of Awartani and Henderson; a triangulation is sinkable if a specific orientation of its dual graph is acyclic. We describe a simple polynomial-time algorithm to find a longitudinally shellable rotation of a given spherical triangulation, if one exists; we also construct a spherical triangulation that has no longitudinally shellable rotation. Our second method is based on a linear-programming characterization of sinkability. By identifying its optimal basis, we show that this linear program can be solved in O(n^{ω/2}) time, where ω is the matrix-multiplication exponent, assuming the underlying linear system is non-singular. Finally, we pose several conjectures and describe experimental results that support them.
Cite as

Jeff Erickson and Christian Howard. Shelling and Sinking Graphs on the Sphere. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{erickson_et_al:LIPIcs.SoCG.2025.47,
  author =	{Erickson, Jeff and Howard, Christian},
  title =	{{Shelling and Sinking Graphs on the Sphere}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{47:1--47:18},
  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.47},
  URN =		{urn:nbn:de:0030-drops-231996},
  doi =		{10.4230/LIPIcs.SoCG.2025.47},
  annote =	{Keywords: morphing, planar graphs, spherical graph drawing, longitudinal shelling}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.11
Monotone Arc Diagrams with Few Biarcs

Authors: Steven Chaplick, Henry Förster, Michael Hoffmann, and Michael Kaufmann

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

Abstract
We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f.
Cite as

Steven Chaplick, Henry Förster, Michael Hoffmann, and Michael Kaufmann. Monotone Arc Diagrams with Few Biarcs. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.GD.2024.11,
  author =	{Chaplick, Steven and F\"{o}rster, Henry and Hoffmann, Michael and Kaufmann, Michael},
  title =	{{Monotone Arc Diagrams with Few Biarcs}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{11:1--11:16},
  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.11},
  URN =		{urn:nbn:de:0030-drops-212955},
  doi =		{10.4230/LIPIcs.GD.2024.11},
  annote =	{Keywords: planar graph, topological book embedding, monotone drawing, linear layout}
}
Document
DOI: 10.4230/DagRep.12.11.66
Set Visualization and Uncertainty (Dagstuhl Seminar 22462)

Authors: Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract
The Dagstuhl Seminar on Set Visualization and Uncertainty brought together a group of researchers from diverse disciplines, all of which are interested in various aspects of this type of visualization: the cognitive aspects, the modelling aspects, the algorithmic aspects, and the information visualization aspects. An important but difficult to handle problem is how one should visualize information with underlying uncertainty. The seminar focused on uncertainty in set systems. This report includes short abstracts of the talks given during the seminar as well as more extensive working group reports on the research done during the seminar.
Cite as

Susanne Bleisch, Steven Chaplick, Jan-Henrik Haunert, Eva Mayr, Marc van Kreveld, and Annika Bonerath. Set Visualization and Uncertainty (Dagstuhl Seminar 22462). In Dagstuhl Reports, Volume 12, Issue 11, pp. 66-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bleisch_et_al:DagRep.12.11.66,
  author =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  title =	{{Set Visualization and Uncertainty (Dagstuhl Seminar 22462)}},
  pages =	{66--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Bleisch, Susanne and Chaplick, Steven and Haunert, Jan-Henrik and Mayr, Eva and van Kreveld, Marc and Bonerath, Annika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.66},
  URN =		{urn:nbn:de:0030-drops-178360},
  doi =		{10.4230/DagRep.12.11.66},
  annote =	{Keywords: cartography, graph drawing, information visualization, set visualization, uncertainty}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.11
Bounding and Computing Obstacle Numbers of Graphs

Authors: Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
An obstacle representation of a graph G consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of G to points such that two vertices are adjacent in G if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each n-vertex graph is O(n log n) [Balko, Cibulka, and Valtr, 2018] and that there are n-vertex graphs whose obstacle number is Ω(n/(log log n)²) [Dujmović and Morin, 2015]. We improve this lower bound to Ω(n/log log n) for simple polygons and to Ω(n) for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of n-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some n-vertex graph is given as part of the input, then for some drawings Ω(n²) obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph G is fixed-parameter tractable in the vertex cover number of G. Second, we show that, given a graph G and a simple polygon P, it is NP-hard to decide whether G admits an obstacle representation using P as the only obstacle.
Cite as

Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff. Bounding and Computing Obstacle Numbers of Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{balko_et_al:LIPIcs.ESA.2022.11,
  author =	{Balko, Martin and Chaplick, Steven and Ganian, Robert and Gupta, Siddharth and Hoffmann, Michael and Valtr, Pavel and Wolff, Alexander},
  title =	{{Bounding and Computing Obstacle Numbers of Graphs}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.11},
  URN =		{urn:nbn:de:0030-drops-169495},
  doi =		{10.4230/LIPIcs.ESA.2022.11},
  annote =	{Keywords: Obstacle representation, Obstacle number, Visibility, NP-hardness, FPT}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.10
On Upward-Planar L-Drawings of Graphs

Authors: Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of e and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but the DAG is biconnected and series-parallel.
Cite as

Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, and Giordano Da Lozzo. On Upward-Planar L-Drawings of Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.MFCS.2022.10,
  author =	{Angelini, Patrizio and Chaplick, Steven and Cornelsen, Sabine and Da Lozzo, Giordano},
  title =	{{On Upward-Planar L-Drawings of Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.10},
  URN =		{urn:nbn:de:0030-drops-168085},
  doi =		{10.4230/LIPIcs.MFCS.2022.10},
  annote =	{Keywords: graph drawing, planar L-drawings, directed graphs, bitonic st-ordering, upward planarity, series-parallel graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.26
Parameterized Algorithms for Upward Planarity

Authors: Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.
Cite as

Steven Chaplick, Emilio Di Giacomo, Fabrizio Frati, Robert Ganian, Chrysanthi N. Raftopoulou, and Kirill Simonov. Parameterized Algorithms for Upward Planarity. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.SoCG.2022.26,
  author =	{Chaplick, Steven and Di Giacomo, Emilio and Frati, Fabrizio and Ganian, Robert and Raftopoulou, Chrysanthi N. and Simonov, Kirill},
  title =	{{Parameterized Algorithms for Upward Planarity}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.26},
  URN =		{urn:nbn:de:0030-drops-160349},
  doi =		{10.4230/LIPIcs.SoCG.2022.26},
  annote =	{Keywords: Upward planarity, parameterized algorithms, SPQR trees, treewidth, treedepth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.8
Recognizing Proper Tree-Graphs

Authors: Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.
Cite as

Steven Chaplick, Petr A. Golovach, Tim A. Hartmann, and Dušan Knop. Recognizing Proper Tree-Graphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.IPEC.2020.8,
  author =	{Chaplick, Steven and Golovach, Petr A. and Hartmann, Tim A. and Knop, Du\v{s}an},
  title =	{{Recognizing Proper Tree-Graphs}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.8},
  URN =		{urn:nbn:de:0030-drops-133118},
  doi =		{10.4230/LIPIcs.IPEC.2020.8},
  annote =	{Keywords: intersection graphs, H-graphs, recognition, fixed-parameter tractability}
}
  • Refine by Type
  • 21 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 9 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • 3 2020
  • Show More...

  • Refine by Author
  • 13 Chaplick, Steven
  • 4 Angelini, Patrizio
  • 3 Cornelsen, Sabine
  • 3 Hoffmann, Michael
  • 3 Wolff, Alexander
  • Show More...

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

  • Refine by Classification
  • 6 Mathematics of computing → Graph theory
  • 6 Theory of computation → Computational geometry
  • 4 Human-centered computing → Graph drawings
  • 3 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 3 FPT
  • 2 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact