LIPIcs, Volume 164
SoCG 2020, June 23-26, 2020, Zürich, Switzerland
Editors: Sergio Cabello and Danny Z. Chen
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6, author = {Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra}, title = {{Faster Treewidth-Based Approximations for Wiener Index}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {6:1--6:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6}, URN = {urn:nbn:de:0030-drops-203718}, doi = {10.4230/LIPIcs.SEA.2024.6}, annote = {Keywords: Computational Chemistry, Treewidth, Wiener Index} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Pankaj K. Agarwal, Esther Ezra, and Micha Sharir. Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2024.4, author = {Agarwal, Pankaj K. and Ezra, Esther and Sharir, Micha}, title = {{Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.4}, URN = {urn:nbn:de:0030-drops-199497}, doi = {10.4230/LIPIcs.SoCG.2024.4}, annote = {Keywords: Range-searching, semi-algebraic sets, pseudo-lines, duality, geometric cuttings} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Sergio Cabello, Siu-Wing Cheng, Otfried Cheong, and Christian Knauer. Geometric Matching and Bottleneck Problems. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cabello_et_al:LIPIcs.SoCG.2024.31, author = {Cabello, Sergio and Cheng, Siu-Wing and Cheong, Otfried and Knauer, Christian}, title = {{Geometric Matching and Bottleneck Problems}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {31:1--31:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.31}, URN = {urn:nbn:de:0030-drops-199768}, doi = {10.4230/LIPIcs.SoCG.2024.31}, annote = {Keywords: Many-to-many matching, bipartite, planar, geometric, approximation} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating Crossings in Ordered Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{agrawal_et_al:LIPIcs.SWAT.2024.1, author = {Agrawal, Akanksha and Cabello, Sergio and Kaufmann, Michael and Saurabh, Saket and Sharma, Roohani and Uno, Yushi and Wolff, Alexander}, title = {{Eliminating Crossings in Ordered Graphs}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.1}, URN = {urn:nbn:de:0030-drops-200417}, doi = {10.4230/LIPIcs.SWAT.2024.1}, annote = {Keywords: Ordered graphs, book embedding, edge deletion, d-planar, hitting set} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Sergio Cabello and Panos Giannopoulos. On k-Means for Segments and Polylines. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cabello_et_al:LIPIcs.ESA.2023.28, author = {Cabello, Sergio and Giannopoulos, Panos}, title = {{On k-Means for Segments and Polylines}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {28:1--28:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.28}, URN = {urn:nbn:de:0030-drops-186812}, doi = {10.4230/LIPIcs.ESA.2023.28}, annote = {Keywords: k-means clustering, segments, polylines, Hausdorff distance, Fr\'{e}chet mean} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Sergio Cabello, Michael Hoffmann, Katharina Klost, Wolfgang Mulzer, and Josef Tkadlec. Long Plane Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cabello_et_al:LIPIcs.SoCG.2022.23, author = {Cabello, Sergio and Hoffmann, Michael and Klost, Katharina and Mulzer, Wolfgang and Tkadlec, Josef}, title = {{Long Plane Trees}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {23:1--23: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.23}, URN = {urn:nbn:de:0030-drops-160311}, doi = {10.4230/LIPIcs.SoCG.2022.23}, annote = {Keywords: geometric network design, spanning trees, plane straight-line graphs, approximation algorithms} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Sergio Cabello. Some Open Problems in Computational Geometry (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 2:1-2:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cabello:LIPIcs.MFCS.2020.2, author = {Cabello, Sergio}, title = {{Some Open Problems in Computational Geometry}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {2:1--2:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.2}, URN = {urn:nbn:de:0030-drops-126734}, doi = {10.4230/LIPIcs.MFCS.2020.2}, annote = {Keywords: barrier resilience, maximum matching, geometric graphs, fixed-parameter tractability, stochastic computational geometry} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1-1222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Proceedings{cabello_et_al:LIPIcs.SoCG.2020, title = {{LIPIcs, Volume 164, SoCG 2020, Complete Volume}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {1--1222}, 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}, URN = {urn:nbn:de:0030-drops-121576}, doi = {10.4230/LIPIcs.SoCG.2020}, annote = {Keywords: LIPIcs, Volume 164, SoCG 2020, Complete Volume} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{cabello_et_al:LIPIcs.SoCG.2020.0, author = {Cabello, Sergio and Chen, Danny Z.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {0:i--0:xx}, 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.0}, URN = {urn:nbn:de:0030-drops-121587}, doi = {10.4230/LIPIcs.SoCG.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1, author = {Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter}, title = {{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {1:1--1:18}, 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.1}, URN = {urn:nbn:de:0030-drops-121591}, doi = {10.4230/LIPIcs.SoCG.2020.1}, annote = {Keywords: Simple polygon, Ramsey theory, combinatorial geometry} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic Geometric Set Cover and Hitting Set. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2020.2, author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Suri, Subhash and Xiao, Allen and Xue, Jie}, title = {{Dynamic Geometric Set Cover and Hitting Set}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {2:1--2:15}, 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.2}, URN = {urn:nbn:de:0030-drops-121604}, doi = {10.4230/LIPIcs.SoCG.2020.2}, annote = {Keywords: Geometric set cover, Geometric hitting set, Dynamic data structures} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. The Parameterized Complexity of Guarding Almost Convex Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{agrawal_et_al:LIPIcs.SoCG.2020.3, author = {Agrawal, Akanksha and Knudsen, Kristine V. K. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav}, title = {{The Parameterized Complexity of Guarding Almost Convex Polygons}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-121614}, doi = {10.4230/LIPIcs.SoCG.2020.3}, annote = {Keywords: Art Gallery, Reflex vertices, Monotone 2-CSP, Parameterized Complexity, Fixed Parameter Tractability} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4, author = {Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor}, title = {{Euclidean TSP in Narrow Strips}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {4:1--4: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.4}, URN = {urn:nbn:de:0030-drops-121628}, doi = {10.4230/LIPIcs.SoCG.2020.4}, annote = {Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, and Yelena Yuditsky. The ε-t-Net Problem. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alon_et_al:LIPIcs.SoCG.2020.5, author = {Alon, Noga and Jartoux, Bruno and Keller, Chaya and Smorodinsky, Shakhar and Yuditsky, Yelena}, title = {{The \epsilon-t-Net Problem}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {5:1--5:15}, 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.5}, URN = {urn:nbn:de:0030-drops-121639}, doi = {10.4230/LIPIcs.SoCG.2020.5}, annote = {Keywords: epsilon-nets, geometric hypergraphs, VC-dimension, linear union complexity} }