Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95, author = {Karczmarz, Adam and Smulewicz, Marcin}, title = {{Fully Dynamic Strongly Connected Components in Planar Digraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {95:1--95:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95}, URN = {urn:nbn:de:0030-drops-202388}, doi = {10.4230/LIPIcs.ICALP.2024.95}, annote = {Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Jeff Erickson. The Tragedy of Being Almost but Not Quite Planar (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{erickson:LIPIcs.ISAAC.2022.2, author = {Erickson, Jeff}, title = {{The Tragedy of Being Almost but Not Quite Planar}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.2}, URN = {urn:nbn:de:0030-drops-172875}, doi = {10.4230/LIPIcs.ISAAC.2022.2}, annote = {Keywords: planar graphs, surface graphs, algorithms, open problems} }
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.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)
Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.23, author = {Chambers, Erin Wolf and Lazarus, Francis and de Mesmay, Arnaud and Parsa, Salman}, title = {{Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {23:1--23: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.23}, URN = {urn:nbn:de:0030-drops-138223}, doi = {10.4230/LIPIcs.SoCG.2021.23}, annote = {Keywords: 3-manifolds, surfaces, low-dimensional topology, contractibility, compressed curves} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening Flow. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{avvakumov_et_al:LIPIcs.SoCG.2020.12, author = {Avvakumov, Sergey and Nivasch, Gabriel}, title = {{Homotopic Curve Shortening and the Affine Curve-Shortening Flow}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {12:1--12: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.12}, URN = {urn:nbn:de:0030-drops-121708}, doi = {10.4230/LIPIcs.SoCG.2020.12}, annote = {Keywords: affine curve-shortening flow, shortest homotopic path, integer grid, convex-layer decomposition} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Jeff Erickson and Patrick Lin. A Toroidal Maxwell-Cremona-Delaunay Correspondence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{erickson_et_al:LIPIcs.SoCG.2020.40, author = {Erickson, Jeff and Lin, Patrick}, title = {{A Toroidal Maxwell-Cremona-Delaunay Correspondence}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {40:1--40:17}, 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.40}, URN = {urn:nbn:de:0030-drops-121984}, doi = {10.4230/LIPIcs.SoCG.2020.40}, annote = {Keywords: combinatorial topology, geometric graphs, homology, flat torus, spring embedding, intrinsic Delaunay} }
Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)
Siu-Wing Cheng, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 19181). In Dagstuhl Reports, Volume 9, Issue 4, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{cheng_et_al:DagRep.9.4.107, author = {Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff}, title = {{Computational Geometry (Dagstuhl Seminar 19181)}}, pages = {107--123}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {4}, editor = {Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.4.107}, URN = {urn:nbn:de:0030-drops-113064}, doi = {10.4230/DagRep.9.4.107}, annote = {Keywords: Computational geometry, polynomial partition, geometric data structures, approximation} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chang_et_al:LIPIcs.SoCG.2019.25, author = {Chang, Hsien-Chih and Cossarini, Marcos and Erickson, Jeff}, title = {{Lower Bounds for Electrical Reduction on Surfaces}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {25:1--25:16}, 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.25}, URN = {urn:nbn:de:0030-drops-104294}, doi = {10.4230/LIPIcs.SoCG.2019.25}, annote = {Keywords: electrical transformation, Delta-Y-transformation, homotopy, tight, defect, SPQR-tree, smoothings, routing set, 2-flipping} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Jeff Erickson and Yipu Wang. Topologically Trivial Closed Walks in Directed Surface Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{erickson_et_al:LIPIcs.SoCG.2019.34, author = {Erickson, Jeff and Wang, Yipu}, title = {{Topologically Trivial Closed Walks in Directed Surface Graphs}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {34:1--34: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.34}, URN = {urn:nbn:de:0030-drops-104383}, doi = {10.4230/LIPIcs.SoCG.2019.34}, annote = {Keywords: computational topology, surface-embedded graphs, homotopy, homology, strong connectivity, hyperbolic geometry, medial axes, context-free grammars} }
Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)
Orfried Cheong, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 17171). In Dagstuhl Reports, Volume 7, Issue 4, pp. 107-127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{cheong_et_al:DagRep.7.4.107, author = {Cheong, Orfried and Driemel, Anne and Erickson, Jeff}, title = {{Computational Geometry (Dagstuhl Seminar 17171)}}, pages = {107--127}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {4}, editor = {Cheong, Orfried and Driemel, Anne and Erickson, Jeff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.4.107}, URN = {urn:nbn:de:0030-drops-82771}, doi = {10.4230/DagRep.7.4.107}, annote = {Keywords: algorithms, applications, combinatorics, complexity, geometric computing, high-dimensional computational geometry, implementation, monitoring and shape data} }
Published in: Dagstuhl Reports, Volume 6, Issue 5 (2016)
Jeff Erickson, Philip N. Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). In Dagstuhl Reports, Volume 6, Issue 5, pp. 94-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{erickson_et_al:DagRep.6.5.94, author = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, title = {{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221)}}, pages = {94--113}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {6}, number = {5}, editor = {Erickson, Jeff and Klein, Philip N. and Marx, D\'{a}niel and Mathieu, Claire}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.5.94}, URN = {urn:nbn:de:0030-drops-67227}, doi = {10.4230/DagRep.6.5.94}, annote = {Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing Weakly Simple Polygons. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{akitaya_et_al:LIPIcs.SoCG.2016.8, author = {Akitaya, Hugo A. and Aloupis, Greg and Erickson, Jeff and T\'{o}th, Csaba}, title = {{Recognizing Weakly Simple Polygons}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {8:1--8: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.8}, URN = {urn:nbn:de:0030-drops-59003}, doi = {10.4230/LIPIcs.SoCG.2016.8}, annote = {Keywords: weakly simple polygon, crossing} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Hsien-Chih Chang and Jeff Erickson. Untangling Planar Curves. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chang_et_al:LIPIcs.SoCG.2016.29, author = {Chang, Hsien-Chih and Erickson, Jeff}, title = {{Untangling Planar Curves}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {29:1--29: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.29}, URN = {urn:nbn:de:0030-drops-59218}, doi = {10.4230/LIPIcs.SoCG.2016.29}, annote = {Keywords: computational topology, homotopy, planar graphs, Delta-Y transformations, defect, Reidemeister moves, tangles} }
Published in: Dagstuhl Reports, Volume 5, Issue 3 (2015)
Otfried Cheong, Jeff Erickson, and Monique Teillaud. Computational Geometry (Dagstuhl Seminar 15111). In Dagstuhl Reports, Volume 5, Issue 3, pp. 41-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{cheong_et_al:DagRep.5.3.41, author = {Cheong, Otfried and Erickson, Jeff and Teillaud, Monique}, title = {{Computational Geometry (Dagstuhl Seminar 15111)}}, pages = {41--62}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {5}, number = {3}, editor = {Cheong, Otfried and Erickson, Jeff and Teillaud, Monique}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.3.41}, URN = {urn:nbn:de:0030-drops-52689}, doi = {10.4230/DagRep.5.3.41}, annote = {Keywords: Algorithms, geometry, theory, approximation, implementation, combinatorics, topology} }