2026-07-20T04:48:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25865 2026-06-23T12:59:52Z ddc:004 open_access

On Sparse Representations of 3‑Manifolds Huszár, Kristóf Maria, Clément computational 3-manifold topology fixed-parameter tractability Heegaard splittings and diagrams triangulations edge valence treewidth quantum invariants tensor networks 3-manifolds are commonly represented as triangulations, consisting of abstract tetrahedra whose triangular faces are identified in pairs. The combinatorial sparsity of a triangulation, as measured by the treewidth of its dual graph, plays a fundamental role in the design of parameterized algorithms. In this work, we investigate algorithmic procedures that transform or modify a given triangulation while controlling specific sparsity parameters. First, we revisit a standard, linear-time algorithm that converts a given triangulation into a Heegaard diagram of the underlying 3-manifold, showing that the construction preserves treewidth. We apply this construction to exhibit a fixed-parameter tractable framework for computing Kuperberg’s quantum invariants of 3-manifolds. Second, we present a quasi-linear-time algorithm that retriangulates a given triangulation into one with maximum edge valence of at most nine, while only moderately increasing the treewidth of the dual graph. Combining these two algorithms yields a quasi-linear-time algorithm that produces, from a given triangulation, a Heegaard diagram in which every attaching curve intersects at most nine others. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kristóf Huszár and Clément Maria 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.58 urn:nbn:de:0030-drops-258659 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.58 eng https://creativecommons.org/licenses/by/4.0/legalcode