LIPIcs, Volume 164
SoCG 2020, June 23-26, 2020, Zürich, Switzerland
Editors: Sergio Cabello and Danny Z. Chen
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Cezar-Mihail Alexandru and Christian Konrad. Interval Selection in Sliding Windows. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alexandru_et_al:LIPIcs.ESA.2024.8, author = {Alexandru, Cezar-Mihail and Konrad, Christian}, title = {{Interval Selection in Sliding Windows}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.8}, URN = {urn:nbn:de:0030-drops-210795}, doi = {10.4230/LIPIcs.ESA.2024.8}, annote = {Keywords: Sliding window algorithms, Streaming algorithms, Interval selection} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Shinwoo An, Eunjin Oh, and Jie Xue. Sparse Outerstring Graphs Have Logarithmic Treewidth. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{an_et_al:LIPIcs.ESA.2024.10, author = {An, Shinwoo and Oh, Eunjin and Xue, Jie}, title = {{Sparse Outerstring Graphs Have Logarithmic Treewidth}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.10}, URN = {urn:nbn:de:0030-drops-210816}, doi = {10.4230/LIPIcs.ESA.2024.10}, annote = {Keywords: Outerstring graphs, geometric intersection graphs, treewidth} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{duraj_et_al:LIPIcs.ESA.2024.51, author = {Duraj, Lech and Konieczny, Filip and Pot\k{e}pa, Krzysztof}, title = {{Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {51:1--51:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.51}, URN = {urn:nbn:de:0030-drops-211229}, doi = {10.4230/LIPIcs.ESA.2024.51}, annote = {Keywords: Graph Diameter, Geometric Intersection Graphs, Vapnik-Chervonenkis Dimension} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-Order Online Independent Set of Intervals and Hyperrectangles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{garg_et_al:LIPIcs.ESA.2024.58, author = {Garg, Mohit and Kar, Debajyoti and Khan, Arindam}, title = {{Random-Order Online Independent Set of Intervals and Hyperrectangles}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {58:1--58:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.58}, URN = {urn:nbn:de:0030-drops-211298}, doi = {10.4230/LIPIcs.ESA.2024.58}, annote = {Keywords: Online Algorithms, Random-Order Model, Maximum Independent Set of Rectangles, Hyperrectangles, Fat Objects, Interval Scheduling} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng. Shortest Path Separators in Unit Disk Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{harb_et_al:LIPIcs.ESA.2024.66, author = {Harb, Elfarouk and Huang, Zhengcheng and Zheng, Da Wei}, title = {{Shortest Path Separators in Unit Disk Graphs}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {66:1--66:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.66}, URN = {urn:nbn:de:0030-drops-211375}, doi = {10.4230/LIPIcs.ESA.2024.66}, annote = {Keywords: Balanced shortest path separators, unit disk graphs, crossings} }
Published in: LIPIcs, Volume 315, 16th International Conference on Spatial Information Theory (COSIT 2024)
Steven van den Broek, Wouter Meulemans, Andreas Reimer, and Bettina Speckmann. Scalable Harmonious Simplification of Isolines. In 16th International Conference on Spatial Information Theory (COSIT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 315, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{vandenbroek_et_al:LIPIcs.COSIT.2024.8, author = {van den Broek, Steven and Meulemans, Wouter and Reimer, Andreas and Speckmann, Bettina}, title = {{Scalable Harmonious Simplification of Isolines}}, booktitle = {16th International Conference on Spatial Information Theory (COSIT 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-330-0}, ISSN = {1868-8969}, year = {2024}, volume = {315}, editor = {Adams, Benjamin and Griffin, Amy L. and Scheider, Simon and McKenzie, Grant}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2024.8}, URN = {urn:nbn:de:0030-drops-208230}, doi = {10.4230/LIPIcs.COSIT.2024.8}, annote = {Keywords: Simplification, isolines, harmony} }
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} }
Feedback for Dagstuhl Publishing