Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes Is ∃ℝ-Complete. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1:1-1:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.1, author = {Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann}, title = {{Geometric Embeddability of Complexes Is \exists\mathbb{R}-Complete}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {1:1--1:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.1}, URN = {urn:nbn:de:0030-drops-178518}, doi = {10.4230/LIPIcs.SoCG.2023.1}, annote = {Keywords: simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer. Parameterized Complexity of Untangling Knots. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 88:1-88:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{legrandduchesne_et_al:LIPIcs.ICALP.2022.88, author = {Legrand-Duchesne, Cl\'{e}ment and Rai, Ashutosh and Tancer, Martin}, title = {{Parameterized Complexity of Untangling Knots}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {88:1--88:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.88}, URN = {urn:nbn:de:0030-drops-164296}, doi = {10.4230/LIPIcs.ICALP.2022.88}, annote = {Keywords: unknot recognition, parameterized complexity, Reidemeister moves, W\lbrackP\rbrack-complete} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Denys Bulavka, Afshin Goodarzi, and Martin Tancer. Optimal Bounds for the Colorful Fractional Helly Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 19:1-19:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bulavka_et_al:LIPIcs.SoCG.2021.19, author = {Bulavka, Denys and Goodarzi, Afshin and Tancer, Martin}, title = {{Optimal Bounds for the Colorful Fractional Helly Theorem}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {19:1--19:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.19}, URN = {urn:nbn:de:0030-drops-138186}, doi = {10.4230/LIPIcs.SoCG.2021.19}, annote = {Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Zuzana Patáková, Martin Tancer, and Uli Wagner. Barycentric Cuts Through a Convex Body. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{patakova_et_al:LIPIcs.SoCG.2020.62, author = {Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli}, title = {{Barycentric Cuts Through a Convex Body}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {62:1--62:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.62}, URN = {urn:nbn:de:0030-drops-122201}, doi = {10.4230/LIPIcs.SoCG.2020.62}, annote = {Keywords: convex body, barycenter, Tukey depth, smooth manifold, critical points} }
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.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 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Shellability is NP-Complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 41:1-41:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{goaoc_et_al:LIPIcs.SoCG.2018.41, author = {Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli}, title = {{Shellability is NP-Complete}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {41:1--41:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.41}, URN = {urn:nbn:de:0030-drops-87542}, doi = {10.4230/LIPIcs.SoCG.2018.41}, annote = {Keywords: Shellability, simplicial complexes, NP-completeness, collapsibility} }
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.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} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 476-490, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.476, author = {Goaoc, Xavier and Mabillard, Isaac and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli}, title = {{On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {476--490}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.476}, URN = {urn:nbn:de:0030-drops-51256}, doi = {10.4230/LIPIcs.SOCG.2015.476}, annote = {Keywords: Heawood Inequality, Embeddings, Van Kampen–Flores, Manifolds} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly Numbers via Betti Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 507-521, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.507, author = {Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli}, title = {{Bounding Helly Numbers via Betti Numbers}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {507--521}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.507}, URN = {urn:nbn:de:0030-drops-51297}, doi = {10.4230/LIPIcs.SOCG.2015.507}, annote = {Keywords: Helly-type theorem, Ramsey’s theorem, Embedding of simplicial complexes, Homological almost-embedding, Betti numbers} }
Feedback for Dagstuhl Publishing