[{"quality_controlled":"1","page":"871 - 888","article_type":"original","publisher":"Springer","issue":"4","author":[{"full_name":"Burton, Benjamin","first_name":"Benjamin","last_name":"Burton"},{"id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","full_name":"De Mesmay, Arnaud N","first_name":"Arnaud N","last_name":"De Mesmay"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"_id":"534","intvolume":"        58","title":"Finding non-orientable surfaces in 3-Manifolds","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:47:01Z","article_processing_charge":"No","publication_status":"published","volume":58,"external_id":{"arxiv":["1602.07907"]},"year":"2017","citation":{"short":"B. Burton, A.N. de Mesmay, U. Wagner, Discrete &#38; Computational Geometry 58 (2017) 871–888.","mla":"Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>.","ista":"Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete &#38; Computational Geometry. 58(4), 871–888.","apa":"Burton, B., de Mesmay, A. N., &#38; Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. 2017;58(4):871-888. doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4. Springer, pp. 871–888, 2017.","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>."},"date_updated":"2023-02-21T17:01:34Z","abstract":[{"lang":"eng","text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case."}],"day":"09","doi":"10.1007/s00454-017-9900-0","arxiv":1,"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"06","oa_version":"Preprint","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"1379","relation":"earlier_version"}]},"main_file_link":[{"url":"https://arxiv.org/abs/1602.07907","open_access":"1"}],"type":"journal_article","date_published":"2017-06-09T00:00:00Z","publist_id":"7283","oa":1,"publication_identifier":{"issn":["01795376"]}},{"language":[{"iso":"eng"}],"conference":{"location":"Medford, MA, USA","end_date":"2016-06-17","start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry"},"has_accepted_license":"1","oa_version":"Published Version","month":"06","file":[{"creator":"system","file_id":"4930","relation":"main_file","access_level":"open_access","file_name":"IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:44:47Z","file_size":574770,"checksum":"f04248a61c24297cfabd30c5f8e0deb9","date_created":"2018-12-12T10:12:12Z"}],"status":"public","related_material":{"record":[{"relation":"later_version","id":"534","status":"public"}]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","date_published":"2016-06-01T00:00:00Z","oa":1,"publist_id":"5832","quality_controlled":"1","page":"24.1 - 24.15","file_date_updated":"2020-07-14T12:44:47Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","scopus_import":1,"_id":"1379","author":[{"last_name":"Burton","first_name":"Benjamin","full_name":"Burton, Benjamin"},{"last_name":"De Mesmay","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"date_created":"2018-12-11T11:51:41Z","department":[{"_id":"UlWa"}],"publication_status":"published","intvolume":"        51","title":"Finding non-orientable surfaces in 3-manifolds","pubrep_id":"622","alternative_title":["LIPIcs"],"volume":51,"ddc":["510"],"year":"2016","citation":{"short":"B. Burton, A.N. de Mesmay, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15.","mla":"Burton, Benjamin, et al. <i>Finding Non-Orientable Surfaces in 3-Manifolds</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>.","ista":"Burton B, de Mesmay AN, Wagner U. 2016. Finding non-orientable surfaces in 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 24.1-24.15.","apa":"Burton, B., de Mesmay, A. N., &#38; Wagner, U. (2016). Finding non-orientable surfaces in 3-manifolds (Vol. 51, p. 24.1-24.15). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-manifolds. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:24.1-24.15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 24.1-24.15.","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds,” 51:24.1-24.15. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>."},"date_updated":"2023-02-23T12:23:20Z","day":"01","doi":"10.4230/LIPIcs.SoCG.2016.24","abstract":[{"text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.","lang":"eng"}]},{"oa":1,"publist_id":"5462","date_published":"2015-09-01T00:00:00Z","type":"conference","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"http://arxiv.org/abs/1507.01688","open_access":"1"}],"month":"09","oa_version":"Preprint","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"conference":{"location":"Patras, Greece","end_date":"2015-09-16","start_date":"2015-09-14","name":"ESA: European Symposium on Algorithms"},"language":[{"iso":"eng"}],"abstract":[{"text":"Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε &gt; 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.\r\nOur techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.","lang":"eng"}],"doi":"10.1007/978-3-662-48350-3_33","day":"01","date_updated":"2021-01-12T06:52:31Z","year":"2015","citation":{"ista":"Cohen Addad V, de Mesmay AN. 2015. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. ESA: European Symposium on Algorithms, LNCS, vol. 9294, 386–398.","mla":"Cohen Addad, Vincent, and Arnaud N. de Mesmay. <i>A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface</i>. Vol. 9294, Springer, 2015, pp. 386–98, doi:<a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">10.1007/978-3-662-48350-3_33</a>.","short":"V. Cohen Addad, A.N. de Mesmay, in:, Springer, 2015, pp. 386–398.","ieee":"V. Cohen Addad and A. N. de Mesmay, “A fixed parameter tractable approximation scheme for the optimal cut graph of a surface,” presented at the ESA: European Symposium on Algorithms, Patras, Greece, 2015, vol. 9294, pp. 386–398.","chicago":"Cohen Addad, Vincent, and Arnaud N de Mesmay. “A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface,” 9294:386–98. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">https://doi.org/10.1007/978-3-662-48350-3_33</a>.","apa":"Cohen Addad, V., &#38; de Mesmay, A. N. (2015). A fixed parameter tractable approximation scheme for the optimal cut graph of a surface (Vol. 9294, pp. 386–398). Presented at the ESA: European Symposium on Algorithms, Patras, Greece: Springer. <a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">https://doi.org/10.1007/978-3-662-48350-3_33</a>","ama":"Cohen Addad V, de Mesmay AN. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. In: Vol 9294. Springer; 2015:386-398. doi:<a href=\"https://doi.org/10.1007/978-3-662-48350-3_33\">10.1007/978-3-662-48350-3_33</a>"},"volume":9294,"title":"A fixed parameter tractable approximation scheme for the optimal cut graph of a surface","alternative_title":["LNCS"],"intvolume":"      9294","publication_status":"published","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:53:27Z","author":[{"last_name":"Cohen Addad","first_name":"Vincent","full_name":"Cohen Addad, Vincent"},{"full_name":"De Mesmay, Arnaud N","first_name":"Arnaud N","last_name":"De Mesmay","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87"}],"_id":"1685","scopus_import":1,"publisher":"Springer","page":"386 - 398","quality_controlled":"1","ec_funded":1},{"volume":53,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.4036"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:52:49Z","year":"2015","citation":{"ama":"Colin De Verdière É, Hubard A, de Mesmay AN. Discrete systolic inequalities and decompositions of triangulated surfaces. <i>Discrete &#38; Computational Geometry</i>. 2015;53(3):587-620. doi:<a href=\"https://doi.org/10.1007/s00454-015-9679-9\">10.1007/s00454-015-9679-9</a>","apa":"Colin De Verdière, É., Hubard, A., &#38; de Mesmay, A. N. (2015). Discrete systolic inequalities and decompositions of triangulated surfaces. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-015-9679-9\">https://doi.org/10.1007/s00454-015-9679-9</a>","ieee":"É. Colin De Verdière, A. Hubard, and A. N. de Mesmay, “Discrete systolic inequalities and decompositions of triangulated surfaces,” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 3. Springer, pp. 587–620, 2015.","chicago":"Colin De Verdière, Éric, Alfredo Hubard, and Arnaud N de Mesmay. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00454-015-9679-9\">https://doi.org/10.1007/s00454-015-9679-9</a>.","short":"É. Colin De Verdière, A. Hubard, A.N. de Mesmay, Discrete &#38; Computational Geometry 53 (2015) 587–620.","mla":"Colin De Verdière, Éric, et al. “Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces.” <i>Discrete &#38; Computational Geometry</i>, vol. 53, no. 3, Springer, 2015, pp. 587–620, doi:<a href=\"https://doi.org/10.1007/s00454-015-9679-9\">10.1007/s00454-015-9679-9</a>.","ista":"Colin De Verdière É, Hubard A, de Mesmay AN. 2015. Discrete systolic inequalities and decompositions of triangulated surfaces. Discrete &#38; Computational Geometry. 53(3), 587–620."},"date_published":"2015-04-02T00:00:00Z","type":"journal_article","doi":"10.1007/s00454-015-9679-9","day":"02","abstract":[{"lang":"eng","text":"How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations."}],"oa":1,"publist_id":"5397","page":"587 - 620","quality_controlled":"1","language":[{"iso":"eng"}],"publisher":"Springer","_id":"1730","publication":"Discrete & Computational Geometry","scopus_import":1,"author":[{"full_name":"Colin De Verdière, Éric","first_name":"Éric","last_name":"Colin De Verdière"},{"first_name":"Alfredo","last_name":"Hubard","full_name":"Hubard, Alfredo"},{"id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","last_name":"De Mesmay","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N"}],"issue":"3","publication_status":"published","oa_version":"Preprint","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:53:42Z","month":"04","title":"Discrete systolic inequalities and decompositions of triangulated surfaces","intvolume":"        53"}]