LIPIcs, Volume 99
SoCG 2018, June 11-14, 2018, Budapest, Hungary
Editors: Bettina Speckmann and Csaba D. Tóth
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill. Reconfiguration of Polygonal Subdivisions via Recombination. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2023.6, author = {A. Akitaya, Hugo and Gonczi, Andrei and Souvaine, Diane L. and T\'{o}th, Csaba D. and Weighill, Thomas}, title = {{Reconfiguration of Polygonal Subdivisions via Recombination}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.6}, URN = {urn:nbn:de:0030-drops-186598}, doi = {10.4230/LIPIcs.ESA.2023.6}, annote = {Keywords: configuration space, gerrymandering, polygonal subdivision, recombination} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth. Online Spanners in Metric Spaces. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhore_et_al:LIPIcs.ESA.2022.18, author = {Bhore, Sujoy and Filtser, Arnold and Khodabandeh, Hadi and T\'{o}th, Csaba D.}, title = {{Online Spanners in Metric Spaces}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {18:1--18:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.18}, URN = {urn:nbn:de:0030-drops-169564}, doi = {10.4230/LIPIcs.ESA.2022.18}, annote = {Keywords: spanner, online algorithm, lightness, sparsity, minimum weight} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Jonathan B. Conroy and Csaba D. Tóth. Hop-Spanners for Geometric Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{conroy_et_al:LIPIcs.SoCG.2022.30, author = {Conroy, Jonathan B. and T\'{o}th, Csaba D.}, title = {{Hop-Spanners for Geometric Intersection Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {30:1--30:17}, 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.30}, URN = {urn:nbn:de:0030-drops-160381}, doi = {10.4230/LIPIcs.SoCG.2022.30}, annote = {Keywords: geometric intersection graph, unit disk graph, hop-spanner} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Sujoy Bhore and Csaba D. Tóth. Online Euclidean Spanners. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhore_et_al:LIPIcs.ESA.2021.16, author = {Bhore, Sujoy and T\'{o}th, Csaba D.}, title = {{Online Euclidean Spanners}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {16:1--16:19}, 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.16}, URN = {urn:nbn:de:0030-drops-145974}, doi = {10.4230/LIPIcs.ESA.2021.16}, annote = {Keywords: Geometric spanner, (1+\epsilon)-spanner, minimum weight, online algorithm} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Christoph Damerius, Dominik Kaaser, Peter Kling, and Florian Schneider. On Greedily Packing Anchored Rectangles. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{damerius_et_al:LIPIcs.ICALP.2021.61, author = {Damerius, Christoph and Kaaser, Dominik and Kling, Peter and Schneider, Florian}, title = {{On Greedily Packing Anchored Rectangles}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {61:1--61:20}, 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.61}, URN = {urn:nbn:de:0030-drops-141306}, doi = {10.4230/LIPIcs.ICALP.2021.61}, annote = {Keywords: lower-left anchored rectangle packing, greedy algorithm, charging scheme} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Sujoy Bhore and Csaba D. Tóth. Light Euclidean Steiner Spanners in the Plane. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhore_et_al:LIPIcs.SoCG.2021.15, author = {Bhore, Sujoy and T\'{o}th, Csaba D.}, title = {{Light Euclidean Steiner Spanners in the Plane}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {15:1--15: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.15}, URN = {urn:nbn:de:0030-drops-138145}, doi = {10.4230/LIPIcs.SoCG.2021.15}, annote = {Keywords: Geometric spanner, lightness, minimum weight} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Sujoy Bhore and Csaba D. Tóth. On Euclidean Steiner (1+ε)-Spanners. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhore_et_al:LIPIcs.STACS.2021.13, author = {Bhore, Sujoy and T\'{o}th, Csaba D.}, title = {{On Euclidean Steiner (1+\epsilon)-Spanners}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.13}, URN = {urn:nbn:de:0030-drops-136586}, doi = {10.4230/LIPIcs.STACS.2021.13}, annote = {Keywords: Geometric spanner, (1+\epsilon)-spanner, lightness, sparsity, minimum weight} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth. Sparse Hop Spanners for Unit Disk Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dumitrescu_et_al:LIPIcs.ISAAC.2020.57, author = {Dumitrescu, Adrian and Ghosh, Anirban and T\'{o}th, Csaba D.}, title = {{Sparse Hop Spanners for Unit Disk Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {57:1--57:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.57}, URN = {urn:nbn:de:0030-drops-134018}, doi = {10.4230/LIPIcs.ISAAC.2020.57}, annote = {Keywords: graph approximation, \epsilon-net, hop-spanner, unit disk graph, lower bound} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, and Csaba D. Tóth. Cutting Polygons into Small Pieces with Chords: Laser-Based Localization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arkin_et_al:LIPIcs.ESA.2020.7, author = {Arkin, Esther M. and Das, Rathish and Gao, Jie and Goswami, Mayank and Mitchell, Joseph S. B. and Polishchuk, Valentin and T\'{o}th, Csaba D.}, title = {{Cutting Polygons into Small Pieces with Chords: Laser-Based Localization}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {7:1--7:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.7}, URN = {urn:nbn:de:0030-drops-128736}, doi = {10.4230/LIPIcs.ESA.2020.7}, annote = {Keywords: Polygon partition, Arrangements, Visibility, Localization} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.MFCS.2019.56, author = {Chen, Ke and Dumitrescu, Adrian and Mulzer, Wolfgang and T\'{o}th, Csaba D.}, title = {{On the Stretch Factor of Polygonal Chains}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56}, URN = {urn:nbn:de:0030-drops-110005}, doi = {10.4230/LIPIcs.MFCS.2019.56}, annote = {Keywords: polygonal chain, vertex dilation, Koch curve, recursive construction} }
Published in: Dagstuhl Reports, Volume 9, Issue 2 (2019)
Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth. Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092). In Dagstuhl Reports, Volume 9, Issue 2, pp. 123-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{hong_et_al:DagRep.9.2.123, author = {Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.}, title = {{Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)}}, pages = {123--156}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {2}, editor = {Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.2.123}, URN = {urn:nbn:de:0030-drops-108634}, doi = {10.4230/DagRep.9.2.123}, annote = {Keywords: combinatorial geometry, geometric algorithms, graph algorithms, graph drawing, graph theory, network visualization} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Hugo A. Akitaya, Matias Korman, Mikhail Rudoy, Diane L. Souvaine, and Csaba D. Tóth. Circumscribing Polygons and Polygonizations for Disjoint Line Segments. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2019.9, author = {Akitaya, Hugo A. and Korman, Matias and Rudoy, Mikhail and Souvaine, Diane L. and T\'{o}th, Csaba D.}, title = {{Circumscribing Polygons and Polygonizations for Disjoint Line Segments}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {9:1--9:17}, 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.9}, URN = {urn:nbn:de:0030-drops-104136}, doi = {10.4230/LIPIcs.SoCG.2019.9}, annote = {Keywords: circumscribing polygon, Hamiltonicity, extremal combinatorics} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22, author = {De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander}, title = {{Convex Polygons in Cartesian Products}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {22:1--22:17}, 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.22}, URN = {urn:nbn:de:0030-drops-104267}, doi = {10.4230/LIPIcs.SoCG.2019.22}, annote = {Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth. Maximum Area Axis-Aligned Square Packings. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{akitaya_et_al:LIPIcs.MFCS.2018.77, author = {Akitaya, Hugo A. and Jones, Matthew D. and Stalfa, David and T\'{o}th, Csaba D.}, title = {{Maximum Area Axis-Aligned Square Packings}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {77:1--77:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul 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.MFCS.2018.77}, URN = {urn:nbn:de:0030-drops-96594}, doi = {10.4230/LIPIcs.MFCS.2018.77}, annote = {Keywords: square packing, geometric optimization} }
Feedback for Dagstuhl Publishing