Document

Invited Talk

**Published in:** LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Planar graphs have been fertile grounds for algorithms research for decades, both because they model several types of real-world networks, and because they admit simpler and and faster algorithms than arbitrary graphs. Many important structural properties of planar graphs extend naturally to graphs that embed on more complex surfaces. As a result, efficient algorithms for planar graphs often extend naturally to higher-genus surface graphs with little or no modification.
I will describe a few of my favorite exceptions to this rule - classical problems that admit simple, efficient, and practical algorithms for planar graphs, but where algorithms for graphs on other surfaces are significantly slower and/or more complex.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

We consider three classes of geodesic embeddings of graphs on Euclidean flat tori:
- A torus graph G is equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of G sum to zero.
- A torus graph G is reciprocal if there is a geodesic embedding of the dual graph G^* on the same flat torus, where each edge of G is orthogonal to the corresponding dual edge in G^*.
- A torus graph G is coherent if it is possible to assign weights to the vertices, so that G is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to G being the projection of the 1-skeleton of the lower convex hull of points in ℝ³. However, this three-way equivalence does not extend directly to geodesic graphs on flat tori. On any flat torus, reciprocal and coherent graphs are equivalent, and every reciprocal graph is equilibrium, but not every equilibrium graph is reciprocal. We establish a weaker correspondence: Every equilibrium graph on any flat torus is affinely equivalent to a reciprocal/coherent graph on some flat torus.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 4 (2019)

This report documents the program and the outcomes of Dagstuhl Seminar 19181 "Computational Geometry". The seminar was held from April 28 to May 3, 2019 and 40 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

We strengthen the connections between electrical transformations and homotopy from the planar setting - observed and studied since Steinitz - to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an n-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous Omega(n^{3/2}) lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier Omega(n^{3/2}) lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follow from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number beta. We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O(n+m) time, or a contractible closed walk in O(n+m) time, or a bounding closed walk in O(beta (n+m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G^*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard.
We also describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g^2L^2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g >= 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** Dagstuhl Reports, Volume 7, Issue 4 (2018)

This report documents the program and the outcomes of Dagstuhl Seminar 17171 "Computational Geometry". The seminar was held from 23rd to 28th April 2017 and 47 participants from various countries attended it. Recent advances in computational geometry were presented and new challenges were identified. The report collects the abstracts of talks and open problems presented in the seminar.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** Dagstuhl Reports, Volume 6, Issue 5 (2016)

This report documents the program and the outcomes of Dagstuhl Seminar 16221
“Algorithms for Optimization Problems in Planar Graphs”. The seminar was held from May 29 to June 3, 2016. This report contains abstracts for the recent developments in planar graph algorithms discussed during the seminar as well as summaries of open problems in this area of research.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

We present an O(n log n)-time algorithm that determines whether a given planar n-gon is weakly simple. This improves upon an O(n^2 log n)-time algorithm by [Chang, Erickson, and Xu, SODA, 2015]. Weakly simple polygons are required as input for several geometric algorithms. As such, how to recognize simple or weakly simple polygons is a fundamental question.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with n self-crossings requires Theta(n^{3/2}) homotopy moves in the worst case. Our algorithm improves the best previous upper bound O(n^2), which is already implicit in the classical work of Steinitz; the matching lower bound follows from the construction of closed curves with large defect, a topological invariant of generic closed curves introduced by Aicardi and Arnold. This lower bound also implies that Omega(n^{3/2}) degree-1 reductions, series-parallel reductions, and Delta-Y transformations are required to reduce any planar graph with treewidth Omega(sqrt{n}) to a single edge, matching known upper bounds for rectangular and cylindrical grid graphs. Finally, we prove that Omega(n^2) homotopy moves are required in the worst case to transform one non-contractible closed curve on the torus to another; this lower bound is tight if the curve is homotopic to a simple closed curve.

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)

Copy BibTex To Clipboard

@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} }

Document

**Published in:** Dagstuhl Reports, Volume 5, Issue 3 (2015)

This report documents the program and the outcomes of Dagstuhl Seminar 15111 "Computational Geometry". The seminar was held from 8th to 13th March 2015 and 41 senior and young researchers from various countries and continents attended it. Recent developments in the field were presented and new challenges in computational geometry were identified.

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)

Copy BibTex To Clipboard

@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} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail