Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Kristóf Huszár and Jonathan Spreer. On the Width of Complicated JSJ Decompositions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{huszar_et_al:LIPIcs.SoCG.2023.42, author = {Husz\'{a}r, Krist\'{o}f and Spreer, Jonathan}, title = {{On the Width of Complicated JSJ Decompositions}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {42:1--42:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.42}, URN = {urn:nbn:de:0030-drops-178920}, doi = {10.4230/LIPIcs.SoCG.2023.42}, annote = {Keywords: computational 3-manifold topology, fixed-parameter tractability, generalized Heegaard splittings, JSJ decompositions, pathwidth, treewidth, triangulations} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Corentin Lunel and Arnaud de Mesmay. A Structural Approach to Tree Decompositions of Knots and Spatial Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lunel_et_al:LIPIcs.SoCG.2023.50, author = {Lunel, Corentin and de Mesmay, Arnaud}, title = {{A Structural Approach to Tree Decompositions of Knots and Spatial Graphs}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {50:1--50:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.50}, URN = {urn:nbn:de:0030-drops-179002}, doi = {10.4230/LIPIcs.SoCG.2023.50}, annote = {Keywords: Knots, Spatial Graphs, Tree Decompositions, Tangle, Representativity} }
Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)
Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck. Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062). In Dagstuhl Reports, Volume 12, Issue 2, pp. 17-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{buchin_et_al:DagRep.12.2.17, author = {Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan}, title = {{Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)}}, pages = {17--66}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {2}, editor = {Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.2.17}, URN = {urn:nbn:de:0030-drops-169305}, doi = {10.4230/DagRep.12.2.17}, annote = {Keywords: Geometric Topology, Computational Geometry, Graph Drawing, Reconfiguration, Dagstuhl Seminar} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Jean Chartier and Arnaud de Mesmay. Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chartier_et_al:LIPIcs.SoCG.2022.27, author = {Chartier, Jean and de Mesmay, Arnaud}, title = {{Finding Weakly Simple Closed Quasigeodesics on Polyhedral Spheres}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.27}, URN = {urn:nbn:de:0030-drops-160350}, doi = {10.4230/LIPIcs.SoCG.2022.27}, annote = {Keywords: Quasigeodesic, polyhedron, curve-shortening process, disk flow, weakly simple} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay. Short Topological Decompositions of Non-Orientable Surfaces. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fuladi_et_al:LIPIcs.SoCG.2022.41, author = {Fuladi, Niloufar and Hubard, Alfredo and de Mesmay, Arnaud}, title = {{Short Topological Decompositions of Non-Orientable Surfaces}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.41}, URN = {urn:nbn:de:0030-drops-160492}, doi = {10.4230/LIPIcs.SoCG.2022.41}, annote = {Keywords: Computational topology, embedded graph, non-orientable surface, joint crossing number, canonical system of loop, surface decomposition} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Éric Colin de Verdière and Thomas Magnard. An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2021.32, author = {Colin de Verdi\`{e}re, \'{E}ric and Magnard, Thomas}, title = {{An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {32:1--32:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.32}, URN = {urn:nbn:de:0030-drops-146139}, doi = {10.4230/LIPIcs.ESA.2021.32}, annote = {Keywords: computational topology, embedding, simplicial complex, graph, surface, fixed-parameter tractability} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Chien-Chung Huang, Mathieu Mari, Claire Mathieu, and Jens Vygen. Approximating Maximum Integral Multiflows on Bounded Genus Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{huang_et_al:LIPIcs.ICALP.2021.80, author = {Huang, Chien-Chung and Mari, Mathieu and Mathieu, Claire and Vygen, Jens}, title = {{Approximating Maximum Integral Multiflows on Bounded Genus Graphs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {80:1--80:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.80}, URN = {urn:nbn:de:0030-drops-141491}, doi = {10.4230/LIPIcs.ICALP.2021.80}, annote = {Keywords: Multi-commodity flows, approximation algorithms, bounded genus graphs} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11, author = {Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander}, title = {{Adjacency Graphs of Polyhedral Surfaces}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11}, URN = {urn:nbn:de:0030-drops-138107}, doi = {10.4230/LIPIcs.SoCG.2021.11}, annote = {Keywords: polyhedral complexes, realizability, contact representation} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.23, author = {Chambers, Erin Wolf and Lazarus, Francis and de Mesmay, Arnaud and Parsa, Salman}, title = {{Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.23}, URN = {urn:nbn:de:0030-drops-138223}, doi = {10.4230/LIPIcs.SoCG.2021.23}, annote = {Keywords: 3-manifolds, surfaces, low-dimensional topology, contractibility, compressed curves} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Vincent Cohen-Addad, Éric Colin de Verdière, Dániel Marx, and Arnaud de Mesmay. Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohenaddad_et_al:LIPIcs.SoCG.2019.27, author = {Cohen-Addad, Vincent and Colin de Verdi\`{e}re, \'{E}ric and Marx, D\'{a}niel and de Mesmay, Arnaud}, title = {{Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.27}, URN = {urn:nbn:de:0030-drops-104311}, doi = {10.4230/LIPIcs.SoCG.2019.27}, annote = {Keywords: Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, and Martin Tancer. The Unbearable Hardness of Unknotting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{demesmay_et_al:LIPIcs.SoCG.2019.49, author = {de Mesmay, Arnaud and Rieck, Yo'av and Sedgwick, Eric and Tancer, Martin}, title = {{The Unbearable Hardness of Unknotting}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {49:1--49:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.49}, URN = {urn:nbn:de:0030-drops-104530}, doi = {10.4230/LIPIcs.SoCG.2019.49}, annote = {Keywords: Knot, Link, NP-hard, Reidemeister move, Unknot recognition, Unlinking number, intermediate invariants} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. Finding Non-Orientable Surfaces in 3-Manifolds. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{burton_et_al:LIPIcs.SoCG.2016.24, author = {Burton, Benjamin A. and de Mesmay, Arnaud and Wagner, Uli}, title = {{Finding Non-Orientable Surfaces in 3-Manifolds}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.24}, URN = {urn:nbn:de:0030-drops-59168}, doi = {10.4230/LIPIcs.SoCG.2016.24}, annote = {Keywords: 3-manifold, low-dimensional topology, embedding, non-orientability, normal surfaces} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{hubard_et_al:LIPIcs.SoCG.2016.43, author = {Hubard, Alfredo and Kalu\v{z}a, Vojtech and de Mesmay, Arnaud and Tancer, Martin}, title = {{Shortest Path Embeddings of Graphs on Surfaces}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.43}, URN = {urn:nbn:de:0030-drops-59356}, doi = {10.4230/LIPIcs.SoCG.2016.43}, annote = {Keywords: Graph embedding, surface, shortest path, crossing number, hyperbolic geometry} }
Feedback for Dagstuhl Publishing