Jeff Erickson

Curriculum Vitæ

Sohaib and Sara Abbasi Professor http://jeffe.cs.illinois.edu

Siebel School of Computing and Data Science jeffe@illinois.edu
University of Illinois Urbana-Champaign +1 (217) 333-6769
201 North Goodwin Ave.
Urbana, IL 61801-2302 USA he/him

Research Interests
Algorithms, data structures, and lower bounds; computational and discrete geometry and topology;
topological graph theory; combinatorial optimization; applications of geometry, topology, and optimization
to computer graphics, robotics, spatial databases, and mesh generation; computer science education

Education
1992–1996 University of California, Berkeley: Ph.D. in Computer Science, July 1996
Advisor: Raimund Seidel
1990–1992 University of California, Irvine: M.S. in Information and Computer Science, June 1992
Advisor: David Eppstein
1983–1987 Rice University: B.A. in Computer Science/Mathematical Sciences (double major), May 1987

Employment
since 1998 Department of Computer Science, University of Illinois Urbana-Champaign
since 2020 Sohaib and Sara Abbasi Professor
2013–2016 Associate department head
since 2010 Professor
2004–2010 Associate professor
1998–2004 Assistant professor
1996–1998 Postdoctoral research associate, Center for Geometric Computing, Department of Computer
Science, Duke University
1992–1996 Graduate student researcher and graduate student instructor, Computer Science Division,
University of California, Berkeley
1990–1992 Graduate student researcher and graduate student instructor, Department of Information
and Computer Science, University of California, Irvine
1988–1990 Software engineer, Claris Corporation, Santa Clara, CA (MacWrite II, MacWrite Pro, XTND)
1986–1988 Software engineer, StyleWare, Inc., Houston, TX (TopDraw, AppleWorks GS)
1984–1986 Laboratory assistant, Computer Science Department, Rice University

Visiting Positions
Jan–May 2019 Department of Computer Science, Universiteit Utrecht, Netherlands
Oct 2011, Mar 2012 Visiting professor, École Normale Supérieure, Paris, France
Aug 2011–Jun 2012 Institute of Science and Technology, Austria
Mar–Jun 2005 Fachbereich Informatik, Freie Universität Berlin, Germany

Last updated June 3, 2024. See http://jeffe.cs.illinois.edu/cv.pdf for the most recent version.
Jeff Erickson Curriculum Vitæ

Nov 2004–Feb 2005 Computer Science Department, Polytechnic University, Brooklyn, New York
Aug–Nov 2004 Research associate, Laboratoire lorrain de recherche en informatique et ses applica-
tions (LORIA), Nancy, France
Aug–Dec 1994 Research assistant, Fachbereich Informatik, Universität des Saarlandes, and
(unofficially) Max-Planck-Institut für Informatik, Saarbrücken, Germany

Awards and Honors

National

2001–2006 National Science Foundation CAREER Award (CCR-0093348)

1999–2002 Alfred P. Sloan Research Fellowship
1996–1998 NSF Mathematical Sciences Postdoctoral Research Fellowship (DMS-9627683)
1983–1987 National Merit Scholarship

Department, College, and University

27 out of 44 semesters of instruction

List of Teachers Ranked as Excellent by Their Students, University of Illinois Urbana-
Champaign. Includes “outstanding” ratings in Spring 2001, Spring 2015, Spring 2017, Fall
2020, and Fall 2022.
since 2020 Sohaib and Sara Abbasi Professorship, Department of Computer Science, University of
Illinois Urbana-Champaign
2017–2018, 2019–2021
Education Innovation Fellow, Grainger College of Engineering, University of Illinois Urbana-
Champaign
April 2010 Xerox Award for (Senior) Faculty Research, College of Engineering, University of Illinois
Urbana-Champaign
May 2007 Campus Award for Excellence in Undergraduate Teaching, University of Illinois Urbana-
Champaign (one of five awards campus-wide)
April 2006 Honorable mention, Campus Award for Excellence in Graduate and Professional Teaching,
University of Illinois Urbana-Champaign
Fall 2002 Computer Science Graduate Student Organization 2002–2003 T-shirt design, Computer
Science Department, University of Illinois Urbana-Champaign. (See my web page.)
2002–2009 Willett Faculty Scholar Award, College of Engineering, University of Illinois Urbana-
Champaign
April 2001 C. W. Gear Outstanding Junior Faculty Award, Department of Computer Science, University
of Illinois Urbana-Champaign
April 2001 William L. Everitt Award for Teaching Excellence, Engineering Council, College of Engineering
University of Illinois Urbana-Champaign (nominated and selected by students)
1995–1996 Graduate Assistance in Areas of National Need Fellowship, Computer Science, University of
California, Berkeley
1991–1992 University of California Regents Fellowship

Students’ Awards and Honors

2020–2025 Emily Kyle Fox (Ph.D. 2013): National Science Foundation CAREER award
2020–2025 Amir Nayyeri (Ph.D. 2012): National Science Foundation CAREER award

2
Jeff Erickson Curriculum Vitæ

2019–2020 Emily Kyle Fox (Ph.D. 2013): Best Teacher in Computer Science, Erik Jonsson School of
Engineering and Computer Science, University of Texas at Dallas
Fall 2019 Patrick Lin (Ph.D. 2021): Outstanding Teaching Assistant award (one of five), Department of
Computer Science, University of Illinois Urbana-Champaign
Fall 2019 Yipu Wang (Ph.D. 2020): Outstanding Teaching Assistant award (one of five), Department of
Computer Science, University of Illinois Urbana-Champaign
Fall 2019 David Bunde (Ph.D. 2006): William & Marilyn Ingersoll Chair in Computer Science, Knox
College
2018–2019 David Bunde (Ph.D. 2006): Faculty Exceptional Achievement Award, Knox College
Fall 2016 Patrick Lin (Ph.D. 2021): Outstanding Teaching Assistant award (one of five), Department of
Computer Science, University of Illinois Urbana-Champaign
June 2016 Hsien-Chih Chang (Ph.D. 2018): Best Student Presentation award, SoCG 2016
Spring 2016 Alexander Steiger (M.S. 2016): Outstanding Teaching Assistant award (one of five), Depart-
ment of Computer Science, University of Illinois Urbana-Champaign
Spring 2013 Emily Kyle Fox (Ph.D. 2013): C. W. Gear Outstanding Graduate Student award, Department
of Computer Science, University of Illinois Urbana-Champaign
2011–2016 Erin Wolf Chambers (Ph.D. 2008): National Science Foundation CAREER award
2009–2014 Alper Üngör (Ph.D. 2002): National Science Foundation CAREER award
Spring 2008 Tracy Russell (née Grauman, M.S. 2008): Outstanding Teaching Assistant award (inaugural
award, one of 16), Department of Computer Science, University of Illinois Urbana-Champaign
Spring 2003 Alper Üngör (Ph.D. 2002): David J. Kuck Outstanding Ph.D. Thesis Award, Department of
Computer Science, University of Illinois Urbana-Champaign

— Research —
Publications
Each paper is listed once, even if it has appeared in multiple versions. Almost all papers can be downloaded from
http://jeffe.cs.illinois.edu/pubs/. *Starred coauthors were students at the time of first submission. Unless indicated
otherwise, each paper lists all authors in alphabetical order, following standard practice in theoretical computer
science. See also my publication profiles at ACM Digital Library, AMiner, DBLP, Google Scholar, ORCID, Scopus, and
Web of Science.

Book

[1] Algorithms. First edition, xiv+454 pages, June 2019. An open-access textbook. 〈https://archive.org/
details/Algorithms-Jeff-Erickson/〉 or 〈http://jeffe.cs.illinois.edu/teaching/algorithms〉 or 〈http:
//algorithms.wtf〉. See related course materials [88].

Invited Refereed Papers

[2] New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry 16(4):389–418,
1996, special issue of invited papers from the 11th Annual Symposium on Computational Geometry.
Extended abstract in Proceedings of the 11th Annual Symposium on Computational Geometry, 127–137,
1995.
[3] Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise
interactions. With David Eppstein. Discrete & Computational Geometry 22(4):569–592, 1999, special
issue of invited papers from the 14th Annual Symposium on Computational Geometry. Extended
abstract in Proceedings of the 14th Annual Symposium on Computational Geometry, 58–67, 1998.

3
Jeff Erickson Curriculum Vitæ

