20 Search Results for "Spreer, Jonathan"

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.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.85
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes

Authors: Geevarghese Philip and Erlend Raa Vågset

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

Abstract
The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has been studied extensively in heuristic, approximation, and parameterized complexity settings. Parameterized by treewidth k, OMM has long been known to be solvable on triangulations of 3-manifolds in 2^O(k²) n^O(1) time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on k has remained an open question. We resolve this by giving a new 2^O(k log k) n-time algorithm for any finite regular CW complex, and show that no 2^o(k log k) n^O(1)-time algorithm exists unless the Exponential Time Hypothesis (ETH) fails.
Cite as

Geevarghese Philip and Erlend Raa Vågset. ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 85:1-85:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{philip_et_al:LIPIcs.SoCG.2026.85,
  author =	{Philip, Geevarghese and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{85:1--85: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.85},
  URN =		{urn:nbn:de:0030-drops-258926},
  doi =		{10.4230/LIPIcs.SoCG.2026.85},
  annote =	{Keywords: Discrete Morse Theory, Simplicial Complexes, Optimal Morse Matching, Treewidth, Parameterized Algorithms, Computational Topology, Dynamic Programming, Exponential Time Hypothesis, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.93
Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations

Authors: Raphaël Tinarrage

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

Abstract
Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.
Cite as

Raphaël Tinarrage. Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{tinarrage:LIPIcs.SoCG.2026.93,
  author =	{Tinarrage, Rapha\"{e}l},
  title =	{{Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{93:1--93:22},
  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.93},
  URN =		{urn:nbn:de:0030-drops-258991},
  doi =		{10.4230/LIPIcs.SoCG.2026.93},
  annote =	{Keywords: Triangulation of manifolds, Simplicial approximation, CW complexes, Delaunay complexes, List homomorphism problem, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.37
Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology

Authors: Henrique Ennes and Clément Maria

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M' with the same quantum invariant, such that M' is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton [Samperton, 2023].
Cite as

Henrique Ennes and Clément Maria. Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ennes_et_al:LIPIcs.ESA.2025.37,
  author =	{Ennes, Henrique and Maria, Cl\'{e}ment},
  title =	{{Hardness of Computation of Quantum Invariants on 3-Manifolds with Restricted Topology}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.37},
  URN =		{urn:nbn:de:0030-drops-245057},
  doi =		{10.4230/LIPIcs.ESA.2025.37},
  annote =	{Keywords: 3-manifold, Heegaard splitting, Hempel distance, Quantum invariant, polynomial time reduction}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.18
Finding a Shortest Curve That Separates Few Objects from Many

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

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

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

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

Copy BibTex To Clipboard

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

Authors: Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer

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

Abstract
We present a framework to classify PL-types of large censuses of triangulated 4-manifolds, which we use to classify the PL-types of all triangulated 4-manifolds with up to 6 pentachora. This is successful except for triangulations homeomorphic to the 4-sphere, CP², and the rational homology sphere QS⁴(2), where we find at most four, three, and two PL-types respectively. We conjecture that they are all standard. In addition, we look at the cases resisting classification and discuss the combinatorial structure of these triangulations - which we deem interesting in their own rights.
Cite as

Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer. Small Triangulations of 4-Manifolds and the 4-Manifold Census. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{burke_et_al:LIPIcs.SoCG.2025.28,
  author =	{Burke, Rhuaidi Antonio and Burton, Benjamin A. and Spreer, Jonathan},
  title =	{{Small Triangulations of 4-Manifolds and the 4-Manifold Census}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{28:1--28: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.28},
  URN =		{urn:nbn:de:0030-drops-231805},
  doi =		{10.4230/LIPIcs.SoCG.2025.28},
  annote =	{Keywords: computational low-dimensional topology, triangulations, census of triangulations, 4-manifolds, PL standard 4-sphere, Pachner graph, mathematical software, experiments in low-dimensional topology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.67
Hard Diagrams of Split Links

Authors: Corentin Lunel, Arnaud de Mesmay, and Jonathan Spreer

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

Abstract
Deformations of knots and links in ambient space can be studied combinatorially on their diagrams via local modifications called Reidemeister moves. While it is well-known that, in order to move between equivalent diagrams with Reidemeister moves, one sometimes needs to insert excess crossings, there are significant gaps between the best known lower and upper bounds on the required number of these added crossings. In this article, we study the problem of turning a diagram of a split link into a split diagram, and we show that there exist split links with diagrams requiring an arbitrarily large number of such additional crossings. More precisely, we provide a family of diagrams of split links, so that any sequence of Reidemeister moves transforming a diagram with c crossings into a split diagram requires going through a diagram with Ω(√c) extra crossings. Our proof relies on the framework of bubble tangles, as introduced by the first two authors, and a technique of Chambers and Liokumovitch to turn homotopies into isotopies in the context of Riemannian geometry.
Cite as

Corentin Lunel, Arnaud de Mesmay, and Jonathan Spreer. Hard Diagrams of Split Links. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lunel_et_al:LIPIcs.SoCG.2025.67,
  author =	{Lunel, Corentin and de Mesmay, Arnaud and Spreer, Jonathan},
  title =	{{Hard Diagrams of Split Links}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{67:1--67:17},
  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.67},
  URN =		{urn:nbn:de:0030-drops-232191},
  doi =		{10.4230/LIPIcs.SoCG.2025.67},
  annote =	{Keywords: Knot theory, hard knot and link diagrams, Reidemeister moves, extra crossings, split links, bubble tangles, compression representativity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.38
An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Authors: Colleen Delaney, Clément Maria, and Eric Samperton

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

Abstract
Quantum topology provides various frameworks for defining and computing invariants of manifolds inspired by quantum theory. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we analyze the computational complexity of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. While these categories are the simplest source of state sum invariants beyond finite abelian groups (whose invariants can be computed in polynomial time) their computational complexities are yet to be fully understood. We first establish that the invariants arising from even the smallest Tambara-Yamagami categories are #P-hard to compute, so that one expects the same to be true of the whole family. Our main result is then the existence of a fixed parameter tractable algorithm to compute these 3-manifold invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is computable in polynomial time. Thus while one generally expects quantum invariants to be hard to compute classically, our results suggest that the hardness of computing state sum invariants from Tambara-Yamagami categories arises from classical 3-manifold topology rather than the quantum nature of the algebraic input.
Cite as

Colleen Delaney, Clément Maria, and Eric Samperton. An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{delaney_et_al:LIPIcs.SoCG.2025.38,
  author =	{Delaney, Colleen and Maria, Cl\'{e}ment and Samperton, Eric},
  title =	{{An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{38:1--38:15},
  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.38},
  URN =		{urn:nbn:de:0030-drops-231901},
  doi =		{10.4230/LIPIcs.SoCG.2025.38},
  annote =	{Keywords: 3-manifold, quantum invariant, fixed parameter tractable algorithm, topological parameter, Gauss sums, topological quantum field theory}
}
Artifact
Software
DOI: 10.4230/artifacts.23286
AlexHe98/idealedge

Authors: Alexander He

Abstract
Cite as

Alexander He. AlexHe98/idealedge (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23286,
   title = {{AlexHe98/idealedge}}, 
   author = {He, Alexander},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ebcbe72831246d6d99ed7ff98f3cc00940ed808c;origin=https://github.com/AlexHe98/idealedge;visit=swh:1:snp:0aecbae79b28d96e564539477e07d7c034f15e2a;anchor=swh:1:rev:9025c724d3c0c208f67a3b711a9342810c7d8909}{\texttt{swh:1:dir:ebcbe72831246d6d99ed7ff98f3cc00940ed808c}} (visited on 2025-06-20)},
   url = {https://github.com/AlexHe98/idealedge},
   doi = {10.4230/artifacts.23286},
}
Artifact
Software
DOI: 10.4230/artifacts.23281
raburke/Dim4Census

Authors: Rhuaidi Antonio Burke, Benjamin A. Burton, and Jonathan Spreer

Abstract
Cite as

Rhuaidi Antonio Burke, Benjamin A. Burton, Jonathan Spreer. raburke/Dim4Census (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23281,
   title = {{raburke/Dim4Census}}, 
   author = {Burke, Rhuaidi Antonio and Burton, Benjamin A. and Spreer, Jonathan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ee5ac0c76fdef9983c5de8a0be93f7684dd9a796;origin=https://github.com/raburke/Dim4Census;visit=swh:1:snp:a7fee9b4ed22b6bf281127e889c432095a216a58;anchor=swh:1:rev:54753c465209c14b34834a5f13cfe373b53ca4c6}{\texttt{swh:1:dir:ee5ac0c76fdef9983c5de8a0be93f7684dd9a796}} (visited on 2025-06-20)},
   url = {https://github.com/raburke/Dim4Census},
   doi = {10.4230/artifacts.23281},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.55
A Practical Algorithm for Knot Factorisation

Authors: Alexander He, Eric Sedgwick, and Jonathan Spreer

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

Abstract
We present an algorithm for computing the prime factorisation of a knot, which is practical in the following sense: using Regina, we give an implementation that works well for inputs of reasonable size, including prime knots from the 19-crossing census. The main new ingredient in this work is an object that we call an "edge-ideal triangulation", which is what our algorithm uses to represent knots. As other applications, we give an alternative proof that prime knot recognition is in coNP, and present some new complexity results for triangulations. Beyond knots, our work showcases edge-ideal triangulations as a tool for potential applications in 3-manifold topology.
Cite as

Alexander He, Eric Sedgwick, and Jonathan Spreer. A Practical Algorithm for Knot Factorisation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.SoCG.2025.55,
  author =	{He, Alexander and Sedgwick, Eric and Spreer, Jonathan},
  title =	{{A Practical Algorithm for Knot Factorisation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{55:1--55:15},
  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.55},
  URN =		{urn:nbn:de:0030-drops-232075},
  doi =		{10.4230/LIPIcs.SoCG.2025.55},
  annote =	{Keywords: Prime and composite knots, (crushing) normal surfaces, edge-ideal triangulations, co-NP certificate, triangulation complexity}
}
Document
DOI: 10.4230/DagRep.14.2.120
Triangulations in Geometry and Topology (Dagstuhl Seminar 24072)

Authors: Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, and Alex He

Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar "Triangulations in Geometry and Topology" (24072). The seminar was held from February 12 to February 16, 2024, gathered 31 participants, and started with four introductory talks and an open problem session. Then the participants spread into small groups to work on open problems on diverse topics including reconfiguration of geometric shapes, geodesics on triangulated surfaces, distances in flip graphs, geometric cycles and algorithms in 3-manifold topology.
Cite as

Maike Buchin, Jean Cardinal, Arnaud de Mesmay, Jonathan Spreer, and Alex He. Triangulations in Geometry and Topology (Dagstuhl Seminar 24072). In Dagstuhl Reports, Volume 14, Issue 2, pp. 120-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{buchin_et_al:DagRep.14.2.120,
  author =	{Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex},
  title =	{{Triangulations in Geometry and Topology (Dagstuhl Seminar 24072)}},
  pages =	{120--163},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{2},
  editor =	{Buchin, Maike and Cardinal, Jean and de Mesmay, Arnaud and Spreer, Jonathan and He, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.120},
  URN =		{urn:nbn:de:0030-drops-205017},
  doi =		{10.4230/DagRep.14.2.120},
  annote =	{Keywords: computational geometry, geometric topology, triangulations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.42
On the Width of Complicated JSJ Decompositions

Authors: Kristóf Huszár and Jonathan Spreer

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "sufficiently complicated" JSJ decomposition of a 3-manifold enforces a "complicated structure" for all of its triangulations. More concretely, we show that, under certain conditions, the treewidth (resp. pathwidth) of the graph that captures the incidences between the pieces of the JSJ decomposition of an irreducible, closed, orientable 3-manifold M yields a linear lower bound on its treewidth tw (M) (resp. pathwidth pw(M)), defined as the smallest treewidth (resp. pathwidth) of the dual graph of any triangulation of M. We present several applications of this result. We give the first example of an infinite family of bounded-treewidth 3-manifolds with unbounded pathwidth. We construct Haken 3-manifolds with arbitrarily large treewidth - previously the existence of such 3-manifolds was only known in the non-Haken case. We also show that the problem of providing a constant-factor approximation for the treewidth (resp. pathwidth) of bounded-degree graphs efficiently reduces to computing a constant-factor approximation for the treewidth (resp. pathwidth) of 3-manifolds.
Cite as

Kristóf Huszár and Jonathan Spreer. On the Width of Complicated JSJ Decompositions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2023.42,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
  title =	{{On the Width of Complicated JSJ Decompositions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.42},
  URN =		{urn:nbn:de:0030-drops-178920},
  doi =		{10.4230/LIPIcs.SoCG.2023.42},
  annote =	{Keywords: computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.13
Parametrized Complexity of Expansion Height

Authors: Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is famously undecidable. There exists a combinatorial refinement of this concept, called simple-homotopy equivalence: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion. In this article we consider the following related problem: given a 2-dimensional simplicial complex, is there a simple-homotopy equivalence to a 1-dimensional simplicial complex using at most p expansions? We show that the problem, which we call the erasability expansion height, is W[P]-complete in the natural parameter p.
Cite as

Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer. Parametrized Complexity of Expansion Height. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.ESA.2019.13,
  author =	{Bauer, Ulrich and Rathod, Abhishek and Spreer, Jonathan},
  title =	{{Parametrized Complexity of Expansion Height}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.13},
  URN =		{urn:nbn:de:0030-drops-111346},
  doi =		{10.4230/LIPIcs.ESA.2019.13},
  annote =	{Keywords: Simple-homotopy theory, simple-homotopy type, parametrized complexity theory, simplicial complexes, (modified) dunce hat}
}
  • Refine by Type
  • 18 Document/PDF
  • 11 Document/HTML
  • 2 Artifact

  • Refine by Publication Year
  • 4 2026
  • 8 2025
  • 1 2024
  • 1 2023
  • 2 2019
  • Show More...

  • Refine by Author
  • 12 Spreer, Jonathan
  • 5 Maria, Clément
  • 3 Burton, Benjamin A.
  • 3 Huszár, Kristóf
  • 2 Burke, Rhuaidi Antonio
  • Show More...

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

  • Refine by Classification
  • 10 Mathematics of computing → Geometric topology
  • 6 Theory of computation → Computational geometry
  • 4 Theory of computation → Fixed parameter tractability
  • 4 Theory of computation → Problems, reductions and completeness
  • 3 Mathematics of computing → Algebraic topology
  • Show More...

  • Refine by Keyword
  • 3 3-manifold
  • 3 fixed-parameter tractability
  • 3 treewidth
  • 3 triangulations
  • 2 Heegaard splitting
  • 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