[{"day":"01","type":"journal_article","author":[{"first_name":"Kristóf","full_name":"Huszár, Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner"}],"citation":{"apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. 2019;10(2):70–98. doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” <i>Journal of Computational Geometry</i>, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy, 2019. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>."},"title":"On the treewidth of triangulated 3-manifolds","language":[{"iso":"eng"}],"doi":"10.20382/JOGC.V10I2A5","ddc":["514"],"related_material":{"record":[{"id":"285","relation":"earlier_version","status":"public"},{"status":"public","id":"8032","relation":"part_of_dissertation"}]},"month":"11","date_created":"2019-11-23T12:14:09Z","page":"70–98","department":[{"_id":"UlWa"}],"quality_controlled":"1","publication":"Journal of Computational Geometry","intvolume":"        10","status":"public","publisher":"Computational Geometry Laborartoy","article_type":"original","has_accepted_license":"1","oa_version":"Published Version","year":"2019","date_updated":"2023-09-07T13:18:26Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"arxiv":["1712.00434"]},"publication_identifier":{"issn":["1920-180X"]},"file":[{"content_type":"application/pdf","file_id":"7094","relation":"main_file","date_created":"2019-11-23T12:35:16Z","file_name":"479-1917-1-PB.pdf","creator":"khuszar","file_size":857590,"checksum":"c872d590d38d538404782bca20c4c3f5","date_updated":"2020-07-14T12:47:49Z","access_level":"open_access"}],"_id":"7093","abstract":[{"lang":"eng","text":"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.\r\nIn 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).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito 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 18(k+1) (resp. 4(3k+1))."}],"date_published":"2019-11-01T00:00:00Z","arxiv":1,"issue":"2","article_processing_charge":"No","file_date_updated":"2020-07-14T12:47:49Z","volume":10,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_status":"published","oa":1},{"publisher":"Carleton University","intvolume":"        10","status":"public","publication":"Journal of Computational Geometry ","quality_controlled":"1","department":[{"_id":"HeEd"}],"page":"223–256","date_created":"2019-06-03T09:35:33Z","month":"07","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"doi":"10.20382/jocg.v10i1a9","ddc":["510"],"language":[{"iso":"eng"}],"title":"Simplices modelled on spaces of constant curvature","citation":{"short":"R. Dyer, G. Vegter, M. Wintraecken, Journal of Computational Geometry  10 (2019) 223–256.","apa":"Dyer, R., Vegter, G., &#38; Wintraecken, M. (2019). Simplices modelled on spaces of constant curvature. <i>Journal of Computational Geometry </i>. Carleton University. <a href=\"https://doi.org/10.20382/jocg.v10i1a9\">https://doi.org/10.20382/jocg.v10i1a9</a>","ama":"Dyer R, Vegter G, Wintraecken M. Simplices modelled on spaces of constant curvature. <i>Journal of Computational Geometry </i>. 2019;10(1):223–256. doi:<a href=\"https://doi.org/10.20382/jocg.v10i1a9\">10.20382/jocg.v10i1a9</a>","ista":"Dyer R, Vegter G, Wintraecken M. 2019. Simplices modelled on spaces of constant curvature. Journal of Computational Geometry . 10(1), 223–256.","ieee":"R. Dyer, G. Vegter, and M. Wintraecken, “Simplices modelled on spaces of constant curvature,” <i>Journal of Computational Geometry </i>, vol. 10, no. 1. Carleton University, pp. 223–256, 2019.","chicago":"Dyer, Ramsay, Gert Vegter, and Mathijs Wintraecken. “Simplices Modelled on Spaces of Constant Curvature.” <i>Journal of Computational Geometry </i>. Carleton University, 2019. <a href=\"https://doi.org/10.20382/jocg.v10i1a9\">https://doi.org/10.20382/jocg.v10i1a9</a>.","mla":"Dyer, Ramsay, et al. “Simplices Modelled on Spaces of Constant Curvature.” <i>Journal of Computational Geometry </i>, vol. 10, no. 1, Carleton University, 2019, pp. 223–256, doi:<a href=\"https://doi.org/10.20382/jocg.v10i1a9\">10.20382/jocg.v10i1a9</a>."},"ec_funded":1,"type":"journal_article","author":[{"last_name":"Dyer","first_name":"Ramsay","full_name":"Dyer, Ramsay"},{"last_name":"Vegter","first_name":"Gert","full_name":"Vegter, Gert"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs","first_name":"Mathijs"}],"day":"01","oa":1,"publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"volume":10,"file_date_updated":"2020-07-14T12:47:32Z","issue":"1","_id":"6515","date_published":"2019-07-01T00:00:00Z","abstract":[{"text":"We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature.","lang":"eng"}],"file":[{"file_name":"mainJournalFinal.pdf","creator":"mwintrae","file_size":2170882,"date_updated":"2020-07-14T12:47:32Z","access_level":"open_access","checksum":"57b4df2f16a74eb499734ec8ee240178","content_type":"application/pdf","relation":"main_file","file_id":"6516","date_created":"2019-06-03T09:30:01Z"}],"publication_identifier":{"issn":["1920-180X"]},"scopus_import":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:07:50Z","year":"2019","has_accepted_license":"1","oa_version":"Published Version"}]