7 Search Results for "Spreer, Jonathan"

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-dev.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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.44
3-Manifold Triangulations with Small Treewidth

Authors: Kristóf Huszár and Jonathan Spreer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.
Cite as

Kristóf Huszár and Jonathan Spreer. 3-Manifold Triangulations with Small Treewidth. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2019.44,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan},
  title =	{{3-Manifold Triangulations with Small Treewidth}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.44},
  URN =		{urn:nbn:de:0030-drops-104487},
  doi =		{10.4230/LIPIcs.SoCG.2019.44},
  annote =	{Keywords: computational 3-manifold topology, fixed-parameter tractability, layered triangulations, structural graph theory, treewidth, cutwidth, Heegaard genus, lens spaces, Seifert fibered spaces}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.46
On the Treewidth of Triangulated 3-Manifolds

Authors: Kristóf Huszár, Jonathan Spreer, and Uli Wagner

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).
Cite as

Kristóf Huszár, Jonathan Spreer, and Uli Wagner. On the Treewidth of Triangulated 3-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huszar_et_al:LIPIcs.SoCG.2018.46,
  author =	{Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan and Wagner, Uli},
  title =	{{On the Treewidth of Triangulated 3-Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.46},
  URN =		{urn:nbn:de:0030-drops-87591},
  doi =		{10.4230/LIPIcs.SoCG.2018.46},
  annote =	{Keywords: computational topology, triangulations of 3-manifolds, thin position, fixed-parameter tractability, congestion, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.71
The Trisection Genus of Standard Simply Connected PL 4-Manifolds

Authors: Jonathan Spreer and Stephan Tillmann

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Gay and Kirby recently introduced the concept of a trisection for arbitrary smooth, oriented closed 4-manifolds, and with it a new topological invariant, called the trisection genus. In this note we show that the K3 surface has trisection genus 22. This implies that the trisection genus of all standard simply connected PL 4-manifolds is known. We show that the trisection genus of each of these manifolds is realised by a trisection that is supported by a singular triangulation. Moreover, we explicitly give the building blocks to construct these triangulations.
Cite as

Jonathan Spreer and Stephan Tillmann. The Trisection Genus of Standard Simply Connected PL 4-Manifolds. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 71:1-71:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{spreer_et_al:LIPIcs.SoCG.2018.71,
  author =	{Spreer, Jonathan and Tillmann, Stephan},
  title =	{{The Trisection Genus of Standard Simply Connected PL 4-Manifolds}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{71:1--71:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.71},
  URN =		{urn:nbn:de:0030-drops-87847},
  doi =		{10.4230/LIPIcs.SoCG.2018.71},
  annote =	{Keywords: combinatorial topology, triangulated manifolds, simply connected 4-manifolds, K3 surface, trisections of 4-manifolds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.64
Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants

Authors: Clément Maria and Jonathan Spreer

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Turaev-Viro invariants are amongst the most powerful tools to distinguish 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them rely on the enumeration of an extremely large set of combinatorial data defined on the triangulation, regardless of the underlying topology of the manifold. In the article, we propose a finer study of these combinatorial data, called admissible colourings, in relation with the cohomology of the manifold. We prove that the set of admissible colourings to be considered is substantially smaller than previously known, by furnishing new upper bounds on its size that are aware of the topology of the manifold. Moreover, we deduce new topology-sensitive enumeration algorithms based on these bounds. The paper provides a theoretical analysis, as well as a detailed experimental study of the approach. We give strong experimental evidence on large manifold censuses that our upper bounds are tighter than the previously known ones, and that our algorithms outperform significantly state of the art implementations to compute Turaev-Viro invariants.
Cite as

Clément Maria and Jonathan Spreer. Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2016.64,
  author =	{Maria, Cl\'{e}ment and Spreer, Jonathan},
  title =	{{Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.64},
  URN =		{urn:nbn:de:0030-drops-64050},
  doi =		{10.4230/LIPIcs.ESA.2016.64},
  annote =	{Keywords: low-dimensional topology, triangulations of 3-manifolds, cohomology theory, Turaev-Viro invariants, combinatorial algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.12
Efficient Algorithms to Decide Tightness

Authors: Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but more efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of 3-manifolds - a problem which previously was thought to be hard. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.
Cite as

Bhaskar Bagchi, Basudeb Datta, Benjamin A. Burton, Nitin Singh, and Jonathan Spreer. Efficient Algorithms to Decide Tightness. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bagchi_et_al:LIPIcs.SoCG.2016.12,
  author =	{Bagchi, Bhaskar and Datta, Basudeb and Burton, Benjamin A. and Singh, Nitin and Spreer, Jonathan},
  title =	{{Efficient Algorithms to Decide Tightness}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.12},
  URN =		{urn:nbn:de:0030-drops-59040},
  doi =		{10.4230/LIPIcs.SoCG.2016.12},
  annote =	{Keywords: discrete geometry and topology, polynomial time algorithms, fixed parameter tractability, tight triangulations, simplicial complexes}
}
  • Refine by Author
  • 7 Spreer, Jonathan
  • 3 Huszár, Kristóf
  • 1 Bagchi, Bhaskar
  • 1 Bauer, Ulrich
  • 1 Burton, Benjamin A.
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Geometric topology
  • 2 Theory of computation → Fixed parameter tractability
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Algebraic topology
  • 1 Theory of computation → W hierarchy

  • Refine by Keyword
  • 3 fixed-parameter tractability
  • 3 treewidth
  • 2 computational 3-manifold topology
  • 2 simplicial complexes
  • 2 triangulations of 3-manifolds
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2016
  • 2 2018
  • 2 2019
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact