119 Search Results for "Chambers, Erin"

Volume

LIPIcs, Volume 258

39th International Symposium on Computational Geometry (SoCG 2023)

SoCG 2023, June 12-15, 2023, Dallas, Texas, USA

Editors: Erin W. Chambers and Joachim Gudmundsson

Document
DOI: 10.4230/LIPIcs.SWAT.2026.26
On the Parameterized Complexity of Min-Sum-Radii

Authors: Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt

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

Abstract
In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics. We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k the number of clusters and Δ the cost of the clustering. We then investigate the structural parameterized complexity of the problem. Drexler et al. [doi:10.48550/arXiv.2310.02130] showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Δ even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Δ. Together, these results provide a complete picture of the parameterized complexity of MSR with respect to any combination of parameters k, Δ, as well as structural parameters for sparse graphs above vertex cover and known parameters for dense graphs (such as neighborhood diversity and modular width). Unweighted Graph Metrics. The story is rather different for unweighted graphs, since it is a long standing open question whether MSR on metrics induced by undirected graphs is solvable in polynomial-time. Although we cannot answer this question, we provide classical and parameterized hardness results for two very closely related problems, namely Exact-MSR (MSR and one wants to find exactly k clusters) and Allowed-Centers-MSR (MSR with an additional set of allowed cluster centers). We also show that MSR as well as these two problems are fixed-parameter tractable parameterized by the treedepth of the input graph.
Cite as

Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt. On the Parameterized Complexity of Min-Sum-Radii. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.SWAT.2026.26,
  author =	{Kumar, Pankaj and M\"{u}ller, Haiko and Ordyniak, Sebastian and Schmidt, Melanie},
  title =	{{On the Parameterized Complexity of Min-Sum-Radii}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{26:1--26: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.26},
  URN =		{urn:nbn:de:0030-drops-260623},
  doi =		{10.4230/LIPIcs.SWAT.2026.26},
  annote =	{Keywords: Parameterized complexity, Min-Sum-Radii clustering}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.37
A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach

Authors: Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken

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

Abstract
Assumptions on the reach are crucial for ensuring the correctness of many geometric and topological algorithms, including triangulation, manifold reconstruction and learning, homotopy reconstruction, and methods for estimating curvature or reach. However, these assumptions are often coupled with the requirement that the manifold be smooth, typically at least C². In this paper, we prove that any manifold with positive reach can be approximated arbitrarily well by a C^∞ manifold without significantly reducing the reach. More precisely, given a manifold with reach R, we construct a manifold that is ε-close to it in the C¹ sense (both the manifold and its tangent spaces are close), and has reach at least R-ε. The proof employs techniques from differential topology - partitions of unity and smoothing using convolution kernels. This result implies that nearly all theorems established for C² or manifolds with a certain reach naturally extend to manifolds with the same reach, even if they are not C², for free!
Cite as

Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken. A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalpozkourimska_et_al:LIPIcs.SoCG.2026.37,
  author =	{Dal Poz Kou\v{r}imsk\'{a}, Hana and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{A Free Lunch: Manifolds of Positive Reach Can Be Smoothed Without Decreasing the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{37:1--37:19},
  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.37},
  URN =		{urn:nbn:de:0030-drops-258434},
  doi =		{10.4230/LIPIcs.SoCG.2026.37},
  annote =	{Keywords: Reach, Manifolds, Smoothing, Differentiability, Differential topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.42
Compressed Data Structures for Heegaard Splitting

Authors: Henrique Ennes and Clément Maria

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

Abstract
Heegaard splittings provide a natural representation of closed 3-manifolds by gluing handlebodies along a common surface. These splittings can be equivalently given by two finite sets of meridians lying on the surface, which define a Heegaard diagram. We present a data structure to effectively represent Heegaard diagrams as normal curves with respect to triangulations of a surface of complexity measured by the space required to express the normal coordinates' vectors in binary. This structure can be significantly more compressed than triangulations of 3-manifolds, giving exponential gains for some families. Even with this succinct definition of complexity, we establish polynomial-time algorithms for comparing and manipulating diagrams, performing stabilizations, detecting trivial stabilizations and reductions, and computing topological invariants of the underlying manifolds, such as their fundamental and homology groups. We also contrast early implementations of our techniques with standard software programs for 3-manifolds, achieving faster algorithms for the average cases and exponential gains in speed for some particular presentations of the inputs.
Cite as

Henrique Ennes and Clément Maria. Compressed Data Structures for Heegaard Splitting. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ennes_et_al:LIPIcs.SoCG.2026.42,
  author =	{Ennes, Henrique and Maria, Cl\'{e}ment},
  title =	{{Compressed Data Structures for Heegaard Splitting}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{42:1--42:15},
  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.42},
  URN =		{urn:nbn:de:0030-drops-258484},
  doi =		{10.4230/LIPIcs.SoCG.2026.42},
  annote =	{Keywords: 3-manifold, Heegaard splitting, curves on surfaces, surface theory, data structure, computational topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.47
Computing the Skyscraper Invariant

Authors: Marc Fersztand and Jan Jendrysiak

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

Abstract
We develop the first algorithms for computing the Skyscraper Invariant [FJNT24]. This is a filtration of the classical rank invariant for multiparameter persistence modules defined by the Harder-Narasimhan filtrations along every central charge supported at a single parameter value. Cheng’s algorithm [Cheng24] can be used to compute HN filtrations of arbitrary acyclic quiver representations in polynomial time in the total dimension, but in practice, the large dimension of persistence modules makes this direct approach infeasible. We show that by exploiting the additivity of the HN filtration and the special central charges, one can get away with a brute-force approach. For d-parameter modules, this produces an FPT ε-approximate algorithm with runtime dominated by 𝒪(1/ε^d ⋅ T_dec), where T_dec is the time for decomposition, which we compute with aida [DJK25]. We show that the wall-and-chamber structure of the module can be computed via lower envelopes of degree d - 1 polynomials. This allows for an exact computation of the Skyscraper Invariant roughly in 𝒪(n^d ⋅ T_dec) time for n the size of the presentation and enables a fast hybrid algorithm. For 2-parameter modules, we have implemented not only our algorithms but also, for the first time, Cheng’s algorithm. We compare all algorithms and, as a proof of concept for data analysis, compute a filtered version of the Multiparameter Landscape for biomedical data.
Cite as

Marc Fersztand and Jan Jendrysiak. Computing the Skyscraper Invariant. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 47:1-47:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fersztand_et_al:LIPIcs.SoCG.2026.47,
  author =	{Fersztand, Marc and Jendrysiak, Jan},
  title =	{{Computing the Skyscraper Invariant}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{47:1--47:23},
  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.47},
  URN =		{urn:nbn:de:0030-drops-258535},
  doi =		{10.4230/LIPIcs.SoCG.2026.47},
  annote =	{Keywords: Topological Data Analysis, Multiparameter Persistence, Persistence, Harder-Narasimhan Filtration, Skyscraper Invariant}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.48
FPT Approximations for Capacitated Sum of Radii and Diameters

Authors: Arnold Filtser and Ameet Gadekar

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

Abstract
The Capacitated Sum of Radii problem involves partitioning a set of points P, where each point p ∈ P has capacity U_p, into k clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point p is at most U_p. We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a ≈5.83-approximation algorithm in FPT time (improving a previous ≈7.61 approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.
Cite as

Arnold Filtser and Ameet Gadekar. FPT Approximations for Capacitated Sum of Radii and Diameters. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SoCG.2026.48,
  author =	{Filtser, Arnold and Gadekar, Ameet},
  title =	{{FPT Approximations for Capacitated Sum of Radii and Diameters}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-258545},
  doi =		{10.4230/LIPIcs.SoCG.2026.48},
  annote =	{Keywords: clustering, sum of radii, sum of diameter, capacitated clustering, fpt}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.74
Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach

Authors: André Lieutier and Mathijs Wintraecken

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

Abstract
This paper contains three main results. Firstly, we give an elementary proof of the following statement: Let ℳ be a topological manifold without boundary embedded in R^d. If ℳ has positive reach, then ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space. Conversely if ℳ can locally be written as the graph of a C^{1,1} function from the tangent space to the normal space, then ℳ has positive reach. The result was hinted at by Federer when he introduced the reach, and proved by Lytchak. Lytchak’s proof relies heavily on CAT(k)-theory. The proof presented here uses only basic results on homology. Secondly, we give optimal Lipschitz-constants for the derivative, in other words we give an optimal bound for the angle between tangent spaces in term of the distance between the points. We stress that Lytchak did not provide any bound, let alone an optimal one, making his proof, although interesting from a mathematical perspective, ineffectual in an algorithmic setting. To provide precise and optimal bounds on the angle between tangent spaces, we formally introduce the local reach for sets of positive reach, based on Aamari et al.’s discussion for C² manifolds. We prove that the local reach of a manifold is completely characterized by the variation of tangent spaces. This improves earlier results, that were either suboptimal or assumed that the manifold was C². Thirdly, we show that the value of the reach is equals minimum of the local reach of the set and a global bottleneck for any set. This generalizes a result by Aamari et al. which explains how the reach is attained for C² manifolds.
Cite as

André Lieutier and Mathijs Wintraecken. Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 74:1-74:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lieutier_et_al:LIPIcs.SoCG.2026.74,
  author =	{Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{Manifolds of Positive Reach, Differentiability, Tangent Variation, and Attaining the Reach}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{74:1--74:16},
  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.74},
  URN =		{urn:nbn:de:0030-drops-258812},
  doi =		{10.4230/LIPIcs.SoCG.2026.74},
  annote =	{Keywords: Reach, Manifolds, Differentiability class, Lipschitz continuity, Tangent space}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.76
A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids

Authors: Clément Maria and Hoel Queffelec

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

Abstract
Knot theory is an active field of mathematics, in which combinatorial and computational methods play an important role. One side of computational knot theory, that has gained interest in recent years, both for complexity analysis and practical algorithms, is quantum topology and the computation of topological invariants issued from the theory. In this article, we leverage the rigidity brought by the representation-theoretic origins of the quantum invariants for algorithmic purposes. We do so by exploiting braids and the algebraic properties of the braid group to describe, analyze, and implement a fast algorithm to compute the Hecke representation of the braid group. We apply this construction to design a parameterized algorithm to compute the HOMFLY-PT polynomial of knots, and demonstrate its interest experimentally. Finally, we combine our fast Hecke representation algorithm with Garside theory, to implement a reservoir sampling search and find non-trivial braids with trivial Hecke representations with coefficients in ℤ/pℤ. We find explicitly several such braids, for the 4-strand and 5-strand braid groups.
Cite as

Clément Maria and Hoel Queffelec. A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.SoCG.2026.76,
  author =	{Maria, Cl\'{e}ment and Queffelec, Hoel},
  title =	{{A Fast Algorithm for the Hecke Representation of the Braid Group, and Applications to the Computation of the HOMFLY-PT Polynomial and the Search for Interesting Braids}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{76:1--76: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.76},
  URN =		{urn:nbn:de:0030-drops-258838},
  doi =		{10.4230/LIPIcs.SoCG.2026.76},
  annote =	{Keywords: Hecke representation of the braid group, parameterized algorithm, HOMFLY-PT polynomial of knots, reservoir sampling, faithfulness of Hecke representation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.87
Robustness of Persistent Topological Features and Minimum Homological Cuts

Authors: Pepijn Roos Hoefgeest and Lucas Slot

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

Abstract
Persistent homology is a popular method for computing topological features of (metric) data. Standard approaches based on the Čech or Rips filtration are stable under small perturbations of the data, but highly sensitive to outliers. This lack of robustness has been frequently addressed in the literature. In this paper, we take a novel perspective by asking the following question: When can we guarantee that an observed persistent feature (a bar) is inherent to the underlying data in the presence of a limited number of unknown, arbitrary outliers. We formalize this question by introducing the notion of adversarial robustness, and study the problem of deciding whether a given bar in the barcode of a filtered simplicial complex is adversarially robust. We show that this problem is essentially equivalent to a homological variant of the minimum cut problem in simplicial complexes, which we believe to be of independent interest. As our main technical contribution, we provide the first computational complexity results for this problem, consisting of an efficient algorithm in 0-dimensional homology, NP-hardness for the general problem, and an efficient algorithm for codimension-1 in n-dimensional complexes embedded in ℝⁿ. We also analyze its natural linear programming relaxation, whose dual defines a homological analog of the max-flow problem in graphs. We show that a max-flow/min-cut theorem does not hold in our setting, implying that the LP relaxation is not tight in general. Finally, in the special case of the Rips filtration, we provide a global heuristic based on the Hausdorff distance that guarantees adversarial robustness of sufficiently long bars. This connects adversarial robustness to standard stability theorems in persistent homology.
Cite as

Pepijn Roos Hoefgeest and Lucas Slot. Robustness of Persistent Topological Features and Minimum Homological Cuts. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2026.87,
  author =	{Roos Hoefgeest, Pepijn and Slot, Lucas},
  title =	{{Robustness of Persistent Topological Features and Minimum Homological Cuts}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{87:1--87:15},
  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.87},
  URN =		{urn:nbn:de:0030-drops-258636},
  doi =		{10.4230/LIPIcs.SoCG.2026.87},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Min-cut Max-flow, Robustness, Vietoris-Rips Filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.10
Fast Free Resolutions of Bifiltered Chain Complexes

Authors: Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls

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

Abstract
In a k-critical bifiltration, every simplex enters along a staircase with at most k steps. Examples with k > 1 include degree-Rips bifiltrations and models of the multicover bifiltration. We consider the problem of converting a k-critical bifiltration into a 1-critical (i.e. free) chain complex with equivalent homology. This is known as computing a free resolution of the underlying chain complex and is a first step toward post-processing such bifiltrations. We present two algorithms. The first one computes free resolutions corresponding to path graphs and assembles them to a chain complex by computing additional maps. The simple combinatorial structure of path graphs leads to good performance in practice, as demonstrated by extensive experiments. However, its worst-case bound is quadratic in the input size because long paths might yield dense boundary matrices in the output. Our second algorithm replaces the simplex-wise path graphs with ones that maintain short paths which leads to almost linear runtime and output size. We demonstrate that pre-computing a free resolution speeds up the task of computing a minimal presentation of the homology of a k-critical bifiltration in a fixed dimension. Furthermore, our findings show that a chain complex that is minimal in terms of generators can be asymptotically larger than the non-minimal output complex of our second algorithm in terms of description size.
Cite as

Ulrich Bauer, Tamal K. Dey, Michael Kerber, Florian Russold, and Matthias Söls. Fast Free Resolutions of Bifiltered Chain Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2026.10,
  author =	{Bauer, Ulrich and Dey, Tamal K. and Kerber, Michael and Russold, Florian and S\"{o}ls, Matthias},
  title =	{{Fast Free Resolutions of Bifiltered Chain Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-258161},
  doi =		{10.4230/LIPIcs.SoCG.2026.10},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Multi-Critical Bifiltrations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.49
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Authors: Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf

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

Abstract
Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.
Cite as

Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf. 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.STACS.2026.49,
  author =	{Gurjar, Rohit and Rothmund, Kilian and Thierauf, Thomas},
  title =	{{2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{49:1--49:22},
  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.49},
  URN =		{urn:nbn:de:0030-drops-255385},
  doi =		{10.4230/LIPIcs.STACS.2026.49},
  annote =	{Keywords: Graph Rigidity, Parallel Algorithms, Polynomial Identity Testing, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.23
Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes

Authors: Archit Chauhan, Samir Datta, and M. Praveen

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. In contrast, randomized parallel algorithms (and more recently, deterministic quasipolynomial parallel algorithms) are known for constructing a DFS tree in general (di)graphs. However a deterministic parallel algorithm for DFS in general graphs remains an elusive goal. Working towards this, a series of works gave deterministic NC algorithms for DFS in planar graphs and digraphs. We further extend these results to more general graph classes, by providing NC algorithms for (di)graphs of bounded genus, and for undirected H-minor-free graphs where H is a fixed graph with at most one crossing. For the case of (di)graphs of bounded treewidth, we further improve the complexity to a Logspace bound. Constructing a maximal path is a simpler problem (that reduces to DFS) for which no deterministic parallel bounds are known for general graphs. For planar graphs a bound of O(log n) parallel time on a CRCW PRAM (thus in NC²) is known. We improve this bound to Logspace.
Cite as

Archit Chauhan, Samir Datta, and M. Praveen. Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.FSTTCS.2025.23,
  author =	{Chauhan, Archit and Datta, Samir and Praveen, M.},
  title =	{{Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.23},
  URN =		{urn:nbn:de:0030-drops-251041},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.23},
  annote =	{Keywords: Parallel Complexity, Graph Algorithms, Depth First Search, Maximal Path, Planar Graphs, Minor-Free, Treewidth, Logspace}
}
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
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.50
Reeb Lobsters Are 1-Planar (Poster Abstract)

Authors: Maarten Löffler, Miriam Münch, and Ignaz Rutter

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

Abstract
Very recently, Chambers, Fasy, Hosseini Sereshgi and Löffler [Erin W. Chambers et al., 2025] showed that every Reeb caterpillar admits a crossing-free drawing. It turns out that this does not hold for Reeb lobsters but we show that these graphs admit drawings with at most one crossing per edge.
Cite as

Maarten Löffler, Miriam Münch, and Ignaz Rutter. Reeb Lobsters Are 1-Planar (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 50:1-50:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.GD.2025.50,
  author =	{L\"{o}ffler, Maarten and M\"{u}nch, Miriam and Rutter, Ignaz},
  title =	{{Reeb Lobsters Are 1-Planar}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{50:1--50:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.50},
  URN =		{urn:nbn:de:0030-drops-250365},
  doi =		{10.4230/LIPIcs.GD.2025.50},
  annote =	{Keywords: Reeb graphs, layered drawings, local crossing number}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.46
Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract)

Authors: Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger

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

Abstract
A fixed set of vertices in the plane may have multiple planar straight-line triangulations in which the degree of each vertex is the same. As such, the degree information does not completely determine the triangulation. We show that even if we know, for each vertex, the number of neighbors in each of the four cardinal directions, the triangulation is not completely determined. We show that counting such triangulations is #P-hard via a reduction from #3-regular bipartite planar vertex cover. pty
Cite as

Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger. Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.GD.2025.46,
  author =	{Chambers, Erin and Ophelders, Tim and Schenfisch, Anna and Sollberger, Julia},
  title =	{{Counting Triangulations of Fixed Cardinal Degrees}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{46:1--46:4},
  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.46},
  URN =		{urn:nbn:de:0030-drops-250325},
  doi =		{10.4230/LIPIcs.GD.2025.46},
  annote =	{Keywords: Planar Triangulations, Degree Information, #P-Hardness}
}
  • Refine by Type
  • 118 Document/PDF
  • 38 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 10 2026
  • 28 2025
  • 1 2024
  • 70 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 6 Ophelders, Tim
  • 5 Bandyapadhyay, Sayan
  • 5 Chambers, Erin Wolf
  • 5 Löffler, Maarten
  • 4 Chambers, Erin
  • Show More...

  • Refine by Series/Journal
  • 116 LIPIcs
  • 2 DagRep

  • Refine by Classification
  • 66 Theory of computation → Computational geometry
  • 14 Theory of computation → Design and analysis of algorithms
  • 13 Mathematics of computing → Algebraic topology
  • 10 Mathematics of computing → Geometric topology
  • 7 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 6 Fréchet distance
  • 5 Topological Data Analysis
  • 3 Clustering
  • 3 Persistent homology
  • 3 Treewidth
  • 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