مؤتمر
On the width of complicated JSJ decompositions ; Sur la largeur des décompositions JSJ compliquées
| العنوان: | On the width of complicated JSJ decompositions ; Sur la largeur des décompositions JSJ compliquées |
|---|---|
| المؤلفون: | Huszár, Kristóf, Spreer, Jonathan |
| المساهمون: | Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), The University of Sydney, Chambers, Erin W., Gudmundsson, Joachim, ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-20-CE48-0007,AlgoKnot,Aspects algorithmiques et combinatoires de la théorie des nœuds(2020), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), ANR-21-CE48-0014,TWIN-WIDTH,Twin-width: théorie et applications(2021), ANR-10-LABX-0059,CARMIN,Centers of Hosting and International Mathematical Encounters(2010) |
| المصدر: | Leibniz International Proceedings in Informatics (LIPIcs) ; 39th International Symposium on Computational Geometry (SoCG 2023) ; https://hal.science/hal-04055617Test ; 39th International Symposium on Computational Geometry (SoCG 2023), Jun 2023, Dallas, United States. pp.42:1--42:18, ⟨10.4230/LIPIcs.SoCG.2023.42⟩ |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2023 |
| المجموعة: | HAL Lyon 1 (University Claude Bernard Lyon 1) |
| مصطلحات موضوعية: | fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations, computational 3-manifold topology, MSC: 57Q15, 57N10, 05C75, 57M15, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, [MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] |
| جغرافية الموضوع: | Dallas, United States |
| الوصف: | Full version of the conference paper. 22 pages, 19 figures ; International audience ; 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. ; Motivés par l’étude algorithmique des variétés tridimensionnelles, nous étudions la relation structurelle entre la décomposition JSJ d’une variété tridimensionnelle donnée et ses triangulations. En nous appuyant sur les travaux de Bachman, Derby-Talbot et Sedgwick, nous montrons qu’une décomposition JSJ « suffisamment compliquée » d’une 3-variété impose une « structure compliquée » pour toutes ses triangulations. Plus concrètement, nous montrons que, sous certaines conditions, la largeur d’arbre (respectivement la largeur de chemin) du graphe qui capture les incidences entre les morceaux de la décomposition JSJ d’une ... |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| العلاقة: | info:eu-repo/semantics/altIdentifier/arxiv/2303.06789; hal-04055617; https://hal.science/hal-04055617Test; https://hal.science/hal-04055617/documentTest; https://hal.science/hal-04055617/file/2303.06789.pdfTest; ARXIV: 2303.06789 |
| DOI: | 10.4230/LIPIcs.SoCG.2023.42 |
| الإتاحة: | https://doi.org/10.4230/LIPIcs.SoCG.2023.42Test https://hal.science/hal-04055617Test https://hal.science/hal-04055617/documentTest https://hal.science/hal-04055617/file/2303.06789.pdfTest |
| حقوق: | http://creativecommons.org/licenses/byTest/ ; info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.1E60F3C7 |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.SoCG.2023.42 |
|---|