[{"page":"xviii+120","citation":{"ama":"Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:10.15479/AT:ISTA:8032","ista":"Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.","apa":"Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032","ieee":"K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020.","mla":"Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.","short":"K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020.","chicago":"Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032."},"date_published":"2020-06-26T00:00:00Z","article_processing_charge":"No","has_accepted_license":"1","day":"26","title":"Combinatorial width parameters for 3-dimensional manifolds","ddc":["514"],"status":"public","_id":"8032","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","file":[{"file_name":"Kristof_Huszar-Thesis.pdf","access_level":"open_access","content_type":"application/pdf","file_size":2637562,"creator":"khuszar","relation":"main_file","file_id":"8034","date_created":"2020-06-26T10:03:58Z","date_updated":"2020-07-14T12:48:08Z","checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3"},{"file_name":"Kristof_Huszar-Thesis-source.zip","access_level":"closed","file_size":7163491,"content_type":"application/x-zip-compressed","creator":"khuszar","relation":"source_file","file_id":"8035","date_created":"2020-06-26T10:10:06Z","date_updated":"2020-07-14T12:48:08Z","checksum":"d5f8456202b32f4a77552ef47a2837d1"}],"alternative_title":["ISTA Thesis"],"type":"dissertation","abstract":[{"text":"Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus.","lang":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"degree_awarded":"PhD","acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"supervisor":[{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"}],"doi":"10.15479/AT:ISTA:8032","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-006-0"]},"month":"06","publisher":"Institute of Science and Technology Austria","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2020","date_created":"2020-06-26T10:00:36Z","date_updated":"2023-09-07T13:18:27Z","related_material":{"record":[{"id":"6556","status":"public","relation":"dissertation_contains"},{"relation":"dissertation_contains","status":"public","id":"7093"}]},"author":[{"first_name":"Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf"}],"file_date_updated":"2020-07-14T12:48:08Z"},{"alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"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."}],"intvolume":" 129","title":"3-manifold triangulations with small treewidth","ddc":["516"],"status":"public","_id":"6556","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"relation":"main_file","file_id":"6557","date_created":"2019-06-12T06:45:33Z","date_updated":"2020-07-14T12:47:33Z","checksum":"29d18c435368468aa85823dabb157e43","file_name":"2019_LIPIcs-Huszar.pdf","access_level":"open_access","file_size":905885,"content_type":"application/pdf","creator":"kschuh"}],"oa_version":"Published Version","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"scopus_import":"1","has_accepted_license":"1","article_processing_charge":"No","day":"01","page":"44:1-44:20","citation":{"apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44."},"publication":"35th International Symposium on Computational Geometry","date_published":"2019-06-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:33Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2019","volume":129,"date_updated":"2023-09-07T13:18:26Z","date_created":"2019-06-11T20:09:57Z","related_material":{"record":[{"id":"8032","status":"public","relation":"part_of_dissertation"}]},"author":[{"orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","first_name":"Kristóf","full_name":"Huszár, Kristóf"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"month":"06","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1812.05528"]},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2019.44","conference":{"location":"Portland, Oregon, United States","start_date":"2019-06-18","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry"}},{"file_date_updated":"2020-07-14T12:47:49Z","year":"2019","publication_status":"published","publisher":"Computational Geometry Laborartoy","department":[{"_id":"UlWa"}],"author":[{"full_name":"Huszár, Kristóf","last_name":"Huszár","first_name":"Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Spreer, Jonathan","first_name":"Jonathan","last_name":"Spreer"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"285","status":"public","relation":"earlier_version"},{"id":"8032","relation":"part_of_dissertation","status":"public"}]},"date_updated":"2023-09-07T13:18:26Z","date_created":"2019-11-23T12:14:09Z","volume":10,"month":"11","publication_identifier":{"issn":["1920-180X"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1712.00434"]},"quality_controlled":"1","doi":"10.20382/JOGC.V10I2A5","language":[{"iso":"eng"}],"type":"journal_article","abstract":[{"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)).","lang":"eng"}],"issue":"2","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"7093","title":"On the treewidth of triangulated 3-manifolds","status":"public","ddc":["514"],"intvolume":" 10","file":[{"content_type":"application/pdf","file_size":857590,"creator":"khuszar","access_level":"open_access","file_name":"479-1917-1-PB.pdf","checksum":"c872d590d38d538404782bca20c4c3f5","date_updated":"2020-07-14T12:47:49Z","date_created":"2019-11-23T12:35:16Z","relation":"main_file","file_id":"7094"}],"oa_version":"Published Version","day":"01","has_accepted_license":"1","article_processing_charge":"No","publication":"Journal of Computational Geometry","citation":{"chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.","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.” Journal of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. Computational Geometry Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5"},"article_type":"original","page":"70–98","date_published":"2019-11-01T00:00:00Z"},{"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1712.00434"]},"language":[{"iso":"eng"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary","end_date":"2018-06-14"},"doi":"10.4230/LIPIcs.SoCG.2018.46","month":"06","publication_identifier":{"issn":["18688969"]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2018","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","date_updated":"2023-09-06T11:13:41Z","date_created":"2018-12-11T11:45:37Z","volume":99,"author":[{"first_name":"Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"7093"}]},"article_number":"46","file_date_updated":"2020-07-14T12:45:51Z","publist_id":"7614","citation":{"mla":"Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.46","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.46"},"date_published":"2018-06-01T00:00:00Z","scopus_import":1,"day":"01","article_processing_charge":"No","has_accepted_license":"1","status":"public","ddc":["516","000"],"title":"On the treewidth of triangulated 3-manifolds","intvolume":" 99","_id":"285","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","file":[{"date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-17T15:32:38Z","checksum":"530d084116778135d5bffaa317479cac","relation":"main_file","file_id":"5713","file_size":642522,"content_type":"application/pdf","creator":"dernst","file_name":"2018_LIPIcs_Huszar.pdf","access_level":"open_access"}],"alternative_title":["LIPIcs"],"type":"conference","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. 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))."}]},{"month":"06","day":"30","article_processing_charge":"No","has_accepted_license":"1","page":"5","citation":{"ama":"Huszár K, Rolinek M. Playful Math - An Introduction to Mathematical Games. IST Austria","ista":"Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p.","apa":"Huszár, K., & Rolinek, M. (n.d.). Playful Math - An introduction to mathematical games. IST Austria.","ieee":"K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical games. IST Austria.","mla":"Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria.","short":"K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.","chicago":"Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria, n.d."},"oa":1,"language":[{"iso":"eng"}],"date_published":"2014-06-30T00:00:00Z","type":"working_paper","file_date_updated":"2020-07-14T12:47:48Z","title":"Playful Math - An introduction to mathematical games","ddc":["510"],"publication_status":"draft","status":"public","publisher":"IST Austria","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7038","year":"2014","date_created":"2019-11-18T15:57:05Z","date_updated":"2020-07-14T23:11:45Z","oa_version":"Published Version","file":[{"checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","date_created":"2019-11-18T15:57:51Z","date_updated":"2020-07-14T12:47:48Z","relation":"main_file","file_id":"7039","file_size":511233,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2014_Playful_Math_Huszar.pdf"}],"author":[{"full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057","first_name":"Kristóf","last_name":"Huszár"},{"first_name":"Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal"}]}]