[4] Efficient searching with linear constraints. With Pankaj K. Agarwal, Lars Arge, Paolo G. Franciosa,
and Jeffrey S. Vitter. Journal of Computer and System Sciences 61(2):192–216, 2000, special issue of
invited papers from the 17th Annual ACM Symposium on Principles of Database Systems. Extended
abstract in Proceedings of the 17th Annual ACM Symposium on Principles of Database Systems, 169–178,
1998.
[5] Reconfiguring convex polygons. With Oswin Aichholzer, Erik D. Demaine*, Ferran Hurtado, Mark
Overmars, Michael A. Soss*, and Godfried T. Toussaint. Computational Geometry: Theory and
Applications 20(1–2):85–95, 2001, special issue of invited papers from the 12th Canadian Conference
on Computational Geometry. Extended abstract in Proceedings of the 12th Canadian Conference on
Computational Geometry, 17–20, 2000.
[6] Flipping cubical meshes. With Marshall Bern and David Eppstein. Engineering with Computers
18(3):173–187, 2002, special issue of invited papers from the 10th International Meshing Roundtable.
Extended abstract (without my contributions) in Proceedings of the 10th International Meshing
Roundtable, 19–29, 2001.
[7] Indexing moving points. With Pankaj K. Agarwal and Lars Arge. Journal of Computer and System
Sciences 66:207–243, 2003, special issue of invited papers from the 19th ACM Symposium on Principles
of Database Systems. Extended abstract in Proceedings of the 19th ACM Symposium on Principles of
Database Systems, 175–186, 2000.
[8] Nice point sets can have nasty Delaunay triangulations. Discrete & Computational Geometry
30:109–132, 2003, special issue of invited papers from the 17th Annual Symposium on Computational
Geometry. Extended abstract in Proceedings of the 17th Annual Symposium on Computational
Geometry, 96–105, 2001.
[9] Optimally cutting a surface into a disk. With Sariel Har-Peled. Discrete & Computational Geometry
31(1):37–59, 2004, special issue of invited papers from the 18th Annual Symposium on Computational
Geometry. Extended abstract in Proceedings of the 18th Annual Symposium on Computational
Geometry, 244–253, 2002.
[10] Local polyhedra and geometric graphs. Computational Geometry: Theory and Applications 31(1–2):
101–125, 2005, special issue of invited papers from the 19th Annual Symposium on Computational
Geometry. Extended abstract in Proceedings of the 19th Annual Symposium on Computational
Geometry, 171–180, 2003.
[11] Separating point sets in polygonal environments. With Erik D. Demaine, Ferran Hurtado, John
Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides. International Journal
of Computational Geometry and Applications 15(4):403–419, 2005, special issue of invited papers from
the 20th Annual Symposium on Computational Geometry. Extended abstract in Proceedings of the
20th Annual Symposium on Computational Geometry, 10–16, 2004.
[12] An h-adaptive spacetime-discontinuous Galerkin method for linearized elastodynamics. With Reza
Abedi*, Robert B. Haber, and Shripad Thite*. Revue Européenne de Mécanique Numérique [European
Journal of Computational Mechanics] 15(6):619–642, 2006. Invited paper for special issue on adaptive
analysis.
[13] On the least median square problem. With Sariel Har-Peled and David Mount. Discrete &
Computational Geometry, 36(4):593–607, 2006, special issue of invited papers from the 20th Annual
Symposium on Computational Geometry. Extended abstract in Proceedings of the 20th Annual
Symposium on Computational Geometry, 273–279, 2004.
[14] Realizing partitions respecting full and partial order information. With Erik D. Demaine, Danny
Kriz̧anc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides. Journal of Discrete Algorithms
6:51–58, 2008, special issue of invited papers from the 16th Australasian Workshop on Combinatorial
Algorithms. Extended abstract in Proceedings of the 16th Australasian Workshop on Combinatorial
Algorithms, 105–114, 2005.

4
Jeff Erickson Curriculum Vitæ

[15] Splitting (complicated) surfaces is hard. With Erin W. Chambers*, Éric Colin de Verdière, Francis
Lazarus, and Kim Whittlesey. Computational Geometry: Theory and Applications 41(1–2):94–110,
2008, special issue of invited papers from the 22nd European Workshop on Computational Geometry.
Extended abstract in Proceedings of the 22nd Annual Symposium on Computational Geometry, 421–429,
2006.
[16] Homotopic Fréchet distance between curves, or walking your dog in the woods in polynomial time.
With Erin W. Chambers*, Éric Colin de Verdière, Sylvain Lazard, Francis Lazarus, and Shripad
Thite*. Computational Geometry: Theory and Applications 43(3):295–311, 2010, special issue of
invited papers from the 24th Annual Symposium on Computational Geometry. Extended abstract in
Proceedings of the 24th Annual Symposium on Computational Geometry, 101–109, 2008.
[17] Finding one tight cycle. With Sergio Cabello, Matt de Vos, and Bojan Mohar. ACM Transactions on
Algorithms 6(4):article 61, 2010, special issue of invited papers from the 19th Annual ACM-SIAM
Symposium on Discrete Algorithms. Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete
Algorithms, 527–531, 2008.
[18] Homology flows, cohomology cuts. With Erin W. Chambers* and Amir Nayyeri*. SIAM Journal
on Computing 41(6):1605–1634, 2012, special section of invited papers from the 41st Annual ACM
Symposium on Theory of Computing. Extended abstract in Proceedings of the 41st Annual ACM
Symposium on Theory of Computing, 273–282, 2009.
[19] Combinatorial optimization of cycles and bases. Advances in Applied and Computational Topology,
Afra Zomorodian, editor. Proceedings of Symposia in Applied Mathematics 70, American Mathematical
Society, 2012, pp. 195–228. Invited survey for an AMS Short Course at the 2011 Joint Mathematics
Meetings.
[20] Tracing compressed curves in triangulated surfaces. With Amir Nayyeri*. Discrete & Computational
Geometry 49(4):823–863, 2013, special issue of invited papers from the 28th Symposium on Com-
putational Geometry. Extended abstract in Proceedings of the 28th Symposium on Computational
Geometry, 131–140, 2012.
[21] Efficiently hex-meshing things with topology. Discrete & Computational Geometry 52(3):427–449,
2014, special issue of invited papers from the 29th Symposium on Computational Geometry. Extended
abstract in Proceedings of the 29th Annual Symposium on Computational Geometry, 37–46, 2013.
[22] Recognizing weakly simple polygons. with Hugo Akitaya*, Greg Aloupis, and Csaba Tóth. Discrete
& Computational Geometry 58(4):785–821, 2017, special issue of invited papers from the 32nd
International Symposium on Computational Geometry. arXiv:1603.07401. Extended abstract in
Proceedings of the 32nd International Symposium on Computational Geometry, 8:1–8:16, 2016.
[23] Untangling planar curves. With Hsien-Chih Chang*. Discrete & Computational Geometry 58(4):889–
920, 2017, special issue of invited papers from the 32nd International Symposium on Computational
Geometry. arXiv:1702.00146. Extended abstract in Proceedings of the 32nd International Symposium
on Computational Geometry, 29:1–29:16, 2016. Winner of the SoCG 2016 Best Student Presentation
Award.
[24] Topologically trivial closed walks in directed surface graphs. With Yipu Wang*. Discrete &
Computational Geometry 64(4):1253–1294, 2020, special issue of invited papers from the 35th
International Symposium on Computational Geometry. Proceedings of the 35th International
Symposium on Computational Geometry, 34:1–34:17, 2019. arXiv:1812.01564.
[25] A toroidal Maxwell–Cremona–Delaunay correspondence. With Patrick Lin*, Journal of Computational
Geometry 12(2):55–85, 2021, special issue of invited papers from the 36th International Symposium
on Computational Geometry. Proceedings of the 36th International Symposium on Computational
Geometry, 40:1–40:17, 2020. arXiv:2003.10057.
[26] Smoothing the gap between NP and ∃R. With Ivor van der Hoog* and Tillmann Miltzow. SIAM
Journal on Computing, special section of invited papers from the 61st Annual IEEE Symposium on
Foundations of Computer Science. Proceedings of the 61st Annual IEEE Symposium on Foundations of

5
Jeff Erickson Curriculum Vitæ

Computer Science, 1022–1033, 2020. arXiv:1912.02278. Preliminary extended abstract (with a different
title) in Abstracts of the 36th European Workshop on Computational Geometry, 62:1–62:7, 2020.
[27] Fusible numbers and Peano arithmetic. With Gabriel Nivasch and Junyan Xu. Logical Methods in
Computer Science 18(3:6), 2022, special issue of invited papers from the 36th Annual ACM/IEEE
Symposium on Logic in Computer Science. Proceedings of the 36th Annual ACM/IEEE Symposium on
Logic in Computer Science, 1–13, 2021. Distinguished paper. arXiv:2003.14342.
[28] Chasing puppies: Mobile beacon routing on closed curves. With Mikkel Abrahamsen, Irina
Kostitsyna, Maarten Löffler, Tillman Miltzow, Jérôme Urhausen*, Jordi Vermeulen*, and Giovanni
Viglietta. Journal of Computational Geometry 13(2):115–150, 2022, special issue of invited papers from
the 37th International Symposium on Computational Geometry. Proceedings of the 37th International
Symposium on Computational Geometry, 5:1–5:19, 2021. arXiv:2103.09811.
[29] Planar and toroidal morphing made easier. With Patrick Lin*. Journal of Graph Algorithms and
Applications 27(2):95–118, 2023, special issue of invited papers from the 29th International Symposium
on Graph Drawing and Network Visualization. Proceedings of the 29th International Symposium on
Graph Drawing and Network Visualization, 123–137; Lecture Notes in Computer Science 12868, Springer,
2021. arXiv:2106.14086.

Other Refereed Journal Papers

[30] Iterated nearest neighbors and finding minimal polytopes. With David Eppstein. Discrete &
Computational Geometry 11(4):321–350, 1994. Portions also appeared in Proceedings of the 4th Annual
ACM-SIAM Symposium on Discrete Algorithms, 64–73, 1993.
[31] Better lower bounds on detecting affine and spherical degeneracies. With Raimund Seidel. Discrete
& Computational Geometry 13(1):41–57, 1995. Erratum in Discrete & Computational Geometry
18(2):239–240, 1997. Extended abstract in Proceedings of the 34th Annual IEEE Symposium on
Foundations of Computer Science, 528–536, 1993.
[32] New lower bounds for convex hull problems in odd dimensions. SIAM Journal on Computing 28(4):
1198–1214, 1999. Extended abstract in Proceedings of the 12th Annual Symposium on Computational
Geometry, 1–9, 1996.
[33] Lower bounds for linear satisfiability problems. Chicago Journal of Theoretical Computer Science
1999(6), 1999. Extended abstract in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete
Algorithms, 388–395, 1995.
[34] Space-time tradeoffs for emptiness queries. SIAM Journal on Computing 29(6):1968–1996, 2000.
Extended abstract in Proceedings of the 13th Annual Symposium on Computational Geometry, 304–313,
1997. Includes results from [57].
[35] Flipturning polygons. With Oswin Aichholzer, Carmen Cortés*, Vida Dujmović*, Erik D. Demaine,
Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried T. Toussaint. Discrete
& Computational Geometry 28:231–253, 2002.
[36] Algorithmic issues in modeling motion. With Pankaj K. Agarwal, Leonidas J. Guibas, and 18 others.
ACM Computing Surveys 34(4):550–572, 2002.
[37] Preprocessing chains for dihedral rotations is hard or even impossible. With Michael A. Soss* and
Mark Overmars. Computational Geometry: Theory and Applications 26(3):235–246, 2003.
[38] Kinetic collision detection for two simple polygons. With Julien Basch, Leonidas J. Guibas, John
Hershberger, and Li Zhang*. Computational Geometry: Theory and Applications 27(3):211–235, 2004.
Extended abstract in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms,
102–111, 1999.
[39] Dense point sets have sparse Delaunay triangulations. Discrete & Computational Geometry 33:83–115,
2005. Extended abstract in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete
Algorithms, 125–134, 2002.

6
Jeff Erickson Curriculum Vitæ

[40] Output-sensitive algorithms for computing nearest-neighbor decision boundaries. With David
Bremner, Erik D. Demaine, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint.
Discrete & Computational Geometry 33(4):593–604, 2005. Extended abstract in Proceedings of the
8th International Workshop on Algorithms and Data Structures, 451–461. Lecture Notes in Computer
Science 2748, Springer-Verlag, 2003.
[41] Building space-time meshes over arbitrary spatial domains. With Damrong Guoy, John M. Sullivan,
and Alper Üngör*. Engineering with Computers 20(4):342–353, 2005. Extended abstract in Proceedings
of the 11th International Meshing Roundtable, 391–402, 2002.
[42] Capturing a convex object with three discs. With Jean Ponce, Fred Rothganger*, and Shripad Thite*.
IEEE Transactions on Robotics 23(6):1133–1140, 2007. Extended abstract in Proceedings of the 2003
IEEE International Conference on Robotics and Automation, 2242–2247, 2003.
[43] Centerpoint theorems for wedges. With Ferran Hurtado and Pat Morin. Discrete Mathematics and
Theoretical Computer Science 11(1):45–54, 2009.
[44] Vietoris-Rips complexes of planar point sets. With Erin W. Chambers*, Vin de Silva, and Robert
Ghrist. Discrete & Computational Geometry 44(1):75–90, 2010.
[45] Computing the shortest essential cycle. With Pratik Worah*. Discrete & Computational Geometry
44(4):912–930, 2010.
[46] Tightening non-simple paths and cycles on surfaces. With Éric Colin de Verdière. SIAM Journal on
Computing 39(8):3784–3813, 2010. Extended abstract in Proceedings of the 17th Annual ACM-SIAM
Symposium on Discrete Algorithms, 192–201, 2006.
[47] Multiple-source shortest paths in surface-embedded graphs. With Sergio Cabello and Erin W.
Chambers. SIAM Journal on Computing 42(4):1542–1571, 2013. Preliminary version (without my
contributions) in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 89–97,
2007.
[48] Necklaces, convolutions, and X + Y . With David Bremner, Timothy M. Chan, Erik D. Demaine, Ferran
Hurtado, John Iacono, Stefan Langerman, Mihai Pătraşcu, and Perouz Taslakian*. Algorithmica
69(2):294–314, 2014. Extended abstract (without Pătraşcu) in Proceedings of the 14th Annual European
Symposium on Algorithms, 160–171. Lecture Notes in Computer Science 4168, Springer-Verlag, 2006.
[49] Unfolding and dissection of multiple cubes. With Zachary Abel*, Brad Ballinger, Erik D. Demaine,
Martin L. Demaine, Adam Hesterberg*, Hiro Ito, Irina Kostitsyna, Jayson Lynch*, and Ryuhei
Uehara. Journal of Information Processing 25:610–615, 2017, special issue of discrete and computational
geometry, graphs, and games. Extended abstract in Abstracts of the 19th Japan Conference on Discrete
and Computational Geometry, Graphs, and Games, 42–43, 2016.
[50] Minimum cuts in surface graphs. With Erin W. Chambers, Emily Kyle Fox, and Amir Nayyeri. SIAM
Journal on Computing 52(1):156–195, 2023. Combined full version of [71], [74], and [77].

Refereed Book Chapters

[51] Sowing games. Games of No Chance, Richard J. Nowakowski, editor. Mathematical Sciences Research
Institute Publications 29, Cambridge University Press, 1996, pp. 287–297.
[52] New Toads and Frogs results. Games of No Chance, Richard J. Nowakowski, editor. Mathematical
Sciences Research Institute Publications 29, Cambridge University Press, 1996, pp. 299–310.
[53] Geometric range searching and its relatives. With Pankaj K. Agarwal. Advances in Discrete and
Computational Geometry, Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors.
Contemporary Mathematics 223, American Mathematical Society Press, 1999, pp. 1–56.
[54] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes. With Scott Kim.
Discrete Geometry: In Honor of W. Kuperberg’s 60th Birthday, Andras Bezdek, editor. Lecture Notes in
Pure and Applied Mathematics, Marcel Dekker, 2003, pp. 267–278.

7
Jeff Erickson Curriculum Vitæ

[55] Vertex-unfoldings of simplicial manifolds. With Erik D. Demaine, David Eppstein, George W. Hart,
and Joseph O’Rourke. Discrete Geometry: In Honor of W. Kuperberg’s 60th Birthday, Andras Bezdek,
editor. Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, 2003, pp. 215–228. Proceedings
of the 18th Annual Symposium on Computational Geometry, 237–243, 2002.

Conference Papers with no Journal Version

[56] On the relative complexities of some geometric problems. Proceedings of the 7th Canadian Conference
on Computational Geometry, 85–90, 1995. Full version available at 〈http://jeffe.cs.illinois.edu/pubs/
relative.html〉.
[57] New lower bounds for halfspace emptiness. Proceedings of the 37th Annual IEEE Symposium on
Foundations of Computer Science, 472–481, 1996. Merged into the journal version of [34].
[58] Kinetic binary space partitions for intersecting segments and disjoint triangles. With Pankaj K.
Agarwal and Leonidas J. Guibas. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete
Algorithms, 107–116, 1998.
[59] Separation-sensitive collision detection for convex objects. With Leonidas J. Guibas, Jorge Stolfi,
and Li Zhang*. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 327–336,
1999.
[60] Finite-resolution hidden surface removal. Proceedings of the 11th Annual ACM-SIAM Symposium on
Discrete Algorithms, 901-909, 2000.
[61] Flat-state connectivity of linkages under dihedral motions. With Greg Aloupis*, Erik D. Demaine,
Vida Dujmović, Stefan Langerman, Henk Meijer, Ileana Streinu, Joseph O’Rourke, Mark Overmars,
Michael Soss*, and Godfried Toussaint. Proceedings of the 13th Annual International Symposium on
Algorithms and Computation, 369–380. Lecture Notes in Computer Science 2518, Springer-Verlag, 2002.
[62] On the complexity of halfspace volume queries. With Erik D. Demaine and Stefan Langerman.
Proceedings of the 15th Canadian Conference on Computational Geometry, 159–160, 2003.
[63] Spacetime meshing with adaptive refinement and coarsening. With Reza Abedi*, Shuo-Heng
Chung*, Yong Fan*, Michael Garland, Damrong Guoy, Robert Haber, John Sullivan, Shripad Thite*,
and Yuan Zhou*. Proceedings of the 20th Annual Symposium on Computational Geometry, 300–309,
2004.
[64] Efficient tradeoff schemes in data structures for querying moving objects. With Pankaj K. Agarwal,
Lars Arge, and Hai Yu*. Proceedings of the 12th Annual European Symposium on Algorithms, 4–15.
Lecture Notes in Computer Science 3221, Springer-Verlag, 2004.
[65] Automatic blocking scheme for structured meshing in 2d multiphase flow simulation. With
Damrong Guoy. Proceedings of the 13th Annual International Meshing Roundtable, 121–132, 2004.
〈http://imr.sandia.gov/papers/abstracts/Gu318.html〉
[66] Greedy optimal homotopy and homology generators. With Kim Whittlesey. Proceedings of the 16th
Annual ACM-SIAM Symposium on Discrete Algorithms, 1038–1046, 2005.
[67] Lower bounds for external algebraic decision trees. Proceedings of the 16th Annual ACM-SIAM
Symposium on Discrete Algorithms, 755–761, 2005.
[68] Minimum-cost coverage of point sets by disks. With Helmut Alt, Esther M. Arkin, Hervé Brönnimann,
Sándor P. Fekete, Christian Knauer, Jonathan Lenchner*, Joseph S. B. Mitchell, and Kim Whittlesey.
Proceedings of the 22nd Annual Symposium on Computational Geometry, 449–458, 2006.
[69] Empty-ellipse graphs. With Olivier Devillers and Xavier Goaoc. Proceedings of the 19th Annual
ACM-SIAM Symposium on Discrete Algorithms, 1249–1257, 2008.
[70] Testing contractibility in planar Rips complexes. With Erin W. Chambers* and Pratik Worah*.
Proceedings of the 24th Annual Symposium on Computational Geometry, 251–259, 2008.

8
Jeff Erickson Curriculum Vitæ

[71] Minimum cuts and shortest homologous cycles. With Erin W. Chambers* and Amir Nayyeri*.
Proceedings of the 25th Annual Symposium on Computational Geometry, 377–385, 2009. Merged
into [71] for journal publication.
[72] Maximum flows and parametric shortest paths in planar graphs. Proceedings of the 21st Annual
ACM-SIAM Symposium on Discrete Algorithms, 794–804, 2010.
[73] Shortest non-crossing walks in the plane. With Amir Nayyeri*. Proceedings of the 22nd Annual
ACM-SIAM Symposium on Discrete Algorithms, 297–308, 2011.
[74] Minimum cuts and shortest non-separating cycles via homology covers. With Amir Nayyeri*.
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1166–1176, 2011. Merged
into [71] for journal publication.
[75] Computing replacement paths in surface embedded graphs. With Amir Nayyeri*. Proceedings of the
22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1347–1354, 2011.
[76] Shortest non-trivial cycles in directed surface graphs. Proceedings of the 27th Annual Symposium on
Computational Geometry, 236–243, 2011.
[77] Global minimum cuts in surface-embedded graphs. With Emily Kyle Fox* and Amir Nayyeri*.
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1309–1318, 2012. Merged
into [71] for journal publication.
[78] Transforming curves on surfaces redux. With Kim Whittlesey. Proceedings of the 24th Annual
ACM-SIAM Symposium on Discrete Algorithms, 1646–1655, 2013.
[79] A near-optimal approximation algorithm for asymmetric TSP on embedded graphs. With Anastasios
Sidiropoulos. Proceedings of the 30th Annual Symposium on Computational Geometry, 130–135, 2014.
[80] Detecting weakly simple polygons. With Hsien-Chih Chang* and Chao Xu*. Proceedings of
the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 1655–1670, 2015. Full version at
arXiv:1407.3340.
[81] Tightening curves on surfaces via local moves. With Hsien-Chih Chang*, David Letscher, Arnaud de
Mesmay, Saul Schleimer, Stephan Tillmann, Eric Sedgwick, and Dylan Thurston. Proceedings of the
29th Annual ACM-SIAM Symposium on Discrete Algorithms, 121–135, 2018.
[82] Holiest minimum-cost paths and flows in surface graphs. With Emily Kyle Fox and Luvsandondov
Lkhamsuren*. Proceedings of the 50th Annual ACM Symposium on Theory of Computing, 1319–1332,
2018. arXiv:1804.01045.
[83] Lower bounds for electrical reduction on surfaces. With Hsien-Chih Chang* and Marcos Cossarini.
Proceedings of the 35th International Symposium on Computational Geometry, 25:1–25:16, 2019.
arXiv:1707.04683.
[84] How to morph graphs on the torus. With Erin Chambers, Patrick Lin*, and Salman Parsa. Proceedings
of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2759–2778, 2021. arXiv:2007.07927.
[85] Auto-graded scaffolding exercises for theoretical computer science. With Jason Xia*, Eliot Wong
Robson*, Tue Do*, Aidan Glickman*, Zhuofan Jia*, Eric Jin*, Jiwon Lee*, Patrick Lin*, Steven
Pan*, Samuel Ruggerio*, Tomoko Sakurayama*, Andrew Yin*, Yael Gertner, and Brad Solomon.
2023 ASEE Annual Conference & Exposition, 2023. Describes [89].
[86] Reconstructing graphs from connected triples. With Paul Bastide*, Linda Cook, Carla Groenland,
Marc van Kreveld, Isja Mannens*, and Jordi Vermeulen*. Proceedings of the 49th International
Workshop on Graph-Theoretic Concepts in Computer Science, 16–29, 2023. Lecture Notes in Computer
Science 14093, Springer.
[87] FSM Builder: A tool for writing autograded finite automata questions. With Eliot W. Robson and
Samuel Ruggerio. To appear in Proceedings of the 29th Annual ACM Conference on Innovation and
Technology in Computer Science Education, 2024.

9
Jeff Erickson Curriculum Vitæ

Educational Materials
[88] Algorithms. Freely available textbook [1] (xiv+454 pages), related lecture notes (526 pages), and
homework/exam/discussion archive (890 pages) for my theoretical computer science classes at
Illinois, most recently revised June 2019. 〈http://jeffe.cs.illinois.edu/teaching/algorithms/〉 or
〈http://algorithms.wtf〉.
[89] “TheorieLearn”. With Eliot Wong Robson, Carl Evans, Yael Gertner, Brad Solomon, and 21
other developers. A large and growing collection of auto-graded exercises for CS 374 and
other theoretical computer science classes at Illinois, implemented on the PrairieLearn platform.
〈http://github.com/jeffgerickson/pl-uiuc-cs374〉. Described in [85].
Abstracts, Preprints, Presentations, Etc.
[90] Font family numbers. With Rilla Reynolds. Apple II GS Technical Note #41, May 1988. Revised by
Matt Deatherage and Keith Rollin, November 1990. 〈https://archive.org/details/IIgs_2523041_Font_
Family_Numbers〉
[91] DrawPicture data format. With Keith Rollin. Apple II GS Technical Note #46, November 1988.
〈https://archive.org/details/IIgs_2523046_DrawPicture_Format〉
[92] New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams.
With David Eppstein. Technical Report 92-55, Department of Information and Computer Science,
University of California, Irvine, June 1992.
[93] Lower Bounds for Fundamental Geometric Problems. Ph.D. dissertation, Computer Science Division,
University of California, Berkeley, July 1996.
[94] Plücker coordinates. Ray Tracing News 10(3), 1997. 〈http://www.realtimerendering.com/resources/
RTNews/html/rtnv10n3.html〉.
[95] Finding longest arithmetic progressions. Unpublished manuscript, 1999. 〈https://jeffe.cs.illinois.
edu/pubs/arith.html〉.
[96] Distance-2 edge coloring is NP-complete. With David P. Bunde* and Shripad Thite*. Unpublished
manuscript, 2005. arXiv:cs/0509100.
[97] Guest editor’s foreword. Discrete & Computational Geometry 42(1):1–2, 2009, special issue of invited
papers from the 23rd Annual Symposium on Computational Geometry.
[98] Special section on Foundations of Computer Science [Guest editors’ foreword]. With Scott Aaronson,
Mohammad Mahdian, R. Ravi, and Emanuele Viola. SIAM Journal on Computing 40(3):770, 2011,
special section of invited papers from the 49th IEEE Symposium on Foundations of Computer
Science (2008).
[99] Global minimum cuts in surface embedded graphs. With Erin W. Chambers, Emily Kyle Fox, and Amir
Nayyeri. Invited article in Encyclopedia of Algorithms, 2nd edition, Springer, 2016. arXiv:1910.04278.
Summarizes results from [71], [74], and [77].
[100] Electrical reduction, homotopy moves, and defect. With Hsien-Chih Chang*. Unpublished manu-
script, October 2015. arXiv:1510.00571. Superseded by [23] and [83].
[101] Unwinding annular curves and electrically reducing planar networks. With Hsien-Chih Chang*.
Abstracts of the Computational Geometry: Young Researchers Forum, 2017. Sketches results from [81]
and [83].
[102] Embedded-width: A variant of treewidth for plane graphs. With Glencora Borradaile, Hung Le*,
and Robbie Weber*. Preprint, March 2017. arXiv:1703.07532.
[103] Four vertex-disjoint paths in planar graphs. With Yipu Wang*. Preprint, April 2018.
[104] Optimal curve straightening is ∃R-complete. Preprint, August 2019. arXiv:1908.09400.
[105] Orthogonal schematization with minimum area homotopy. With Bram Custers*, Irina Kostitsyna,
Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek. Abstracts of the 36th European
Workshop on Computational Geometry, 64:1–64:7, 2020.

10
Jeff Erickson Curriculum Vitæ

Funding
Submitted Collaborative Research: CUE-T: Theory-ABCs: Transforming online theory instruction while
building ability, belonging, and confidence. Co-principal investigator. With Diana Franklin
(University of Chicago, PI), Yale Gertner, Geoffrey Herman (co-PI), and Seth Poulsen (Utah
State University, co-PI). [$1,366,000]
2024–2025 Automatic short answer grading at scale using large language models. Co-principal investi-
gator. With Mariana Silva (PI), Matthew West (co-PI), Yael Gertner (co-PI), Seth Poulsen
(Utah State University, co-PI), and Firas Moosvi (University of British Columbia, co-PI).
Strategic Instructional Innovations Program, Grainger College of Engineering, University of
Illinois Urbana-Champaign [$26,440]
2023–2025 TheorieLearn: Autograded resources for theoretical computer science. Principal investigator.
With Carl Evans, Yael Gertner, and Brad Solomon. Strategic Instructional Innovations Pro-
gram, Grainger College of Engineering, University of Illinois Urbana-Champaign [$116,000].
In-kind support provided by the Department of Computer Science [$44,000]
2022–2023 PrairieLearn for theoretical computer science (startup grant). Principal investigator. With
Carl Evans, Yael Gertner, Brad Solomon, and Tiffani Williams. Strategic Instructional Inno-
vations Program, Grainger College of Engineering, University of Illinois Urbana-Champaign.
[$10,000]
2017–2021 NSF SPX: Collaborative research: Asynchronous, parallel-adaptive solution of extreme
multiscale problems in seismology (SPX-1725544). Co-principal investigator. With Reza
Abedi (University of Tennessee, co-PI), Robert Haber (PI), Ahmed Elbanna (co-PI), and
Volodymyr V. Kindratenko (co-PI). [$800,000]
2014–2018 NSF AF: Medium: Collaborative research: Fast and accurate optimization in planar
graphs and beyond (CCF-1408763). Co-principal investigator. With Philip Klein (Brown
University, PI). [$1,200,000]
2013–2014 NSF: Student travel support for SoCG 2013 (CCF-1342819). Sole principal investigator.
[$20,000]
2009–2014 NSF AF: Small: Optimization in surface-embedded graphs (CCF-0915519). Sole principal
investigator. [$500,000]
2009–2012 NSF EAGER: Adaptive spacetime discontinuous Galerkin methods in 3D×time (OCI-0948393).
Co-principal investigator. With Robert Haber (PI). [$200,000]
2005–2008 NSF MSPA/MCS: Fundamental geodesic problems in computational topology (DMS-0528086).
Principal investigator. With Robert Ghrist (co-PI) and Steve LaValle (co-PI). [$500,000] One
of three grants chosen from over 100 proposals.
2002–2005 NSF ITR: Making 3D visibility practical (CCR-0219594). Co-principal investigator. With Frédo
Durand (MIT), John Hart (co-PI), and Steve LaValle (PI). [$500,000]
2001–2006 NSF ITR/AP: Multiscale models for microstructure simulation and process design (DMR-
0121695). With Jonathan A. Dantzig (co-PI), Michael Garland, Robert Haber (PI), Robert L.
Jerrard, Duane D. Johnson (co-PI), Laxmikant Kale, John Sullivan, and Daniel A. Tortorelli.
[$4,000,000]
2001–2006 NSF CAREER: Realistically efficient geometric algorithms (CCR-0093348). Sole principal
investigator. [$325,000]
1999–2002 Alfred P. Sloan Research Fellowship [$36,000]
1996–1998 NSF Mathematical Sciences Postdoctoral Research Fellowship (DMS-9627683). [$75,000]

11
Jeff Erickson Curriculum Vitæ

Plenary Lectures and Invited Tutorials

Dec 2022 The tragedy of being almost but not quite planar, 33rd International Symposium on Algorithms
and Computation (ISAAC 2022), Seoul, South Korea
Sep 2020 Fun with toroidal spring embeddings [25][84], 28th International Symposium on Graph
Drawing and Network Visualization (GD 2020), Vancouver, BC, Canada (online)
Aug 2020 Chasing puppies [28], Ferran Hurtado Memorial Lecture, 32nd Canadian Conference on
Computational Geometry (CCCG 2020), Saskatoon, SK, Canada (online)
Mar 2019 Variations on a theme of Steinitz [23][81][83][25]. 35th European Workshop on Computa-
tional Geometry (EuroCG 2019), Utrecht, Netherlands
Sep 2018 Minicourse on algorithms for planar graphs and surface graphs [9][47]. 20 Aniversario de la
Maestría en Computación, Centro de Investigacion en Matemáticas, Guanajuato, México
Jun 2018 One-dimensional computational topology [18][23][47][72][74][81]. Research School on
“Low-Dimensional Geometry and Topology: Discrete & Algorithmic Aspects”, Institut Henri
Poincaré, Paris, France
May 2016 Untangling planar curves and planar graphs [23]. Topology, Geometry, and Data Analysis at
OSU, The Ohio State University, Columbus, OH
Jul 2014 Computational topology of flows and cuts [18][71][74]. 9th International Colloquium on
Graph Theory and Combinatorics, Grenoble, France
Oct 2013 Cuts and flows in planar and surface graphs [18][71][72][74]. Dagstuhl Seminar on
Algorithms for Optimization Problems in Planar Graphs, Schloß Dagstuhl, Wadern, Germany
Jul 2013 Basic algorithms for surface-embedded graphs. ACAT summer school on computational
topology and topological data analysis, Ljubljana, Slovenia
Jun 2013 Theoretical advances in hexahedral mesh generation. Workshop on mesh generation, 29th
Annual Symposium on Computational Geometry, Rio de Janiero, Brazil
Jan 2011 Optimizing cycles and bases [19]. Short course on computational topology, AMS-MAA Joint
Mathematics Meeting, New Orleans, LA
Oct 2010 Computational complexity of games: How playing checkers (but not Jenga) can make you a
millionaire. 30th Annual Mathematics Symposium, Western Kentucky University, Bowling
Green, KY
Aug 2010 Computational topology: Shortest paths, flows, and cuts [18][47][74]. Workshop on Barriers
in Computational Complexity, Princeton Center for Computational Intractability, Princeton,
NJ
Aug 2007 Finding small holes: A brief foray into computational topology [8][44][47][70]. 10th
Workshop on Algorithms and Data Structures, Halifax, NS, Canada
Sep 2005 Computing (with) curves on surfaces [8][66]. 6th Max-Planck Advanced Course on the
Foundations of Computer Science, Saarbrücken, Germany
Aug 2005 Computing optimal graphs on surfaces [8][66]. 17th Canadian Conference on Computational
Geometry, Windsor, ON, Canada
Aug 2000 Kinetic data structures [38][58][59]. DIMACS Summer School on Foundations of Wireless
Networks and Applications, Piscataway, NJ

Other Invited Workshop Talks

Sep 2019 Chasing puppies [28], ICERM workshop on Illustrating Geometry and Topology, Brown
University, Providence, RI
May 2016 Untangling planar curves [23]. Topology, Geometry, and Data Analysis Conference at OSU,
Columbus, OH.

12
Jeff Erickson Curriculum Vitæ

Jun 2015 A brief (pre-)history of computational topology: Polygons and curves. 4th Annual Mini-
symposium on Computational Topology, workshop at the 31st International Symposium on
Computational Geometry, Eindhoven, Netherlands
May 2014 Hex meshing things with topology [21]. Applied Topology: Methods, Computation, and
Science (ATMCS), Vancouver, BC
Feb 2014 Hex meshing things with topology [21]. IMSE Hot TIME Symposium, University of Illinois at
Urbana-Champaign;
Aug 2013 Hex meshing things with topology [21]. Mathematical Congress of the Americas, Guanajuato,
Mexico
Jan 2013 Transforming curves on surfaces redux [78]. AMS-MAA Joint Mathematics Meeting, San
Diego, CA
Mar 2009 Homology flows, cohomology cuts [18]. Dagstuhl Seminar on Computational Geometry,
Schloß Dagstuhl, Wadern, Germany
Jul 2005 Local polyhedra and geometric graphs [10]. Carleton–Eindhoven Workshop on Computa-
tional Geometry, Gatineau Park, Québec, Canada
May 2003 Well-spaced samples of generic surfaces have sparse Delaunay triangulations. DIMACS
Workshop on Surface Reconstruction, Piscataway, NJ
Mar 2001 Nice point sets can have nasty Delaunay triangulations [8]. Dagstuhl Seminar on Computa-
tional Geometry, Schloß Dagstuhl, Wadern, Germany
Dec 1997 Raising roofs, crashing cycles, and playing pool [3]. 29th Computational Geometry Day,
Courant Institute of Mathematical Sciences
Mar 1997 Raising roofs, crashing cycles, and playing pool [3]. Dagstuhl Seminar on Computational
Geometry, Schloß Dagstuhl, Wadern, Germany

Invited Talks at Institutions

2023 ACM SIGMA, University of Illinois Urbana-Champaign
2019 Friday Colloquium, Berlin Mathematical School; Freie Universität Berlin; Universiteit Utrecht
(twice)
2018 Centro de Investigacion en Matemáticas, Guanajuato, México
2016 Duke University; St. Louis University
2015 Princeton University
2014 Oregon State University
2012 Brown University; École Normale Supérieure (twice); Institute of Science and Technology
Austria (twice)
2011 Århus Universitet/MADALGO; École Normale Supérieure; Institute of Science and Technology
Austria; Universität des Saarlandes
2010 The Ohio State University
2009 California Institute of Technology
2008 Mathematics Department Colloquium, University of Illinois at Urbana-Champaign; Toyota Techno-
logical Institute; University of California, Irvine
2005 Århus Universitet; AT&T Labs, Florin Park, NJ; Courant Institute of Mathematical Sciences;
École Normale Supérieure; Freie Universität Berlin (twice); Universitat Politècnica de Catalunya;
University of Waterloo; Univerza v Ljubljiana
2004 École Normale Supérieure; Freie Universität Berlin; LORIA/INRIA Lorraine; Polytechnic University;
Université Libre de Bruxelles

13
Jeff Erickson Curriculum Vitæ

2002 Duke University; Sandia National Laboratory; Stanford University

2001 Los Alamos National Laboratory; McGill University; The Ohio State University; University of
Waterloo
2000 Duke University; INRIA Sophia-Antipolis
1999 IBM Almaden Research Center
1998 Duke University (twice); The Johns Hopkins University; Massachusetts Institute of Technology;
Middlebury College; University of Illinois at Urbana-Champaign (twice)
1997 The Johns Hopkins University; University of Maryland, College Park
1996 Duke University; Xerox Palo Alto Research Center
1994 Freie Universität Berlin; Max-Planck-Institut für Informatik, Saarbrücken (twice); Universiteit
Utrecht
1993 NSF Regional Geometry Institute, Smith College

— Education —
Course Development
CS 374: Introduction to Algorithms and Models of Computation
A junior-level course in theoretical computer science. Developed and piloted with Lenny Pitt in
Spring 2014, and required for all computer science and computer engineering majors since Fall 2015.
Currently offered every semester, with aan average enrollment of 500–600 students per semester.
CS 473: Algorithms
An elective advanced algorithms course designed for advanced undergraduates and graduate
students in computer science and related fields. Developed and piloted in Spring 2015. Currently
offered every semester, with an average enrollment of 80–100 students per semester.
CS 498/598: Special Topics
Special-topics classes on various topics in theoretical computer science, including computational
geometry, lower bounds, online algorithms, algorithms for massive data, advanced data structures,
and computational topology. CS 498s are broader courses designed for undergraduates; CS 598s
are deeper research-level courses designed for graduate students.

Instruction
Numbers after each class show final (or estimated future) enrollment and student evaluations of instructor effec-
tiveness/course quality (maximum 5.0/5.0). ∗ Stars indicate inclusion in the university’s “List of Teachers Ranked as
Excellent by Their Students” based on these evaluations; ∗∗ double stars indicate evaluations recognized as outstanding.
◦
Circles indicate courses offered both on-campus and online through our online master’s program. This list spans
several major course and curriculum revisions, including a 2005 campus-wide renumbering of all courses.

Semester Class number and title Students ICES

Fall 2024 CS 473: Algorithms (200)
Co-teaching with Makrand Sinha
Spring 2024 CS 225: Data Structures, honors supplement 45 4.50/4.50
Fall 2023 CS 374: Algorithms and Models of Computation 385 4.16/3.95
Spring 2023 CS 598: Special Topics: One-Dimensional Computational Topology 20 4.73/4.55∗
Fall 2022 CS 473: Algorithms 110 4.81/4.76∗∗
Spring 2022 CS 498: Special Topics: Computational Geometry 20 4.88/4.38

14
Jeff Erickson Curriculum Vitæ

Fall 2021 CS 374: Algorithms and Models of Computation 385 4.43/4.33∗

Co-taught with Dakshita Khurana
Spring 2021 CS 498: Special Topics: Computational Geometry 20 4.91/4.82∗
Fall 2020 CS 598: Special Topics: One-Dimensional Computational Topology 20 5.00/5.00∗∗
Spring 2020 CS 473: Algorithms 135 4.82/4.75∗
Fall 2019 CS 374: Algorithms and Models of Computation 325 4.7/4.3∗

2018–2019 — On sabbatical —
Spring 2018 CS 374: Algorithms and Models of Computation 275 4.7/4.4∗
Fall 2017 CS 598: Special Topics: One-Dimensional Computational Topology 15 4.9/4.7∗
Spring 2017 CS 473: Algorithms 100 5.0/4.9∗∗
Fall 2016 CS 374: Algorithms and Models of Computation 405 4.4/3.9
Co-taught with Alexandra Kolla
Spring 2016 CS 473: Algorithms 105 4.9/4.7∗
Fall 2015 CS 598: Special Topics: Advanced Data Structures 30 4.73/4.73∗
Spring 2015 CS 473: Algorithms 50 4.96/4.92∗∗
Pilot for revised senior- and graduate-level elective course
Fall 2014 CS 374: Algorithms and Models of Computation 75 4.73/4.61∗
Spring 2014 CS 374: Algorithms and Models of Computation 40 4.72/4.27
Co-taught with Lenny Pitt, pilot for new junior-level course required for all
computer science and computer engineering majors
Fall 2013 CS 473: Undergraduate Algorithms 190 4.9/4.7∗
Spring 2013 CS 598: Special Topics: Computational Topology 10 (no evals)
Fall 2012 CS 473: Undergraduate Algorithms 175 4.8/4.4∗

2011–2012 — On sabbatical —
Spring 2011 CS 598: Special Topics: Advanced Data Structures 10 4.9/4.8∗
Fall 2010 CS 573: Graduate Algorithms 60 4.9/4.7∗
Spring 2010 CS 473: Undergraduate Algorithms 115 4.73/4.46∗
Fall 2009 CS 598: Special Topics: Computational Topology 10 4.56/4.44
Spring 2009 CS 473: Undergraduate Algorithms 80 4.76/4.15
Fall 2008 CS 573: Graduate Algorithms 40 4.65/4.33
Spring 2008 CS 598: Special Topics: Computational Geometry 15 4.6/4.5∗
Fall 2007 CS 173: Discrete Mathematical Structures 180 3.8/3.6
Co-taught with Cinda Heeren
Spring 2007 CS 473G: Graduate Algorithms 25 4.7/4.6∗
Fall 2006 CS 473U: Undergraduate Algorithms 100 4.8/4.4∗
Spring 2006 CS 573: Topics in Analysis of Algorithms: Advanced Data Structures 15 4.7/4.3
◦
Fall 2005 CS 473G: Graduate Algorithms 60 4.6/4.6∗

2004–2005 — On sabbatical —
Spring 2004 CS 373U: Undergraduate Algorithms 150 4.5/3.8
Fall 2003 CS 473: Topics in Analysis of Algorithms: Algorithms for Massive Data 20 (no evals)
Spring 2003 CS 497: Special Topics: Concrete Models of Computation 20 4.6/4.4

15
Jeff Erickson Curriculum Vitæ

Fall 2002 CS 373: Combinatorial Algorithms◦ 320 4.5/4.1

Spring 2002 CS 497: Special Topics: Computational Geometry 15 4.8/4.4
Fall 2001 CS 473: Topics in Analysis of Algorithms: Online Algorithms 15 5.0/4.8∗
Spring 2001 CS 373: Combinatorial Algorithms◦ 180 4.9/4.7∗∗
Fall 2000 CS 373: Combinatorial Algorithms 150 4.8/4.6∗
Spring 2000 CS 497: Special Topics: Computational Geometry 20 4.6/4.5
Fall 1999 CS 173: Discrete Mathematical Structures 200 4.4/4.1
Spring 1999 CS 373: Combinatorial Algorithms◦ 140 4.8/4.6∗
Fall 1998 CS 497: Special Topics: Geometric Data Structures 5 4.3/4.3

1998–2023 Average student evaluations (weighted by class size) 4845 4.63/4.37

Mentorship
Current students

• Christian Howard
• Hongxuan Chen, co-advised with Geoffrey Herman
• Katherine Braught
• Alex Jin (MS)

Former Ph.D. students and postdocs

• Patrick Lin, Ph.D. 2021. Equilibrium Graphs on the Flat Torus, or Finding Zen Amidst the Bull.
– Software engineer (since 2o21), Google, Mountain View, California
• Yipu Wang, Ph.D. 2020. Algorithms for Flows and Disjoint Paths in Planar Graphs.
– Postdoctoral researcher (since 2020), Sandia National Labs
• Hsien-Chih Chang, Ph.D. 2018. Tightening Curves and Graphs on Surfaces.
– Assistant professor (since 2020), Department of Computer Science, Dartmouth College
• Emily Kyle Fox, Ph.D. 2013. Fast Algorithms for Surface Embedded Graphs via Homology.
– Associate professor (since 2023), Department of Computer Science, University of Texas at Dallas
– Former Ph.D. students:
◦ Jiashuai Lu, Ph.D. 2022. Software engineer, Google, Mountain View, California
• Anastasios Sidiropoulos (Ph.D. 2008 MIT), postdoc 2012–2013, co-hosted with Sariel Har-Peled
– Associate professor (since 2019), Department of Computer Science, University of Illinois,
Chicago
• Amir Nayyeri, Ph.D. 2012. Combinatorial Optimization of Embedded Curves.
– Associate professor (since 2020), Department of Electrical Engineering and Computer Science,
Oregon State University, Corvallis
– Former Ph.D. students:
◦ Hanzhong Xu, Ph.D. 2020. Software Engineer at Google, Sunnyvale, California
◦ William Maxwell, Ph.D. 2021. Scientist at Naval Surface Warfare Center, Dahlgren, Virginia
• Erin Wolf Chambers, Ph.D. 2008. Finding Interesting Topological Features.
– Snyder Family Mission Collegiate Professor (starting 2023), Department of Computer Science
and Engineering. Notre Dame University.

16
Jeff Erickson Curriculum Vitæ

– Previously professor (2018–2023) and department chair (2021–2023), Department of Computer

Science, Saint Louis University, St. Louis, Missouri.
– Former Ph.D. students:
◦ Kyle Sykes, Ph.D. 2016. Senior Data Engineer, Avise Inc.
◦ Rehab Alharbi, Ph.D. 2021. Assistant professor at Jazan University, Saudi Arabia
◦ Kathleen Kramer, Ph.D. 2023.
• David Bunde, Ph.D. 2006. Scheduling and Admission Control.
– William & Marilyn Ingersoll Chair (since 2019) and former department chair, Department of
Computer Science, Knox College, Galesburg, Illinois
• Shripad Thite, Ph.D. 2005. Spacetime Meshing for Discontinuous Galerkin Methods.
– Software engineer, Facebook, San Francisco, California
• Alper Üngör, Ph.D. 2002, co-advised with Shang-Hua Teng. Parallel Delaunay Refinement and
Space-Time Meshing.
– Associate professor (since 2010), Department of Computer & Information Science & Engineering,
University of Florida, Gainesville
– Former Ph.D. students:
◦ Hale Erten, Ph.D. 2009. Software engineer at Intel, Portland, Oregon
◦ Homer “Scooter” Willis, Ph.D. 2010. Co-founder and chairman of the board, TechGarage,
Boca Raton, Florida.
◦ Paul Accisano, Ph.D. 2014. Software engineer at Microsoft, Redmond, Washington
◦ Anubhav Singh, Ph.D. 2014. Senior Software Engineer at Microsoft, Redmond, Washington
◦ Eyup Serdar Ayaz, Ph.D. 2018. Software Engineer at Philips, Gainesville, Florida

Former M.S. students

• Kieran Kaempen, M.S. 2022. The Art Gallery Problem in Polyomino Corridors. Software Engineer at
Coalition, Inc., San Francisco, California.
• Christian Howard, M.S. 2019. Spacetime Meshing of Stratified Spaces for Spacetime Discontinuous
Galerkin Methods in Arbitrary Spatial Dimensions. Ph.D. student at Illinois since August 2019.
• Alexander Steiger, M.S. 2017. Single-Face Non-Crossing Shortest Paths in Planar Graphs. Ph.D.
2023, Duke University, advised by Pankaj K. Agarwal. Assistant research professor (since 2023),
Department of Computer Science, Duke University.
• Alexander Mont, M.S. 2011. Adaptive Unstructured Spacetime Meshing for Four-Dimensional Spacetime
Discontinuous Galerkin Finite Element Methods. Senior software engineer, Common Networks, San
Francisco, CA.
• Emily Kyle Fox, M.S. 2010. Online Scheduling on Identical Machines using SRPT. See above.
• Aparna Sundar, M.S. 2009. More Homology Flows. Software engineer, Zenoss, Austin, Texas.
• Tracy Russell (née Grauman), M.S. 2008. Making Sense of Making Change. Staff software engineer,
Reforge, San Francisco, California.
• Pratik Worah, M.S. 2008 (Applied Mathematics). Finding Nontrivial Cycles in Topological Spaces. Ph.D.
2013, University of Chicago, advised by Janos Simon. Senior research scientist, Google Research,
New York.
• Kevin Milans, M.S. 2006. The Complexity of Graph Pebbling. Ph.D. 2010 in Mathematics, advised by
Doug West. Associate professor (since 2018) of mathematics, West Virginia University.
• Daniel Cranston, M.S. 2003. Coloring for Efficient Computation of Jacobians. Ph.D. 2007, advised by
Doug West. Associate professor (since 2015) of computer science, Virginia Commonwealth University.

17
Jeff Erickson Curriculum Vitæ

• Amit K. Patel, M.S. 2003. Line Transversals in R3 . Ph.D. 2010, Duke University, advised by Herbert
Edelsbrunner. Associate professor of mathematics (since 2022), Colorado State University.
• David Bunde, M.S. 2002. Approximating Total Flow Time. See above.
• Matthew Hayward, M.S. 2002. Lower Query Bounds in the Quantum Oracle Model. Technical program
manager, Google, San Francisco, California.

Former B.S. students (senior theses)

• Luvsandondov Lkhamsuren, B.S. 2016. Multiple-Source Shortest Paths in Unweighted Embedded

Graphs. Software engineer at AirBnB.
• Robert Weber, B.S. 2015. Embedded-width of Planar Graphs. Ph.D. 2020, University of Washington.
Assistant teaching professor of computer science (since 2020), University of Washington.
• Daniel Larkin-York (né Larkin), B.S. 2011. An Experimental Comparison of Heaps. Ph.D. 2015, Princeton
University. Staff Engineer at MongoDB, St. Petersburg, Florida.
• Luigi Marini, B.S. 2002. Edge-Coloring Graphs. Lead Research Software Engineer at National Center
for Supercomputing Applications, Urbana, Illinois.

Other undergraduate mentoring

• Independent study projects without thesis: Yiran Wang (BS 2009), JohnMark Lau (BS 2010), Will
Setchell (BS 2011), Sanchit Agarwal (BS 2016), Jingwen Jiang (BS 2016), Binghui Cheng (BS 2021),
Julie Lee (BS 2022), Steven Pan (BS 2022), Jason Xia (BS 2022), Aidan Glickman (BS 2023), Eli Kujawa
(BS expected 2026)
• TheorieLearn developers (see [85] and [89]): Julie Lee (BS 2022), Steven Pan (BS 2022), Tomoko
Sakurayama (BS 2022), Jason Xia (BS 2022), Anshul Bheemreddy (BS 2023), Ben Clarage (BS 2023),
Aidan Glickman (BS 2023), Zhuofan Jia (BS 2023), Eric Jin (BS 2023), Sam Ruggerio (BS 2023),
Andrew Yin (BS 2024), Tue Do (BS 2024), Alex Jin (BS 2024), Dhiraj Kuttichirayil (BS expected 2025),
George Huber (BS expected 2025), Nathan Omerza (BS expected 2025), Vedaant Jain (BS expected
2025), Yuqing Zhai (BS expected 2025), Eli Kujawa (BS expected 2026)

Other thesis committees (Ph.D. in Computer Science from Illinois unless otherwise indicated)

• Current: Mishal Assif P K (Electrical and Computer Engineering), Zander Kelley

• 2023: Robert Andrews, Rucha Kulkarni
• 2020: Ching-Hua Yu
• 2019: Kent Quanrud, Omer Gold (Tel Aviv University)
• 2018: Tim Ophelders (Technische Universiteit Eindhoven), Chao Xu
• 2015: Kaushik Kalyanaraman, Daniel Larkin-York (Princeton University), Yahav Nussbaum (Tel Aviv
University), Benjamin Raichel
• 2014: Hanna Erickson, Nirman Kumar, Arnaud de Mesmay (École Normale Supérieure), Steve Oudot
(Habilitation, Université Paris-Sud)
• 2012: Hayim Shaul (Tel Aviv University), Shay Mozes (Brown University), Sungjin Im
• 2011: Kostas Tsakalidis (Århus Universitet)
• 2010: Nitish Korula
• 2009: Bill Cochran, Evan VanderZee (Mathematics), Michael Wolf, Feida Zhu
• 2008: Hamidreza Chitsaz, Gio Kao, Stephen Kloder, Anna Yershova
• 2007: Ke Chen, Dan Cranston, Shen Dong, Xinlai Ni, Jason O’Kane
• 2006: Svetlana Lazebnik, Bardia Sadri
• 2005: Masud Hasan (University of Waterloo), Peng Cheng, Sung-Il Pae, Eric Shaffer
• 2004: Fred Rothganger, Xavier Goaoc (Université de Nancy 2)

18
Jeff Erickson Curriculum Vitæ

• 2002: Derek Armstrong (Industrial Engineering), Tanya Berger-Wolf, Ho-Lun (Alan) Cheng
• 2001: Damrong Guoy, Peter Leven (Electrical and Computer Engineering), Ali Pınar, Radhika
Ramamurthi (Mathematics), Afra Zomorodian
• 2000: Xiang-Yang Li
• 1999: André Kündgen (Mathematics)

— Service —
Department and University
Departmental service

• Associate department head 2013–2016

• Committee chairing
– Advisory: 2017–2018, 2022–2023 (elected by the committee)
– CS CARES: 2023–present
– Tenure-track faculty recruiting: 2013–2016
• Major committees
– Advisory: 2000–2003, 2012–2014, 2016–2018, 2022–2026 (elected by the faculty, 2-year terms)
– Broadening participation in computing: 2019–2020, 2021–2022
– Chairs and Professorships, 2021-present
– CS CARES: 2021–present
– Graduate admissions: 1999–2000, 2002–2004, 2012–2013
– Teaching faculty recruiting: 2015–2016, 2020–2022
– Promotions and tenure: 2010–2018, 2019–2024 (elected by the faculty since 2017)
– Tenure-track faculty recruiting: 2000–2004, 2005–2011, 2012–2017
– Undergraduate curriculum revision: 2011–2015
• Other departmental service
– Algorithms and theoretical computer science area chair, 2005–2011, 2016–2017

Other university service

• Senate of the Urbana-Champaign Campus, 2005–2007, 2009–2011 (elected by CS department faculty)

– General University Policy committee, 2009–2011
• College of Engineering service
– Department of Computer Science head search committee, 2007–2009
– Department of Computer Science head search committee, 2017–2018
– Promotions and tenure committee, 2022–2024
– Education Innovation Fellow, 2017–2018, 2019–2021
– Engineering-Mathematics liaison, 2007–2011, 2015–2018
– Equal Employment Opportunity Officer, 2015–2018

Professional
Professional society service

• ACM SIGACT Committee for the Advancement of Theoretical Computer Science, 2013–2015

19
Jeff Erickson Curriculum Vitæ

Editorial service

• Discrete & Computational Geometry, since 2007

• Journal of Applied and Computational Topology, 2016–2022
• CoRR/ArXiv moderator for Computational Geometry (cs.CG) and Discrete Mathematics (cs.DM),
2007–2019
• Guest editor, Discrete & Computational Geometry 42(1), 2009, special issue of invited papers from the
23rd Annual Symposium on Computational Geometry (2007) [97]
• Journal on Computational Geometry, 2009–2015 (founding editorial board)
• SIAM Journal on Computing, 2010–2012
• Guest editor (with Scott Aaronson, Mohammad Mahdian, R. Ravi, and Emanuele Viola), SIAM
Journal on Computing 40(3), 2011, special section of invited papers from the 49th IEEE Symposium
on Foundations of Computer Science (2008) [98].

Conference committee chairing (*Submissions not accepted from committee members)

• Workshop committee chair, 30th Annual Symposium on Computational Geometry (2014)

• Steering committee chair, Symposium on Computational Geometry, 2013–2016 (committee members
elected by the SoCG community, officers elected by the committee)
– Oversaw the 2014 community vote ending SoCG’s 30-year affiliation with ACM. For details, see
http://makingSoCG.wordpress.com.
– STOC/STOC 2016 colocation committee (ex officio)
• Program committee chair, 23rd Annual Symposium on Computational Geometry (2007)*
• Video Review committee chair, 15th Annual Symposium on Computational Geometry (1999)

Conference program and steering committees (*Submissions not accepted from committee members)

• 2025 Symposium on Simplicity in Algorithms

• 39th International Symposium on Computational Geometry (2023) — first year with double-blind
reviews, first year accepting submissions from committee members
• 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (2022) — first year with double-blind
reviews
• 2021 ASEE Illinois/Indiana Section Conference
• 2019 Symposium on Simplicity in Algorithms
• 34th International Symposium on Computational Geometry (2018)*
• 28th Annual ACM-SIAM Symposium on Discrete Algorithms (2017)*
• 8th International Conference on Fun with Algorithms (2016)
• Steering committee, Symposium on Computational Geometry, 2013–2016 (elected by the SoCG
community)
• 45th Annual ACM Symposium on Theory of Computing (2013)*
• 24th Canadian Conference on Computational Geometry (2012)*
• 3rd Symposium on Innovations in Theoretical Computer Science (2012)
• 21st Canadian Conference on Computational Geometry (2009)*
• 49th IEEE Symposium on Foundations of Computer Science (2008)*
• 13th ACM Symposium on Solid and Physical Modeling (2008)
• 19th Canadian Conference on Computational Geometry (2007)
• Steering committee, Symposium on Computational Geometry, 2006–2009 (elected by the SoCG
community)
• 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007)*

20
Jeff Erickson Curriculum Vitæ

• 47th IEEE Symposium on Foundations of Computer Science (2006)*

• 10th Scandinavian Workshop on Algorithm Theory (2006)*
• 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003)*
• Steering committee, Symposium on Computational Geometry, 2001–2003 (elected by the SoCG
community)
• 11th Annual International Symposium on Algorithms and Computation (2000)*
• 16th Annual Symposium on Computational Geometry, theory track (2000)*

Workshop organization and other committees

• Lead SafeTOC (anti-harassment) advocate for the ACM-SIAM Symposium on Discrete Algorithms,
since 2020
• SafeTOC advocate for the International Symposium on Computational Geometry, since 2020
• Organizing committee, Dagstuhl Seminar on Computational Geometry (2019)
• Organizing committee, 60th birthday workshop for Herbert Edelsbrunner, Raimund Seidel, and Emo
Welzl, 34th International Symposium on Computational Geometry (2018)
• Organizing committee, Dagstuhl Seminar on Computational Geometry (2017)
• Organizing committee, Dagstuhl Seminar on Optimization in Planar Graphs (2016)
• Organizing committee, Oberwolfach Seminar on Computational Geometric and Algebraic Topology
(2015)
• Organizing committee, Dagstuhl Seminar on Computational Geometry (2015)
• Program committee, 6th Workshop on Massive Data Algorithmics (2014)
• Workshop committee, 29th Annual Symposium on Computational Geometry (2013)
• Young Researchers Forum committee, 28th Annual Symposium on Computational Geometry (2012)
• Organizing committee, 15th Annual Fall Workshop on Computational Geometry and Visualization
(2005)
• Organizer, minisymposium on computational geometry, SIAM Conference on Discrete Mathematics
(2004)
• Organizing committee, 7th Annual Fall Workshop on Computational Geometry (1997)

Reviewing and refereeing

• Book reviewer for the American Mathematical Society and Princeton University Press
• Proposal panelist/reviewer for the National Science Foundation (CCF, DMS, CAREER, and GFRP),
the Army Research Office, the Department of Defense (EPSCoR), the European Research Council,
the Israeli Science Foundation, the Netherlands Organisation for Scientific Research (NWO), and
the U.S.–Israel Binational Science Foundation (BSF)
• Referee for ACM Journal of Experimental Algorithmics; ACM Transactions on Algorithms; ACM Transac-
tions on Database Systems; Algebraic and Geometric Topology; Algorithmica; Computational Geometry:
Theory and Applications; Computational Statistics and Data Analysis; Discrete & Computational
Geometry; Discrete Mathematics; Engineering with Computers; Graphical Models and Image Processing;
IEEE Transactions on Dependable and Secure Computing; IEEE Transactions on Pattern Recognition and
Machine Intelligence; IEEE Transactions on Robotics and Automation; Information Processing Letters;
International Journal of Computational Geometry and Applications; International Journal of Robotics
Research; Israeli Journal of Mathematics; Journal of Applied and Computational Topology; Journal of
the ACM; Journal on Computational Geometry; Journal of Computer and System Sciences; Proceedings
of Symposia in Applied Mathematics (AMS); SIAM Journal on Computing; and Software: Practice &
Experience

21
Jeff Erickson Curriculum Vitæ

• External reviewer for ACM-SIAM Symposium on Discrete Algorithms [SODA] (19 years between 1998
and 2023); ACM Symposium on Solid Modeling and Applications (1999); ACM Symposium on Theory
of Computing [STOC] (10 years between 1999 and 2019); Algorithms and Data Structures Symposium
[WADS] (2007 and 2011); Conference on Integer Programming and Combinatorial Optimization
[IPCO] (2020); Eurographics (2002); European Symposium on Algorithms [ESA] (8 years between
2002 and 2020); Fall Workshop on Computational Geometry (1996); IEEE Conference on Automation
Science and Engineering [CASE] (2008); IEEE Conference on Computational Complexity [CCC]
(2013); IEEE Symposium on Foundations of Computer Science [FOCS] (14 years between 1994 and
2020); International Colloquium on Automata, Languages, and Programming [ICALP] (2008 and
2010); International Meshing Roundtable [IMR] (5 years between 2000 and 2008); International
Symposium on Experimental Algorithms [SEA] (2009); International Symposium on Theoretical
Aspects of Computer Science [STACS] (2000 and 2013); Pacific Conference on Computer Graphics and
Applications [PG] (2009); Robotics: Science and Systems Conference [RSS] (2009); Scandinavian
Symposium and Workshops on Algorithm Theory [SWAT] (2014); SIAM Meeting on Algorithm
Engineering and Experimentation [ALENEX] (2008 and 2014); SIGGRAPH (8 years between 2001
and 2019); and Symposium on Computational Geometry [SoCG] (19 years between 1995 and 2021)

Last updated June 3, 2024. See http://jeffe.cs.illinois.edu/cv.pdf for the most recent version.
22