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 189, 37th International Symposium on Computational Geometry (SoCG 2021)
37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 1-978, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Proceedings{buchin_et_al:LIPIcs.SoCG.2021, title = {{LIPIcs, Volume 189, SoCG 2021, Complete Volume}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {1--978}, 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}, URN = {urn:nbn:de:0030-drops-137987}, doi = {10.4230/LIPIcs.SoCG.2021}, annote = {Keywords: LIPIcs, Volume 189, SoCG 2021, Complete Volume} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{buchin_et_al:LIPIcs.SoCG.2021.0, author = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {0:i--0:xviii}, 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.0}, URN = {urn:nbn:de:0030-drops-137993}, doi = {10.4230/LIPIcs.SoCG.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Robert Ghrist. On Laplacians (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ghrist:LIPIcs.SoCG.2021.1, author = {Ghrist, Robert}, title = {{On Laplacians}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-138003}, doi = {10.4230/LIPIcs.SoCG.2021.1}, annote = {Keywords: Laplacian, sheaf theory, applied topology} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{vassilevskawilliams:LIPIcs.SoCG.2021.2, author = {Vassilevska Williams, Virginia}, title = {{3SUM and Related Problems in Fine-Grained Complexity}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {2:1--2:2}, 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.2}, URN = {urn:nbn:de:0030-drops-138014}, doi = {10.4230/LIPIcs.SoCG.2021.2}, annote = {Keywords: fine-grained complexity} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{aamand_et_al:LIPIcs.SoCG.2021.3, author = {Aamand, Anders and Abrahamsen, Mikkel and Knudsen, Jakob B{\ae}k Tejs and Rasmussen, Peter Michael Reichstein}, title = {{Classifying Convex Bodies by Their Contact and Intersection Graphs}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-138024}, doi = {10.4230/LIPIcs.SoCG.2021.3}, annote = {Keywords: convex body, contact graph, intersection graph} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Ahmed Abdelkader and David M. Mount. Approximate Nearest-Neighbor Search for Line Segments. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abdelkader_et_al:LIPIcs.SoCG.2021.4, author = {Abdelkader, Ahmed and Mount, David M.}, title = {{Approximate Nearest-Neighbor Search for Line Segments}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {4:1--4:15}, 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.4}, URN = {urn:nbn:de:0030-drops-138039}, doi = {10.4230/LIPIcs.SoCG.2021.4}, annote = {Keywords: Approximate nearest-neighbor searching, Approximate Voronoi diagrams, Line segments, Macbeath regions} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5, author = {Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni}, title = {{Chasing Puppies: Mobile Beacon Routing on Closed Curves}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {5:1--5:19}, 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.5}, URN = {urn:nbn:de:0030-drops-138046}, doi = {10.4230/LIPIcs.SoCG.2021.5}, annote = {Keywords: Beacon routing, navigation, generic smooth curves, puppies} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Mikkel Abrahamsen and Lorenzo Beretta. Online Packing to Minimize Area or Perimeter. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.6, author = {Abrahamsen, Mikkel and Beretta, Lorenzo}, title = {{Online Packing to Minimize Area or Perimeter}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {6:1--6:15}, 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.6}, URN = {urn:nbn:de:0030-drops-138054}, doi = {10.4230/LIPIcs.SoCG.2021.6}, annote = {Keywords: Packing, online algorithms} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee, and Bodhayan Roy. Complexity of Maximum Cut on Interval Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{adhikary_et_al:LIPIcs.SoCG.2021.7, author = {Adhikary, Ranendu and Bose, Kaustav and Mukherjee, Satwik and Roy, Bodhayan}, title = {{Complexity of Maximum Cut on Interval Graphs}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {7:1--7:11}, 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.7}, URN = {urn:nbn:de:0030-drops-138067}, doi = {10.4230/LIPIcs.SoCG.2021.7}, annote = {Keywords: Maximum cut, Interval graph, NP-complete} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Peyman Afshani and Pingan Cheng. Lower Bounds for Semialgebraic Range Searching and Stabbing Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{afshani_et_al:LIPIcs.SoCG.2021.8, author = {Afshani, Peyman and Cheng, Pingan}, title = {{Lower Bounds for Semialgebraic Range Searching and Stabbing Problems}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {8:1--8:15}, 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.8}, URN = {urn:nbn:de:0030-drops-138072}, doi = {10.4230/LIPIcs.SoCG.2021.8}, annote = {Keywords: Computational Geometry, Data Structures and Algorithms} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Henk Alkema and Mark de Berg. Rectilinear Steiner Trees in Narrow Strips. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{alkema_et_al:LIPIcs.SoCG.2021.9, author = {Alkema, Henk and de Berg, Mark}, title = {{Rectilinear Steiner Trees in Narrow Strips}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {9:1--9: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.9}, URN = {urn:nbn:de:0030-drops-138081}, doi = {10.4230/LIPIcs.SoCG.2021.9}, annote = {Keywords: Computational geometry, fixed-parameter tractable algorithms} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2021.10, author = {A. Akitaya, Hugo and Demaine, Erik D. and Gonczi, Andrei and Hendrickson, Dylan H. and Hesterberg, Adam and Korman, Matias and Korten, Oliver and Lynch, Jayson and Parada, Irene and Sacrist\'{a}n, Vera}, title = {{Characterizing Universal Reconfigurability of Modular Pivoting Robots}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {10:1--10:20}, 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.10}, URN = {urn:nbn:de:0030-drops-138094}, doi = {10.4230/LIPIcs.SoCG.2021.10}, annote = {Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots} }
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)
Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12, author = {Ashur, Stav and Har-Peled, Sariel}, title = {{On Undecided LP, Clustering and Active Learning}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {12:1--12:15}, 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.12}, URN = {urn:nbn:de:0030-drops-138116}, doi = {10.4230/LIPIcs.SoCG.2021.12}, annote = {Keywords: Linear Programming, Active learning, Classification} }
Feedback for Dagstuhl Publishing