If you made any changes in Pure these will be visible here soon.
Filter
Conference contribution

Search results

  • 2021

    Chasing puppies: Mobile beacon routing on closed curves

    Abrahamsen, M., Erickson, J., Kostitsyna, I., Löffler, M., Miltzow, T., Urhausen, J., Vermeulen, J. & Viglietta, G., Jun 1 2021, 37th International Symposium on Computational Geometry, SoCG 2021. Buchin, K. & de Verdiere, E. C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 5. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 189).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • How to morph graphs on the torus

    Chambers, E. W., Erickson, J., Lin, P. & Parsa, S., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2759-2778 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Planar and Toroidal Morphs Made Easier

    Erickson, J. & Lin, P., 2021, Graph Drawing and Network Visualization - 29th International Symposium, GD 2021, Revised Selected Papers. Purchase, H. C. & Rutter, I. (eds.). Springer, p. 123-137 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12868 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2020

    A toroidal maxwell-cremona-delaunay correspondence

    Erickson, J. & Lin, P., Jun 1 2020, 36th International Symposium on Computational Geometry, SoCG 2020. Cabello, S. & Chen, D. Z. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, LIPIcs-SoCG-2020-40. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 164).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Smoothing the gap between np and er

    Erickson, J., Van Der Hoog, I. & Miltzow, T., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 1022-1033 12 p. 9317986. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2019

    Lower bounds for electrical reduction on surfaces

    Chang, H. C., Cossarini, M. & Erickson, J., Jun 1 2019, 35th International Symposium on Computational Geometry, SoCG 2019. Barequet, G. & Wang, Y. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 25. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 129).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Topologically trivial closed walks in directed surface graphs

    Erickson, J. & Wang, Y., Jun 1 2019, 35th International Symposium on Computational Geometry, SoCG 2019. Barequet, G. & Wang, Y. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 34. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 129).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2018

    Holiest minimum-Cost paths and flows in surface graphs

    Erickson, J., Fox, K. & Lkhamsuren, L., Jun 20 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Henzinger, M., Kempe, D. & Diakonikolas, I. (eds.). Association for Computing Machinery, p. 620-631 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Tightening curves on surfaces via local moves

    Chang, H. C., Erickson, J., Letscher, D., De Mesmay, A., Schleimer, S., Sedgwick, E., Thurston, D. & Tillmann, S., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 121-135 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2016

    Recognizing weakly simple polygons

    Akitaya, H. A., Aloupis, G., Erickson, J. & Tóth, C. D., Jun 1 2016, 32nd International Symposium on Computational Geometry, SoCG 2016. Fekete, S. & Lubiw, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 8.1-8.16 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 51).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Untangling planar curves

    Chang, H. C. & Erickson, J., Jun 1 2016, 32nd International Symposium on Computational Geometry, SoCG 2016. Fekete, S. & Lubiw, A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 29.1-29.16 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 51).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2015

    Detecting weakly simple polygons

    Chang, H. C., Erickson, J. & Xu, C., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 1655-1670 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2014

    A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

    Erickson, J. & Sidiropoulos, A., 2014, Proceedings of the 30th Annual Symposium on Computational Geometry, SoCG 2014. Association for Computing Machinery, p. 130-135 6 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2013

    Efficiently hex-meshing things with topology

    Erickson, J., 2013, Proceedings of the 29th Annual Symposium on Computational Geometry, SoCG 2013. Association for Computing Machinery, p. 37-45 9 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Transforming curves on surfaces redux

    Erickson, J. & Whittlesey, K., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. Association for Computing Machinery, p. 1646-1655 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2012

    Global minimum cuts in surface embedded graphs

    Erickson, J., Fox, K. & Nayyeri, A., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 1309-1318 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Tracing compressed curves in triangulated surfaces

    Erickson, J. & Nayyeri, A., 2012, Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012. p. 131-140 10 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2011

    Computing replacement paths in surface embedded graphs

    Erickson, J. & Nayyeri, A., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 1347-1354 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Minimum cuts and shortest non-separating cycles via homology covers

    Erickson, J. & Nayyeri, A., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 1166-1176 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Shortest non-crossing walks in the plane

    Erickson, J. & Nayyeri, A., 2011, Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, p. 297-308 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
  • Shortest non-trivial cycles in directed surface graphs

    Erickson, J., Jul 15 2011, Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11. p. 236-243 8 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2010

    Maximum flows and parametric shortest paths in planar graphs

    Erickson, J., 2010, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery (ACM), p. 794-804 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2009

    Homology flows, cohomology cuts

    Chambers, E. W., Erickson, J. & Nayyeri, A., 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 273-281 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Minimum cuts and shortest homologous cycles

    Chambers, E. W., Erickson, J. & Nayyeri, A., 2009, Proceedings of the 25th Annual Symposium on Computational Geometry, SCG'09. p. 377-385 9 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2008

    Empty-Ellipse Graphs

    Devillers, O., Erickson, J. & Goaoc, X., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1249-1257 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Finding one tight cycle *

    Cabello, S., DeVos, M., Erickson, J. & Mohar, B., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 527-531 5 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Testing contractibility in planar rips complexes

    Chambers, E. W., Erickson, J. & Worah, P., 2008, Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. p. 251-259 9 p. (Proceedings of the Annual Symposium on Computational Geometry).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2007

    Finding small holes a brief foray into computational topology

    Erickson, J., 2007, Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer, 1 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4619 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2006

    Minimum-cost coverage of point sets by disks

    Alt, H., Erickson, J., Lenchner, J., Arkin, E. M., Fekete, S. P., Mitchell, J. S. B., Brönnimann, H., Knauer, C. & Whittlesey, K., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery (ACM), p. 449-458 10 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Necklaces, convolutions, and X + Y

    Bremner, D., Chan, T. M., Demaine, E. D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S. & Taslakian, P., 2006, Algorithms, ESA 2006 - 14th Annual European Symposium, Proceedings. Springer, p. 160-171 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4168 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Splitting (complicated) surfaces is hard

    Chambers, E. W., De Verdière, É. C., Erickson, J., Lazarus, F. & Whittlesey, K., 2006, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06. Association for Computing Machinery, p. 421-429 9 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 2002

    Dense point sets have sparse delaunay triangulations or "... but not too nasty"

    Erickson, J., 2002, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002. Association for Computing Machinery, p. 125-134 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 06-08-January-2002).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Flat-state connectivity of linkages under dihedral motions

    Aloupis, G., Demaine, E. D., Dujmović, V., Erickson, J., Langerman, S., Meijer, H., O'Rourke, J., Overmars, M., Soss, M., Streinu, I. & Toussaint, G. T., 2002, Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings. p. 369-380 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2518 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 1995

    Lower bounds for linear satisfiability problems

    Erickson, J., Jan 22 1995, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, p. 388-395 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • New lower bounds for Hopcroft's problem

    Erickson, J., Sep 1 1995, Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995. Association for Computing Machinery, p. 127-137 11 p. (Proceedings of the Annual Symposium on Computational Geometry; vol. Part F129372).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 1993

    Better lower bounds on detecting affine and spherical degeneracies

    Erickson, J. G. & Seidel, R., 1993, Annual Symposium on Foundatons of Computer Science (Proceedings). Anon (ed.). Publ by IEEE, p. 528-536 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution