% Papers written by Erik D. Demaine % % URL is simply "http://theory.lcs.mit.edu/~edemaine/papers/" followed by the % entry name. This directory is created automatically from this file. % The "talks" directory used to have this property too. % Missing: % - TU Berlin talk during Sandor's class @Article{Clobber_TCS, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer}, TITLE = {Solitaire Clobber}, JOURNAL = {Theoretical Computer Science}, YEAR = {to appear}, NOTE = {Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory.}, PAPERS = {Clobber_CGames2002; Clobber_TR2002}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Getting Clobbered,'' Science News 161(17), April 27, 2002.} } @Article{UniversallyEasy_TCS, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {On Universally Easy Classes for NP-complete Problems}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://www.elsevier.nl/locate/tcs}, YEAR = {to appear}, PAPERS = {SODA2001c} } @Article{PushingBlocks_CGTA, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Michael Hoffmann and Joseph O'Rourke}, TITLE = {Pushing Blocks is Hard}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.nl/locate/comgeo}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.}, WEBPAGES = {pushingblocks}, PAPERS = {PushXCCCG2001}, LENGTH = {19 pages} } @Article{InterlockedLinkages_CGTA, AUTHOR = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke and Jack Snoeyink}, TITLE = {Interlocked Open and Closed Linkages with Few Joints}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.nl/locate/comgeo}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.}, PAPERS = {InterlockedLinkages_CCCG2001; InterlockedLinkages_SoCG2002}, LENGTH = {10 pages} } @Article{GeneExpression_Bioinformatics, AUTHOR = {Ziv Bar-Joseph and Erik D. Demaine and David K. Gifford and Ang\`ele M. Hamel and Tommi S. Jaakkola and Nathan Srebro}, TITLE = {{$K$}-ary Clustering with Optimal Leaf Ordering for Gene Expression Data}, JOURNAL = {Bioinformatics}, JOURNALURL = {http://bioinformatics.oupjournals.org/}, YEAR = {to appear}, NOTE = {Special issue on Microarray Analysis.}, PAPERS = {GeneExpression_WABI2002; GeneExpression_UWTR2001} } @InProceedings{SquareCutting_JCDCG2002, AUTHOR = {Prosenjit Bose and Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Quartering a Square Optimally}, BOOKTITLE = {Proceedings of the Japan Conference on Discrete and Computational Geometry}, BOOKURL = {http://www.ried.u-tokai.ac.jp/JCDCG/}, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Tokyo, Japan}, MONTH = {December 6-9}, YEAR = 2002, PAGES = {to appear} } @InProceedings{TriangulationGames_JCDCG2002, AUTHOR = {Oswin Aichholzer and David Bremner and Erik D. Demaine and Ferran Hurtado and Evangelos Kranakis and Hannes Krasser and Suneeta Ramaswami and Saurabh Sethia and Jorge Urrutia}, TITLE = {Playing with Triangulations}, BOOKTITLE = {Proceedings of the Japan Conference on Discrete and Computational Geometry}, BOOKURL = {http://www.ried.u-tokai.ac.jp/JCDCG/}, ADDRESS = {Tokyo, Japan}, MONTH = {December 6-9}, YEAR = 2002, PAGES = {to appear} } @InProceedings{Flat2Flat_ISAAC2002, AUTHOR = {Greg Aloupis and Erik D. Demaine and Vida Dujmovi\'c and Jeff Erickson and Stefan Langerman and Henk Meijer and Joseph O'Rourke and Mark Overmars and Michael Soss and Ileana Streinu and Godfried Toussaint}, TITLE = {Flat-State Connectivity of Linkages under Dihedral Motions}, BOOKTITLE = {Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002)}, bookurl = {http://www.scs.carleton.ca/isaac2002/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {November 20--23}, YEAR = 2002, PAGES = {to appear}, LENGTH = {12 pages}, PAPERS = {Flat2Flat_CCCG2002} } @InProceedings{CliqueSum_ISAAC2002, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Exponential Speedup of Fixed-Parameter Algorithms on $K_{3,3}$-minor-free or $K_5$-minor-free Graphs}, BOOKTITLE = {Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002)}, bookurl = {http://www.scs.carleton.ca/isaac2002/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {November 20--23}, YEAR = 2002, PAGES = {to appear}, LENGTH = {12 pages}, PAPERS = {CliqueSum_TR2002; CliqueSum_APPROX2002} } @InProceedings{ForceLinkage_CGW2002, AUTHOR = {Jason Cantarella and Erik D. Demaine and Hayley Iben and James O'Brien}, TITLE = {An Energy-Driven Approach to Linkage Unfolding}, BOOKTITLE = {Proceedings of the 12th Annual Fall Workshop on Computational Geometry}, BOOKURL = {http://dimacs.rutgers.edu/Workshops/CompGeom/}, ADDRESS = {Piscataway, New Jersey}, MONTH = {November 14--15}, YEAR = 2002, PAPERTYPE = {abstract}, LENGTH = {2 pages} } @InProceedings{Tetris_CGW2002, AUTHOR = {Erik D. Demaine and Susan Hohenberger and David Liben-Nowell}, TITLE = {Tetris is Hard, Even to Approximate}, BOOKTITLE = {Proceedings of the 12th Annual Fall Workshop on Computational Geometry}, BOOKURL = {http://dimacs.rutgers.edu/Workshops/CompGeom/}, ADDRESS = {Piscataway, New Jersey}, MONTH = {November 14--15}, YEAR = 2002, PAPERTYPE = {abstract}, LENGTH = {2 pages}, PAPERS = {Tetris_TR2002}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Tetris Is Hard,'' Science News 162(17), October 26, 2002.

Helen Pearson also wrote an article describing these results, ``Maths proves Tetris is tough,'' Nature Science Update, October 28, 2002.

Sarah Graham also wrote a short article describing these results, ``Mathematicians Prove Tetris is Tough,'' Scientific American News, October 29, 2002.} } @Misc{TreeLayout_Manuscript2002, AUTHOR = {Stephen Alstrup and Michael A. Bender and Erik D. Demaine and Martin Farach-Colton and J. Ian Munro and Theis Rauhe and Mikkel Thorup}, TITLE = {Efficient Tree Layout in a Multilevel Memory Hierarchy}, HOWPUBLISHED = {Manuscript}, MONTH = {November 11}, YEAR = 2002, LENGTH = {14 pages}, PAPERS = {TreeLayout_ESA2002}, COMMENTS = {This paper is also available as arXiv:cs.DS/0211010 of the Computing Research Repository (CoRR).

This paper replaces and rectifies the ESA version.} } @TechReport{Tetris_TR2002, AUTHOR = {Erik D. Demaine and Susan Hohenberger and David Liben-Nowell}, TITLE = {Tetris is Hard, Even to Approximate}, INSTITUTION = {Massachusetts Institute of Technology}, NUMBER = {MIT-LCS-TR-865}, numberurl = {http://www.lcs.mit.edu/publications/specpub.php?id=1611}, MONTH = {October 21}, YEAR = 2002, LENGTH = {55 pages}, PAPERS = {Tetris_CGW2002}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Tetris Is Hard,'' Science News 162(17), October 26, 2002.

Helen Pearson also wrote an article describing these results, ``Maths proves Tetris is tough,'' Nature Science Update, October 28, 2002.

Sarah Graham also wrote a short article describing these results, ``Mathematicians Prove Tetris is Tough,'' Scientific American News, October 29, 2002.} } @InCollection{VertexUnfolding_Kuperberg2002, AUTHOR = {Erik D. Demaine and David Eppstein and Jeff Erickson and George W. Hart and Joseph O'Rourke}, TITLE = {Vertex-Unfolding of Simplicial Manifolds}, BOOKTITLE = {Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday}, PUBLISHER = {Marcer Dekker Inc.}, YEAR = 2002, PAGES = {to appear}, PAPERS = {VertexUnfolding_SoCG2002; VertexUnfolding2}, LENGTH = {15 pages} } @InProceedings{NetworkStats_ESA2002, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Frequency Estimation of Internet Packet Streams with Limited Space}, BOOKTITLE = {Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002)}, BOOKURL = {http://www.dis.uniroma1.it/~algo02/esa02/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2461, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {348--360}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {NetworkStats_TR2002}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610348.pdf.} } @InProceedings{DietzSleator_ESA2002, AUTHOR = {Michael A. Bender and Richard Cole and Erik D. Demaine and Martin Farach-Colton and Jack Zito}, TITLE = {Two Simplified Algorithms for Maintaining Order in a List}, BOOKTITLE = {Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002)}, bookurl = {http://www.dis.uniroma1.it/~algo02/esa02/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2461, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {152--164}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610152.pdf.} } @InProceedings{Traversals_ESA2002, AUTHOR = {Michael A. Bender and Richard Cole and Erik D. Demaine and Martin Farach-Colton}, TITLE = {Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy}, BOOKTITLE = {Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002)}, bookurl = {http://www.dis.uniroma1.it/~algo02/esa02/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2461, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {139--151}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610139.pdf.} } @InProceedings{TreeLayout_ESA2002, AUTHOR = {Michael A. Bender and Erik D. Demaine and Martin Farach-Colton}, TITLE = {Efficient Tree Layout in a Multilevel Memory Hierarchy}, BOOKTITLE = {Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002)}, bookurl = {http://www.dis.uniroma1.it/~algo02/esa02/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2461, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {165--173}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {8 pages}, PAPERS = {TreeLayout_Manuscript2002}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610165.pdf.}, UPDATES = {We have discovered some of the claims in this paper to be incorrect. Please refer to the revision where these mistakes are described and corrected.} } @InProceedings{CliqueSum_APPROX2002, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor}, BOOKTITLE = {Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2002)}, bookurl = {http://www.dis.uniroma1.it/~algo02/approx02/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2462, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {67--80}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {14 pages}, PAPERS = {CliqueSum_ISAAC2002} } @InProceedings{GeneExpression_WABI2002, AUTHOR = {Ziv Bar-Joseph and Erik D. Demaine and David K. Gifford and Ang\`ele M. Hamel and Tommi S. Jaakkola and Nathan Srebro}, TITLE = {{$K$}-ary Clustering with Optimal Leaf Ordering for Gene Expression Data}, BOOKTITLE = {Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI 2002)}, bookurl = {http://www.dis.uniroma1.it/~algo02/wabi02/}, ADDRESS = {Rome, Italy}, MONTH = {September 17--21}, YEAR = 2002, PAGES = {to appear}, LENGTH = {15 pages}, PAPERS = {GeneExpression_Bioinformatics; GeneExpression_UWTR2001} } @Article{ObliviousRouting_IJCGA2002, AUTHOR = {Prosenjit Bose and Andrej Brodnik and Svante Carlsson and Erik D. Demaine and Rudolf Fleischer and Alejandro L\'opez-Ortiz and Pat Morin and J. Ian Munro}, TITLE = {Online Routing in Convex Subdivisions}, JOURNAL = {International Journal of Computational Geometry and Applications}, JOURNALURL = {http://ejournals.wspc.com.sg/ijcga/ijcga.html}, VOLUME = 12, NUMBER = 4, PAGES = {283--295}, MONTH = {August}, YEAR = 2002, NOTE = {Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation, 2000.}, LENGTH = {14 pages}, PAPERS = {ISAAC2000} } % xxx add number, numberurl, and day of month @TechReport{NetworkStats_TR2002, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Frequency Estimation of Internet Packet Streams with Limited Space}, INSTITUTION = {Massachusetts Institute of Technology}, MONTH = {August}, YEAR = 2002, LENGTH = {14 pages}, PAPERS = {NetworkStats_ESA2002} } @InProceedings{CCCG2001Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2001}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, LENGTH = {4 pages}, PAPERS = {CCCG2000Open; CCCG99Open}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.} } @InProceedings{NonOrthogonal_CCCG2002, AUTHOR = {Therese Biedl and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and Paul Nijjar and Ryuhei Uehara and Ming-wei Wang}, TITLE = {Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, PAGES = {105--108}, LENGTH = {4 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/C95.ps.} } @InProceedings{Push2F_CCCG2002, AUTHOR = {Erik D. Demaine and Robert A. Hearn and Michael Hoffmann}, TITLE = {Push-2F is PSPACE-Complete}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, PAGES = {31--35}, LENGTH = {5 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/31.ps.} } @InProceedings{PermutingPolygons_CCCG2002, AUTHOR = {Greg Aloupis and Prosenjit Bose and Erik D. Demaine and Stefan Langerman and Henk Meijer and Mark Overmars and Godfried T. Toussaint}, TITLE = {Computing Signed Permutations of Polygons}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, LENGTH = {14 pages}, COMMENTS = {A short version of the paper appeared on pages 68--71.

Both the short and long versions are available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/23l.ps (long version) and http://www.cs.uleth.ca/~wismath/cccg/papers/23m.ps (short version).} } @InProceedings{PointSearching_CCCG2002, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Proximate Point Searching}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, PAGES = {1--4}, LENGTH = {4 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/22.ps.} } @InProceedings{Flat2Flat_CCCG2002, AUTHOR = {Greg Aloupis and Erik D. Demaine and Henk Meijer and Joseph O'Rourke and Ileana Streinu and Godfried Toussaint}, TITLE = {Flat-State Connectivity of Chains with Fixed Acute Angles}, BOOKTITLE = {Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)}, bookurl = {http://www.cs.uleth.ca/cccg}, ADDRESS = {Lethbridge, Alberta, Canada}, MONTH = {August 12--14}, YEAR = 2002, PAGES = {27--30}, LENGTH = {4 pages}, PAPERS = {Flat2Flat_ISAAC2002}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/16.ps.} } @InCollection{InfinitesimallyLocked_LasVegas, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Infinitesimally Locked Self-Touching Linkages with Applications to Locked Trees}, BOOKTITLE = {Physical Knots: Knotting, Linking, and Folding of Geometric Objects in 3-space}, EDITOR = {Jorge Calvo and Kenneth Millett and Eric Rawdon}, PUBLISHER = {American Mathematical Society}, YEAR = {to appear}, NOTE = {Collection of papers from the Special Session on Physical Knotting and Unknotting at the AMS Spring Western Section Meeting, Las Vegas, Nevada, April 21--22, 2001}, LENGTH = {25 pages}, WEBPAGES = {linkage}, COPYRIGHT = {The paper is \copyright American Mathematical Society.} } @Article{HingedAlphabet, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Hinged Dissection of the Alphabet}, JOURNAL = {Journal of Recreational Mathematics}, YEAR = {to appear}, PAPERS = {HingedPolyforms}, LENGTH = {4 pages} } @PlenaryTalk{DCCG2002, AUTHOR = {Erik D. Demaine}, TITLE = {To Be Announced}, CONFERENCE = {Conference on Discrete, Combinatorical and Computational Geometry}, CONFERENCEURL = {http://www.icm2002.org.cn/satellite/satel_7.htm}, ADDRESS = {Beijing, China}, MONTH = {August 13--19}, YEAR = 2002, LENGTH = {45 minutes} } @InProceedings{Clobber_CGames2002, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer}, TITLE = {Solitaire Clobber}, BOOKTITLE = {Proceedings of the 3rd International Conference on Computers and Games}, BOOKURL = {http://www.cs.ualberta.ca/~cg2002/}, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Edmonton, Alberta, Canada}, MONTH = {July 25-27}, YEAR = 2002, PAGES = {to appear}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {13 pages}, PAPERS = {Clobber_TCS; Clobber_TR2002}, COMMENTS = {This paper is also available as arXiv:cs.DM/0204017 of the Computing Research Repository (CoRR).}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Getting Clobbered,'' Science News 161(17), April 27, 2002.} } @TechReport{Clobber_TR2002, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer}, TITLE = {Solitaire Clobber}, NUMBER = {HKUST-TCSC-2002-05}, NUMBERURL = {http://www.cs.ust.hk/tcsc/RR/2002-05.ps.gz}, INSTITUTION = {Hong Kong University of Science and Technology}, MONTH = {April}, YEAR = 2002, LENGTH = {14 pages}, PAPERS = {Clobber_TCS; Clobber_CGames2002}, COMMENTS = {This paper is also available as arXiv:cs.DM/0204017 of the Computing Research Repository (CoRR).}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Getting Clobbered,'' Science News 161(17), April 27, 2002.} } @InProceedings{NCL_ICALP2002, AUTHOR = {Robert A. Hearn and Erik D. Demaine}, TITLE = {The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications}, BOOKTITLE = {Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002)}, BOOKURL = {http://www.lcc.uma.es/icalp2002}, ADDRESS = {Malaga, Spain}, MONTH = {July 8--13}, YEAR = 2002, PAGES = {401--413}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2380, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {NCL_Manuscript}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2380/23800401.pdf.}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Logic in the Blocks,'' Science News 162(7):106-108, August 17, 2002.} } @InProceedings{BlindRobots_SWAT2002, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Robot Localization without Depth Perception}, BOOKTITLE = {Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002)}, BOOKURL = {http://www.cs.utu.fi/swat2002/}, ADDRESS = {Turku, Finland}, MONTH = {July 3--5}, YEAR = 2002, PAGES = {249--259}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2368, LENGTH = {10 pages}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2368/23680249.pdf.} } @InvitedTalk{G4G5, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Cutting Paper}, CONFERENCE = {Gathering for Gardner V}, CONFERENCEURL = {http://www.g4g4.com/}, ADDRESS = {Atlanta, Georgia}, MONTH = {April 5--7}, YEAR = 2002 } @InvitedTalk{Tufts2002, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding in Computational Geometry}, SERIES = {EECS Colloquium}, INSTITUTION = {Tufts University}, ADDRESS = {Medford, Massachusetts}, MONTH = {April 24}, YEAR = 2002, LENGTH = {1 hour} } @InvitedTalk{GeorgiaTech2002, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding in Computational Geometry}, INSTITUTION = {College of Computing, Georgia Institute of Technology}, ADDRESS = {Atlanta, Georgia}, MONTH = {April 8}, YEAR = 2002, LENGTH = {1 hour} } @TechReport{CliqueSum_TR2002, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Exponential Speedup of Fixed Parameter Algorithms on $K_{3,3}$-minor-free or $K_5$-minor-free Graphs}, INSTITUTION = {Massachusetts Institute of Technology}, NUMBER = {MIT-LCS-TR-838}, numberurl = {http://www.lcs.mit.edu/publications/specpub.php?id=1611}, MONTH = {March 18}, YEAR = 2002, LENGTH = {22 pages}, PAPERS = {CliqueSum_ISAAC2002; CliqueSum_APPROX2002} } @InvitedTalk{DagstuhlFeb2002, AUTHOR = {Erik D. Demaine}, TITLE = {Cache-Oblivious Traversal of a Dynamic List}, SERIES = {Seminar on Data Structures}, SERIESURL = {http://www.dagstuhl.de/02091}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {February 24--March 3}, YEAR = 2002, LENGTH = {30 minutes} } @InvitedTalk{DagstuhlGames2002, AUTHOR = {Erik D. Demaine}, TITLE = {PushPush is PSPACE-complete}, SERIES = {Seminar on Algorithmic Combinatorial Game Theory}, SERIESURL = {http://www.dagstuhl.de/02081}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {February 17--22}, YEAR = 2002, LENGTH = {15 minutes} } @InvitedTalk{AAAS2002b, AUTHOR = {Erik D. Demaine}, TITLE = {Locked and Unlocked Polygonal Chains}, SERIES = {Robot Arm Manipulation: Geometric Challenges}, CONFERENCE = {Annual Meeting of the American Association for Advancement of Science (AAAS 2002)}, CONFERENCEURL = {http://www.aaas.org/meetings/}, ADDRESS = {Boston, Massachussetts}, MONTH = {February 14--19}, YEAR = 2002, LENGTH = {30 minutes} } @InvitedTalk{AAAS2002a, AUTHOR = {Erik D. Demaine}, TITLE = {Recent Results in Computational Origami}, SERIES = {Mathematics and Science of Origami: Visualize the Possibilities}, CONFERENCE = {Annual Meeting of the American Association for Advancement of Science (AAAS 2002)}, CONFERENCEURL = {http://www.aaas.org/meetings/}, ADDRESS = {Boston, Massachussetts}, MONTH = {February 14--19}, YEAR = 2002, LENGTH = {30 minutes} } @Article{TextSearchLB_JAlgorithms2002, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz}, TITLE = {A Linear Lower Bound on Index Size for Text Retrieval}, JOURNAL = {Journal of Algorithms}, JOURNALURL = {http://www.academicpress.com/www/journal/al.htm}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.}, PAPERS = {SODA2001b}, LENGTH = {14 pages} } @Article{RedBlue_CGTA2002, AUTHOR = {Oswin Aichholzer and David Bremner and Erik D. Demaine and Henk Meijer and Vera Sacrist\'an and Michael Soss}, TITLE = {Long Proteins with Unique Optimal Foldings in the {H-P} Model}, JOURNAL = {Computational Geometry: Theory and Applications}, JOURNALURL = {http://www.elsevier.nl/locate/comgeo}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 17th European Workshop on Computational Geometry, 2001}, LENGTH = {27 pages}, PAPERS = {EuroCG2001}, COMMENTS = {This paper is also available as arXiv:cs.CG/0201018 of the Computing Research Repository (CoRR).} } @InProceedings{InterlockedLinkages_SoCG2002, AUTHOR = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke and Jack Snoeyink}, TITLE = {Interlocked Open Linkages with Few Joints}, BOOKTITLE = {Proceedings of the 18th Annual ACM Symposium on Computational Geometry (SoCG 2002)}, BOOKURL = {http://www-ma2.upc.es/~geomc/events/socg2002/socg2002.html}, ADDRESS = {Barcelona, Spain}, MONTH = {June 5--7}, YEAR = 2002, PAGES = {189--198}, PAPERS = {InterlockedLinkages_CGTA; InterlockedLinkages_CCCG2001}, LENGTH = {10 pages} } @InProceedings{VertexUnfolding_SoCG2002, AUTHOR = {Erik D. Demaine and David Eppstein and Jeff Erickson and George W. Hart and Joseph O'Rourke}, TITLE = {Vertex-Unfolding of Simplicial Manifolds}, BOOKTITLE = {Proceedings of the 18th Annual ACM Symposium on Computational Geometry (SoCG 2002)}, BOOKURL = {http://www-ma2.upc.es/~geomc/events/socg2002/socg2002.html}, ADDRESS = {Barcelona, Spain}, MONTH = {June 5--7}, YEAR = 2002, PAGES = {237--243}, PAPERS = {VertexUnfolding_Kuperberg2002; VertexUnfolding2}, LENGTH = {7 pages} } @InProceedings{BufferTrees_STOC2002, AUTHOR = {Lars Arge and Michael A. Bender and Erik D. Demaine and Bryan Holland-Minkley and J. Ian Munro}, TITLE = {Cache-Oblivious Priority Queue and Graph Algorithm Applications}, BOOKTITLE = {Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002)}, BOOKURL = {http://omega.crm.umontreal.ca/STOC'02/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {May 19--21}, YEAR = 2002, PAGES = {268--276}, LENGTH = {9 pages} } @Misc{NCL_Manuscript, AUTHOR = {Robert A. Hearn and Erik D. Demaine}, TITLE = {The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications}, HOWPUBLISHED = {Manuscript}, MONTH = {May}, YEAR = 2002, LENGTH = {20 pages}, PAPERS = {NCL_ICALP2002}, WEBPAGES = {games}, COMMENTS = {This paper is also available as arXiv:cs.CC/0205005 of the Computing Research Repository (CoRR).}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Logic in the Blocks,'' Science News 162(7):106-108, August 17, 2002.} } @Article{Aleks_GC2002, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw and Joseph O'Rourke}, TITLE = {Enumerating Foldings and Unfoldings between Polygons and Polytopes}, JOURNAL = {Graphs and Combinatorics}, JOURNALURL = {http://link.springer.de/link/service/journals/00373/}, VOLUME = 18, NUMBER = 1, YEAR = 2002, PAGES = {93--104}, LENGTH = {12 pages}, WEBPAGES = {aleksandrov}, PAPERS = {JCDCG2000c; AleksTR}, COMMENTS = {This paper is also available from the publisher's website.

A preliminary version of this paper is also available as arXiv:cs.CG/0107024 of the Computing Research Repository (CoRR).} } @Article{Linkage, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Straightening Polygonal Arcs and Convexifying Polygonal Cycles}, JOURNAL = {Discrete \& Computational Geometry}, JOURNALURL = {http://link.springer.de/link/service/journals/00454/}, YEAR = {to appear}, LENGTH = {36 pages}, PAPERS = {LinkageTR; FOCS2000a; EuroCG2000}, WEBPAGES = {linkage}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Unlocking Puzzling Polygons,'' Science News 158(13):200-201, September 23, 2000.

Joseph O'Rourke also wrote an article describing these results, ``Computational Geometry Column 39,'' International Journal of Computational Geometry and Applications, 10(4):441-444, 2000.} } @TechReport{LinkageTR, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Straightening Polygonal Arcs and Convexifying Polygonal Cycles}, SERIES = {Fachbereich Mathematik und Informatik, Serie B - Informatik}, INSTITUTION = {Freie Universit\"at Berlin}, NUMBER = {B 02-02}, MONTH = {February}, YEAR = 2002, LENGTH = {49 pages}, PAPERS = {Linkage; FOCS2000a; EuroCG2000}, WEBPAGES = {linkage}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Unlocking Puzzling Polygons,'' Science News 158(13):200-201, September 23, 2000.

Joseph O'Rourke also wrote an article describing these results, ``Computational Geometry Column 39,'' International Journal of Computational Geometry and Applications, 10(4):441-444, 2000.} } @TechReport{PCR_TR2001, AUTHOR = {Therese Biedl and Bro\v{n}a Brejov\'a and Erik D. Demaine and Ang\`ele M. Hamel and Alejandro L\'opez-Ortiz and Tom\'a\v{s} Vina\v{r}}, TITLE = {Finding Hidden Independent Sets in Interval Graphs}, INSTITUTION = {Department of Computer Science, University of Waterloo}, NUMBER = {2001-26}, MONTH = {December}, YEAR = 2001, LENGTH = {21 pages} } @InvitedTalk{UToronto2001, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding in Computational Geometry}, INSTITUTION = {Department of Computer Science, University of Toronto}, ADDRESS = {Toronto, Ontario, Canada}, MONTH = {December 11}, YEAR = 2001, LENGTH = {1 hour} } @InvitedTalk{CMSToronto2001, AUTHOR = {Erik D. Demaine}, TITLE = {History of Geometric Constructions by Paper Folding}, SERIES = {Special Session on History of Mathematics}, CONFERENCE = {Canadian Mathematical Society Winter Meeting}, ADDRESS = {Toronto, Ontario, Canada}, MONTH = {December 8--10}, YEAR = 2001 } @InvitedTalk{Harvard2001, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding in Computational Geometry}, SERIES = {DEAS Computer Science Colloquium Series}, INSTITUTION = {Harvard University}, INSTITUTIONURL = {http://www.harvard.edu/}, ADDRESS = {Cambridge, Massachusetts}, MONTH = {December 13}, YEAR = 2001, LENGTH = {1 hour} } @InvitedTalk{MITAppliedMath2001, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding in Computational Geometry}, SERIES = {Applied Mathematics Colloquium}, SERIESURL = {http://www-math.mit.edu/amc/}, INSTITUTION = {Massachussets Institute of Technology}, INSTITUTIONURL = {http://www.mit.edu/}, ADDRESS = {Cambridge, Massachusetts}, MONTH = {October 1}, YEAR = 2001, LENGTH = {1 hour} } @InvitedTalk{MITCombinatorics2001, AUTHOR = {Erik D. Demaine}, TITLE = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, SERIES = {Combinatorics Seminar}, SERIESURL = {http://www-math.mit.edu/~combin/}, INSTITUTION = {Massachussets Institute of Technology}, INSTITUTIONURL = {http://www.mit.edu/}, ADDRESS = {Cambridge, Massachusetts}, MONTH = {October 12}, YEAR = 2001, LENGTH = {1 hour} } @Article{3DChains_DCG2001, AUTHOR = {T. Biedl and E. Demaine and M. Demaine and S. Lazard and A. Lubiw and J. O'Rourke and M. Overmars and S. Robbins and I. Streinu and G. Toussaint and S. Whitesides}, TITLE = {Locked and Unlocked Polygonal Chains in Three Dimensions}, JOURNAL = {Discrete \& Computational Geometry}, JOURNALURL = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 26, NUMBER = 3, PAGES = {269--281}, MONTH = {October}, YEAR = 2001, LENGTH = {29 pages}, PAPERS = {3DChainsTR; SODA99c}, COMMENTS = {This paper is also available from the publisher's website.} } @InProceedings{MatchingBoundsISAAC2001, AUTHOR = {Therese Biedl and Erik D. Demaine and Christian A. Duncan and Rudolf Fleischer and Stephen G. Kobourov}, TITLE = {Tight Bounds on Maximal and Maximum Matchings}, BOOKTITLE = {Proceedings of the 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001)}, BOOKURL = {http://www.cosc.canterbury.ac.nz/isaac01/}, ADDRESS = {Christchurch, New Zealand}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2223, MONTH = {December 19--21}, YEAR = 2001, PAGES = {308--319}, LENGTH = {12 pages}, PAPERS = {MatchingJAlgorithms}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2223/22230308.pdf.} } @PhDThesis{dthesis, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding}, SCHOOL = {Department of Computer Science, University of Waterloo}, SCHOOLURL = {http://www.cs.uwaterloo.ca/}, YEAR = 2001, LENGTH = {97 pages}, WEBPAGES = {folding} } @InProceedings{InfinitesimallyLockedCGW2001, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Infinitesimally Locked Linkages with Applications to Locked Trees}, BOOKTITLE = {Proceedings of the 11th Annual Fall Workshop on Computational Geometry}, BOOKURL = {http://geometry.poly.edu/cgw-2001.html}, ADDRESS = {New York, New York}, MONTH = {November 2--3}, YEAR = 2001, PAPERTYPE = {abstract}, LENGTH = {2 pages} } @TechReport{VertexUnfolding2, AUTHOR = {Erik D. Demaine and David Eppstein and Jeff Erickson and George W. Hart and Joseph O'Rourke}, TITLE = {Vertex-Unfoldings of Simplicial Manifolds}, NUMBER = {072}, INSTITUTION = {Smith College}, MONTH = {October}, YEAR = 2001, LENGTH = {12 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/0110054 of the Computing Research Repository (CoRR).}, PAPERS = {VertexUnfolding_SoCG2002; VertexUnfolding} } @PlenaryTalk{MFCS2001, AUTHOR = {Erik D. Demaine}, TITLE = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, CONFERENCE = {26th Symposium on Mathematical Foundations in Computer Science (MFCS 2001)}, CONFERENCEURL = {http://www.math.cas.cz/~mfcs2001/}, ADDRESS = {Marianske Lazne, Czech Republic}, MONTH = {August 27--31}, YEAR = 2001, LENGTH = {50 minutes}, PAPERS = {AlgGameTheoryMFCS}, WEBPAGES = {games} } @InProceedings{AlgGameTheoryMFCS2001, AUTHOR = {Erik D. Demaine}, TITLE = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, BOOKTITLE = {Proceedings of the 26th Symposium on Mathematical Foundations in Computer Science (MFCS 2001)}, BOOKURL = {http://www.math.cas.cz/~mfcs2001/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {2136}, EDITOR = {Ji\v{r}\'{\i} Sgall and Ale\v{s} Pultr and Petr Kolman}, ADDRESS = {Marianske Lazne, Czech Republic}, MONTH = {August 27--31}, YEAR = 2001, PAGES = {18--32}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {15 pages}, PAPERS = {AlgGameTheoryDraft}, WEBPAGES = {games}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2136/21360018.pdf.} } @InProceedings{MapFoldingWADS2001, AUTHOR = {Esther M. Arkin and Michael A. Bender and Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell and Saurabh Sethia and Steven S. Skiena}, TITLE = {When Can You Fold a Map?}, BOOKTITLE = {Proceedings of the 7th Workshop on Algorithms and Data Structures (WADS 2001)}, BOOKURL = {http://www.wads.org/}, EDITOR = {Frank Dehne and J\"org-R\"udiger Sack and Roberto Tamassia}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2125, ADDRESS = {Providence, Rhode Island}, MONTH = {August 8--10}, YEAR = 2001, PAGES = {401--413}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {MapFolding; CGW2000}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2125/21250401.pdf.}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Proof clarifies a map-folding problem,'' Science News 158(26-27):406, December 23-30, 2002.

Helen Pearson also wrote an article describing these results, ``Origami solves road map riddle,'' Nature Science Update, February 18, 2002.} } @InProceedings{CCCG2000Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2000}, BOOKTITLE = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001)}, BOOKURL = {http://compgeo.math.uwaterloo.ca/~cccg01}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 13--15}, YEAR = 2001, PAGES = {185--187}, LENGTH = {3 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/short/eddemaine-18187.ps.gz.}, PAPERS = {CCCG2001Open; CCCG99Open} } @InProceedings{PushXCCCG2001, AUTHOR = {Erik D. Demaine and Michael Hoffmann}, TITLE = {Pushing Blocks is {NP}-Complete for Noncrossing Solution Paths}, BOOKTITLE = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001)}, BOOKURL = {http://compgeo.math.uwaterloo.ca/~cccg01}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 13--15}, YEAR = 2001, PAGES = {65--68}, WEBPAGES = {pushingblocks}, LENGTH = {5 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/long/eddemaine-24711.ps.} } @InProceedings{PaperReachabilityCCCG2001, AUTHOR = {Erik D. Demaine and Joseph S. B. Mitchell}, TITLE = {Reaching Folded States of a Rectangular Piece of Paper}, BOOKTITLE = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001)}, BOOKURL = {http://compgeo.math.uwaterloo.ca/~cccg01}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 13--15}, YEAR = 2001, PAGES = {73--75}, WEBPAGES = {folding}, LENGTH = {3 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/short/eddemaine-33029.ps.

Photos of Victoria Hart folding a crane by our algorithm } } @InProceedings{InterlockedLinkages_CCCG2001, AUTHOR = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke}, TITLE = {Short Interlocked Linkages}, BOOKTITLE = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001)}, BOOKURL = {http://compgeo.math.uwaterloo.ca/~cccg01}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 13--15}, YEAR = 2001, PAGES = {69--72}, WEBPAGES = {linkage}, LENGTH = {4 pages}, PAPERS = {InterlockedLinkages_CGTA; InterlockedLinkages_SoCG2002}, COMMENTS = {This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/short/eddemaine-27484.ps.} } @InProceedings{CCCG2001Logo, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw}, TITLE = {The CCCG 2001 Logo}, BOOKTITLE = {Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001)}, BOOKURL = {http://compgeo.math.uwaterloo.ca/~cccg01}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 13--15}, YEAR = 2001, PAGES = {iv--v}, WEBPAGES = {foldcut}, PAPERS = {SODA99a; JCDCG98}, LENGTH = {2 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://compgeo.math.uwaterloo.ca/~cccg01/proceedings/short/eddemaine-67778.ps.} } @TechReport{VertexUnfolding, AUTHOR = {Erik D. Demaine and David Eppstein and Jeff Erickson and George W. Hart and Joseph O'Rourke}, TITLE = {Vertex-Unfoldings of Simplicial Polyhedra}, NUMBER = {071}, INSTITUTION = {Smith College}, MONTH = {July}, YEAR = 2001, LENGTH = {10 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/0107023 of the Computing Research Repository (CoRR).}, PAPERS = {VertexUnfolding2} } @PlenaryTalk{UWMathGradConf2001, AUTHOR = {Erik D. Demaine}, TITLE = {Playing Games with Algorithms}, CONFERENCE = {University of Waterloo Faculty of Mathematics Graduate Student Conference}, CONFERENCEURL = {http://www.math.uwaterloo.ca/Mathgrad_Office/gradconf/}, MONTH = {June 26--27}, YEAR = {2001} } @Misc{AlgGameTheoryDraft, AUTHOR = {Erik D. Demaine}, TITLE = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, HOWPUBLISHED = {Manuscript}, MONTH = {June}, YEAR = 2001, LENGTH = {25 pages}, PAPERS = {AlgGameTheoryMFCS}, WEBPAGES = {games}, COMMENTS = {This paper is also available as arXiv:cs.CC/0106009 of the Computing Research Repository (CoRR).} } @Misc{CacheObliviousBTrees, AUTHOR = {Michael A. Bender and Erik D. Demaine and Martin Farach-Colton}, TITLE = {Cache-Oblivious B-Trees}, HOWPUBLISHED = {Manuscript}, MONTH = {May}, YEAR = 2001, LENGTH = {26 pages}, PAPERS = {FOCS2000b} } @Article{BalancedColoringDM, AUTHOR = {Therese C. Biedl and Eowyn \v{C}enek and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer and Ming-Wei Wang}, TITLE = {Balanced $k$-Colorings}, JOURNAL = {Discrete Mathematics}, JOURNALURL = {http://www.elsevier.com/locate/disc}, VOLUME = {254}, PAGES = {19--32}, YEAR = {2002}, COPYRIGHT = {The paper is \copyright Elsevier Science B.V.}, LENGTH = {13 pages}, PAPERS = {MFCS2000; BalancedColoringTR} } @Article{LockedTreeDAM, AUTHOR = {Therese Biedl and Erik Demaine and Martin Demaine and Sylvain Lazard and Anna Lubiw and Joseph O'Rourke and Steve Robbins and Ileana Streinu and Godfried Toussaint and Sue Whitesides}, TITLE = {A Note on Reconfiguring Tree Linkages: Trees can Lock}, JOURNAL = {Discrete Applied Mathematics}, JOURNALURL = {http://www.elsevier.com/locate/dam}, VOLUME = 117, NUMBER = {1--3}, YEAR = 2002, PAGES = {293--297}, PAPERS = {LockedTreeTR; CCCG98c}, LENGTH = {5 pages}, WEBPAGES = {linkage} } @Article{CircularSawCGTA, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Craig S. Kaplan}, TITLE = {Polygons Cuttable by a Circular Saw}, JOURNAL = {Computational Geometry: Theory and Applications}, JOURNALURL = {http://www.elsevier.nl/locate/comgeo}, VOLUME = 20, NUMBER = {1--2}, MONTH = {October}, YEAR = 2001, PAGES = {69--84}, NOTE = {Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.}, COPYRIGHT = {The paper is \copyright Elsevier Science B.V.}, LENGTH = {14 pages}, PAPERS = {CCCG2000a}, COMMENTS = {This paper is also available from the publisher's website.} } @Article{ConvexPolygonsCGTA, AUTHOR = {Oswin Aichholzer and Erik D. Demaine and Jeff Erickson and Ferran Hurtado and Mark Overmars and Michael A. Soss and Godfried T. Toussaint}, TITLE = {Reconfiguring Convex Polygons}, JOURNAL = {Computational Geometry: Theory and Applications}, JOURNALURL = {http://www.elsevier.nl/locate/comgeo}, VOLUME = 20, NUMBER = {1--2}, MONTH = {October}, YEAR = 2001, PAGES = {85--95}, NOTE = {Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.}, COPYRIGHT = {The paper is \copyright Elsevier Science B.V.}, LENGTH = {13 pages}, PAPERS = {CCCG2000c}, WEBPAGES = {linkage}, COMMENTS = {This paper is also available from the publisher's website.} } @InProceedings{FUN2001, AUTHOR = {Therese Biedl and Timothy Chan and Erik D. Demaine and Rudolf Fleischer and Mordecai Golin and J. Ian Munro}, TITLE = {Fun-Sort}, BOOKTITLE = {Proceedings of the 2nd International Conference on Fun with Algorithms (FUN 2001)}, BOOKURL = {http://www.di.unipi.it/fun01/}, EDITOR = {Elena Lodi and Linda Pagli and Nicola Santoro}, ADDRESS = {Isola d'Elba, Italy}, MONTH = {May 29--31}, YEAR = 2001, PAGES = {15--26}, LENGTH = {12 pages}, PAPERS = {FunSort_TR2001} } @TechReport{FunSort_TR2001, AUTHOR = {Therese Biedl and Timothy Chan and Erik D. Demaine and Rudolf Fleischer and Mordecai Golin and J. Ian Munro}, TITLE = {Fun-Sort}, NUMBER = {HKUST-TCSC-2001-03}, NUMBERURL = {http://www.cs.ust.hk/tcsc/RR/2001-03.ps.gz}, INSTITUTION = {Hong Kong University of Science and Technology}, MONTH = {February}, YEAR = 2001, LENGTH = {12 pages}, PAPERS = {FUN2001} } @InvitedTalk{AMSVegas2001, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Infinitesimally Locked Linkages with Applications to Locked Trees}, SERIES = {Special Session on Physical Knotting and Unknotting}, SERIESURL = {http://www.ams.org/amsmtgs/2071_program_Unsched.html#2071:AMSSSD1}, CONFERENCE = {AMS Spring Western Section Meeting}, CONFERENCEURL = {http://www.ams.org/amsmtgs/2071_program.html}, ADDRESS = {Las Vegas, Nevada}, MONTH = {April 21--22}, YEAR = {2001}, LENGTH = {20 minutes}, WEBPAGES = {linkage} } @TechReport{GeneExpression_UWTR2001, AUTHOR = {Therese Biedl and Bro\v{n}a Brejov\'a and Erik D. Demaine and Ang\`ele M. Hamel and Tom\'a\v{s} Vina\v{r}}, TITLE = {Optimal Arrangement of Leaves in the Tree Representing Hierarchical Clustering of Gene Expression Data}, INSTITUTION = {Department of Computer Science, University of Waterloo}, NUMBER = {2001-14}, MONTH = {April}, YEAR = 2001, LENGTH = {12 pages}, COMMENTS = {Detailed results, source code, and running times}, PAPERS = {GeneExpression_WABI2002} } @InvitedTalk{MSU2001, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, SERIES = {Campus Theory Seminar}, SERIESURL = {http://www.pa.msu.edu/seminars/ctss/}, INSTITUTION = {College of Natural Science, Michigan State University}, INSTITUTIONURL = {http://www.pa.msu.edu/}, ADDRESS = {East Lansing, Michigan}, MONTH = {April 13}, YEAR = {2001}, LENGTH = {1 hour}, PAPERS = {JCDCG2000b} } % PAGES? @InProceedings{EuroCG2001, AUTHOR = {Oswin Aichholzer and David Bremner and Erik D. Demaine and Henk Meijer and Vera Sacrist\'an and Michael Soss}, TITLE = {Long Proteins with Unique Optimal Foldings in the H-P Model}, BOOKTITLE = {Proceedings of the 17th European Workshop on Computational Geometry (Euro-CG 2001)}, BOOKURL = {http://www.inf.fu-berlin.de/~cg01/}, MONTH = {March 26--28}, YEAR = 2001, ADDRESS = {Berlin, Germany}, LENGTH = {4 pages}, PAPERTYPE = {abstract}, PAPERS = {RedBlue_CGTA2002} } @InvitedTalk{DagstuhlMarch2001, AUTHOR = {Erik D. Demaine}, TITLE = {When Can You Fold a Map?}, SERIES = {Seminar on Computational Geometry}, SERIESURL = {http://www.dagstuhl.de/01121/}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {March 18--23}, YEAR = 2001 } @InProceedings{OSME2001, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Recent Results in Computational Origami}, BOOKTITLE = {Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001)}, BOOKURL = {http://web.merrimack.edu/~thull/osm/osm.html}, ADDRESS = {Monterey, California}, MONTH = {March 9--11}, YEAR = 2001, PAGES = {3--16}, LENGTH = {10 pages}, PAPERTYPE = {submitted version}, WEBPAGES = {folding}, UPDATES = {Barry A. Cipra wrote an article describing some of these results, ``In the Fold: Origami Meets Mathematics,'' SIAM News 34(8):200-201, October 2001.} } @InProceedings{OSME2001b, AUTHOR = {Marshall Bern and Erik Demaine and David Eppstein and Barry Hayes}, TITLE = {A Disk-Packing Algorithm for an Origami Magic Trick}, BOOKTITLE = {Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001)}, BOOKURL = {http://web.merrimack.edu/~thull/osm/osm.html}, ADDRESS = {Monterey, California}, MONTH = {March 9--11}, YEAR = 2001, PAGES = {17--28}, LENGTH = {10 pages}, PAPERS = {FUN98} } @InvitedTalk{StonyBrook2001a, AUTHOR = {Erik D. Demaine}, TITLE = {Flipping Polygons}, INSTITUTION = {Department of Computer Science, State University of New York}, INSTITUTIONURL = {http://www.cs.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {January 24}, YEAR = {2001}, LENGTH = {45 minutes}, PAPERS = {Flipturns; JCDCG2000a} } @InvitedTalk{ATT2001a, AUTHOR = {Erik D. Demaine}, TITLE = {Cache-Oblivious Search Trees}, INSTITUTION = {Shannon Laboratory, AT\&T Labs Research}, INSTITUTIONURL = {http://www.research.att.com/}, ADDRESS = {Florham Park, New Jersey}, MONTH = {January 16}, YEAR = {2001}, LENGTH = {1 hour}, PAPERS = {FOCS2000b} } @InProceedings{SODA2001a, AUTHOR = {Esther M. Arkin and Michael A. Bender and Erik D. Demaine and S\'andor P. Fekete and Joseph S. B. Mitchell and Saurabh Sethia}, TITLE = {Optimal Covering Tours with Turn Costs}, BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)}, BOOKURL = {http://www.siam.org/meetings/da01/}, ADDRESS = {Washington, DC}, MONTH = {January 7--9}, YEAR = {2001}, PAGES = {138--147}, LENGTH = {10 pages} } @InProceedings{SODA2001b, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz}, TITLE = {A Linear Lower Bound on Index Size for Text Retrieval}, BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)}, BOOKURL = {http://www.siam.org/meetings/da01/}, ADDRESS = {Washington, DC}, MONTH = {January 7--9}, YEAR = {2001}, PAGES = {289--294}, LENGTH = {6 pages}, PAPERS = {TextSearchLB_JAlgorithms2002} } @InProceedings{SODA2001c, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {On Universally Easy Classes for NP-complete Problems}, BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)}, BOOKURL = {http://www.siam.org/meetings/da01/}, ADDRESS = {Washington, DC}, MONTH = {January 7--9}, YEAR = {2001}, PAGES = {910--911}, LENGTH = {2 pages}, PAPERS = {UniversallyEasy_TCS} } @InProceedings{ALENEX2001, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Experiments on Adaptive Set Intersections for Text Retrieval Systems}, BOOKTITLE = {Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments (ALENEX 2001)}, bookurl = {http://www.research.att.com/~alb/ALENEX01/}, ADDRESS = {Washington, DC}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2153, MONTH = {January 5--6}, YEAR = 2001, PAGES = {91--104}, LENGTH = {14 pages}, PAPERS = {SODA2000}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2153/21530091.pdf.} } @Article{Ununfoldable, AUTHOR = {Marshall Bern and Erik D. Demaine and David Eppstein and Eric Kuo and Andrea Mantler and Jack Snoeyink}, TITLE = {Ununfoldable Polyhedra with Convex Faces}, JOURNAL = {Computational Geometry: Theory and Applications}, JOURNALURL = {http://www.elsevier.nl/locate/comgeo}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 1999 CGC Workshop on Computational Geometry.}, PAPERS = {CGC99; CCCG99b}, LENGTH = {14 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/9908003 of the Computing Research Repository (CoRR).} } @Article{Flipturns, AUTHOR = {Oswin Aichholzer and Carmen Cort\'es and Erik D. Demaine and Vida Dujmovi\'c and Jeff Erickson and Henk Meijer and Mark Overmars and Bel\'en Palop and Suneeta Ramaswami and Godfried T. Toussaint}, TITLE = {Flipturning Polygons}, JOURNAL = {Discrete \& Computational Geometry}, JOURNALURL = {http://link.springer.de/link/service/journals/00454/}, YEAR = {to appear}, LENGTH = {25 pages}, PAPERS = {JCDCG2000a}, PAPERKIND = {August 2000 draft}, COMMENTS = {The August 2000 draft is also available as arXiv:cs.CG/0008010 of the Computing Research Repository (CoRR).} } @Article{TPDS2001, AUTHOR = {Erik D. Demaine and Ian Foster and Carl Kesselman and Marc Snir}, TITLE = {Generalized Communicators in the Message Passing Interface}, JOURNAL = {IEEE Transactions on Parallel and Distributed Systems}, journalurl = {http://www.computer.org/tpds/}, VOLUME = 12, NUMBER = 6, MONTH = {June}, YEAR = 2001, PAGES = {610--616}, LENGTH = {19 pages}, COPYRIGHT = {The paper is \copyright 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.} } @InProceedings{ISAAC2000, AUTHOR = {Prosenjit Bose and Andrej Brodnik and Svante Carlsson and Erik D. Demaine and Rudolf Fleischer and Alejandro L\'opez-Ortiz and Pat Morin and J. Ian Munro}, TITLE = {Online Routing in Convex Subdivisions}, BOOKTITLE = {Proceedings of the 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000)}, BOOKURL = {http://www.iis.sinica.edu.tw/isaac00}, YEAR = 2000, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = 1969, ADDRESS = {Taipei, Taiwan}, MONTH = {December 18--20}, PAGES = {47--59}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {ObliviousRouting_IJCGA2002} } @InvitedTalk{HKUST2000b, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Polygonal Arcs and Convexifying Polygonal Cycles}, SERIES = {Noon Theory Seminar}, SERIESURL = {http://www.cs.ust.hk/tcsc/noon.html}, INSTITUTION = {Department of Computer Science, Hong Kong University of Science and Technology}, INSTITUTIONURL = {http://www.cs.ust.hk/}, ADDRESS = {Hong Kong, China}, MONTH = {December 11}, YEAR = {2000}, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{HKUST2000a, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, SERIES = {Computer Science Seminar}, INSTITUTION = {Department of Computer Science, Hong Kong University of Science and Technology}, INSTITUTIONURL = {http://www.cs.ust.hk/}, ADDRESS = {Hong Kong, China}, MONTH = {December 4}, YEAR = {2000}, LENGTH = {1 hour}, PAPERS = {JCDCG2000b} } @InvitedTalk{UTokyo2000, AUTHOR = {Erik D. Demaine}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, INSTITUTION = {Department of Information Science, University of Tokyo}, INSTITUTIONURL = {http://www.is.s.u-tokyo.ac.jp/}, ADDRESS = {Tokyo, Japan}, MONTH = {December 4}, YEAR = {2000}, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @Misc{MapFolding, AUTHOR = {Esther M. Arkin and Michael A. Bender and Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell and Saurabh Sethia and Steven S. Skiena}, TITLE = {When Can You Fold a Map?}, HOWPUBLISHED = {Manuscript}, MONTH = {June}, YEAR = 2001, LENGTH = {21 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/0011026 of the Computing Research Repository (CoRR).}, PAPERS = {MapFoldingWADS2001; CGW2000}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Proof clarifies a map-folding problem,'' Science News 158(26-27):406, December 23-30, 2002.

Helen Pearson also wrote an article describing these results, ``Origami solves road map riddle,'' Nature Science Update, February 18, 2002.} } @PlenaryTalk{JCDCG2000i, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, CONFERENCE = {Japan Conference on Discrete and Computational Geometry 2000 (JCDCG 2000)}, CONFERENCEURL = {http://gorogoro.cis.ibaraki.ac.jp/jcdcg2000/}, ADDRESS = {Tokyo, Japan}, MONTH = {November 22--25}, YEAR = {2000}, LENGTH = {45 minutes}, PAPERS = {JCDCG2000b} } @InProceedings{JCDCG2000c, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw and Joseph O'Rourke}, TITLE = {Enumerating Foldings and Unfoldings between Polygons and Polytopes}, BOOKTITLE = {Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2000)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/jcdcg2000/}, ADDRESS = {Tokyo, Japan}, MONTH = {November 22--25}, YEAR = 2000, PAGES = {9--12}, LENGTH = {12 pages}, WEBPAGES = {aleksandrov}, PAPERS = {Aleks_GC2002; AleksTR}, COMMENTS = {This paper is also available as arXiv:cs.CG/0107024 of the Computing Research Repository (CoRR).} } @InProceedings{JCDCG2000b, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, BOOKTITLE = {Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2000)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/jcdcg2000/}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2098, EDITOR = {Jin Akiyama and Mikio Kano and Masatsugu Urabe}, ADDRESS = {Tokyo, Japan}, MONTH = {November 22--25}, YEAR = 2000, PAGES = {113--124}, LENGTH = {12 pages}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2098/20980113.pdf.} } @InProceedings{JCDCG2000a, AUTHOR = {Oswin Aichholzer and Carmen Cort\'es and Erik D. Demaine and Vida Dujmovi\'c and Jeff Erickson and Henk Meijer and Mark Overmars and Bel\'en Palop and Suneeta Ramaswami and Godfried T. Toussaint}, TITLE = {Flipturning Polygons}, BOOKTITLE = {Proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2000)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/jcdcg2000/}, ADDRESS = {Tokyo, Japan}, MONTH = {November 22--25}, YEAR = 2000, LENGTH = {2 pages}, PAPERKIND = {abstract}, PAPERS = {Flipturns} } @InProceedings{FOCS2000b, AUTHOR = {Michael A. Bender and Erik D. Demaine and Martin Farach-Colton}, TITLE = {Cache-Oblivious B-Trees}, BOOKTITLE = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000)}, BOOKURL = {http://www.cs.cmu.edu/~FOCS2000/}, ADDRESS = {Redondo Beach, California}, MONTH = {November 12--14}, YEAR = 2000, PAGES = {399--409}, LENGTH = {11 pages}, PAPERS = {CacheObliviousBTrees} } @InProceedings{FOCS2000a, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Straightening Polygonal Arcs and Convexifying Polygonal Cycles}, BOOKTITLE = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000)}, BOOKURL = {http://www.cs.cmu.edu/~FOCS2000/}, ADDRESS = {Redondo Beach, California}, MONTH = {November 12--14}, YEAR = 2000, PAGES = {432--442}, LENGTH = {11 pages}, PAPERS = {Linkage; LinkageTR; EuroCG2000}, WEBPAGES = {linkage}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Unlocking Puzzling Polygons,'' Science News 158(13):200-201, September 23, 2000.

Joseph O'Rourke also wrote an article describing these results, ``Computational Geometry Column 39,'' International Journal of Computational Geometry and Applications, 10(4):441-444, 2000.} } @InvitedTalk{StonyBrook2000b, AUTHOR = {Erik D. Demaine}, TITLE = {Cutting Polygons with a Circular Saw}, INSTITUTION = {Department of Computer Science, State University of New York}, INSTITUTIONURL = {http://www.cs.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {November 1}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {CCCG2000a} } % not sure what seminar... @InProceedings{CGW2000, AUTHOR = {Esther M. Arkin and Michael A. Bender and Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell and Saurabh Sethia and Steven S. Skiena}, TITLE = {When Can You Fold a Map?}, BOOKTITLE = {Proceedings of the 10th Annual Fall Workshop on Computational Geometry}, BOOKURL = {http://www.ams.sunysb.edu/~jsbm/cgworkshop.html}, ADDRESS = {Stony Brook, New York}, MONTH = {October 27--28}, YEAR = 2000, LENGTH = {2 pages; 20 minutes}, PAPERKIND = {abstract}, PAPERS = {MapFolding}, UPDATES = {Ivars Peterson wrote an article describing these results, ``Proof clarifies a map-folding problem,'' Science News 158(26-27):406, December 23-30, 2002.

Helen Pearson also wrote an article describing these results, ``Origami solves road map riddle,'' Nature Science Update, February 18, 2002.} } @InvitedTalk{Cornell2000, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, SERIES = {Discrete Geometry and Graph Theory Seminar}, SERIESURL = {http://www.math.cornell.edu/~connelly/seminar.F00.html}, INSTITUTION = {Department of Mathematics, Cornell University}, INSTITUTIONURL = {http://www.math.cornell.edu/}, ADDRESS = {Ithaca, New York}, MONTH = {October 25}, YEAR = {2000}, LENGTH = {1 hour} } @InvitedTalk{AMSToronto2000, AUTHOR = {Erik D. Demaine}, TITLE = {Minimum-Turn Milling}, SERIES = {Special Session on Discrete and Applied Geometry}, SERIESURL = {http://www.ams.org/amsmtgs/2051_program_sunday.html#2051:AMSSSL3}, CONFERENCE = {AMS Fall Central Section Meeting}, CONFERENCEURL = {http://www.ams.org/amsmtgs/2051_program.html}, ADDRESS = {Toronto, Ontario, Canada}, MONTH = {September 23--24}, YEAR = {2000}, LENGTH = {25 minutes}, PAPERS = {SODA2001a} } @InProceedings{MFCS2000, AUTHOR = {Therese C. Biedl and Eowyn \v{C}enek and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer and Ming-Wei Wang}, TITLE = {Balanced $k$-Colorings}, BOOKTITLE = {Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000)}, BOOKURL = {http://www.mfcs.sk/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = {1893}, MONTH = {August 28--September 1}, ADDRESS = {Bratislava, Slovak Republic}, YEAR = 2000, PAGES = {202--211}, LENGTH = {10 pages}, PAPERS = {BalancedColoringDM; BalancedColoringTR}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1893/18930202.pdf.} } @InvitedTalk{Dagstuhl2000b, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Experience with Adaptive Set Intersection}, SERIES = {Seminar on Experimental Algorithmics}, SERIESURL = {http://www.dagstuhl.de/00371/}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {September 10--15}, YEAR = 2000, LENGTH = {25 minutes}, PAPERS = {ALENEX2001; SODA2000}, COMMENTS = {Both Erik Demaine and Ian Munro gave the talk.} } @TechReport{LockedTreeTR, AUTHOR = {Therese Biedl and Erik Demaine and Martin Demaine and Sylvain Lazard and Anna Lubiw and Joseph O'Rourke and Steve Robbins and Ileana Streinu and Godfried Toussaint and Sue Whitesides}, TITLE = {On Reconfiguring Tree Linkages: Trees can Lock}, INSTITUTION = {School of Computer Science, McGill University}, INSTITUTIONURL = {http://www.cs.mcgill.ca/}, NUMBER = {SOCS-00.7}, NUMBERURL = {http://www.cs.mcgill.ca/resrchpages/tech2000.html}, MONTH = {September}, YEAR = {2000}, LENGTH = {16 pages}, PAPERS = {LockedTreeDAM; CCCG98c}, COMMENTS = {This paper is also available as arXiv:cs.CG/9910024 of the Computing Research Repository (CoRR).}, WEBPAGES = {linkage} } @InProceedings{CCCG2000a, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Craig S. Kaplan}, TITLE = {Polygons Cuttable by a Circular Saw}, BOOKTITLE = {Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000)}, BOOKURL = {http://www.cs.unb.ca/conf/cccg/}, MONTH = {August 16--18}, YEAR = 2000, ADDRESS = {Fredericton, New Brunswick, Canada}, PAGES = {1--6}, LENGTH = {6 pages; 25 minutes}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.unb.ca/conf/cccg/eProceedings/36.ps.gz.} } @InProceedings{CCCG2000b, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph O'Rourke}, TITLE = {{PushPush} and {Push-1} are {NP}-hard in {2D}}, BOOKTITLE = {Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000)}, BOOKURL = {http://www.cs.unb.ca/conf/cccg/}, MONTH = {August 16--18}, YEAR = 2000, ADDRESS = {Fredericton, New Brunswick, Canada}, PAGES = {211--219}, LENGTH = {9 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.unb.ca/conf/cccg/eProceedings/26.ps.gz, and as cs.CG/0007021 of the Computing Research Repository (CoRR).

This version is updated from the original conference version in order to fix an error discovered by and solved together with Thomas Shermer.}, PAPERS = {PushPush2DTR}, WEBPAGES = {pushingblocks} } @InProceedings{CCCG2000c, AUTHOR = {Oswin Aichholzer and Erik D. Demaine and Jeff Erickson and Ferran Hurtado and Mark Overmars and Michael A. Soss and Godfried T. Toussaint}, TITLE = {Reconfiguring Convex Polygons}, BOOKTITLE = {Proceedings of the 12th Annual Canadian Conference on Computational Geometry (CCCG 2000)}, BOOKURL = {http://www.cs.unb.ca/conf/cccg/}, MONTH = {August 16--18}, YEAR = 2000, ADDRESS = {Fredericton, New Brunswick, Canada}, PAGES = {17--20}, LENGTH = {4 pages; 25 minutes}, WEBPAGES = {linkage}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.unb.ca/conf/cccg/eProceedings/42.ps.gz.}, PAPERS = {ConvexPolygonsCGTA} } @InvitedTalk{ISMP2000, AUTHOR = {Esther Arkin and Michael Bender and Erik Demaine and S\'andor Fekete and Joseph Mitchell and Saurabh Sethia}, TITLE = {Minimum turn milling}, SERIES = {Session on Geometric Instances of Graph Optimization Problems}, SERIESURL = {http://www.isye.gatech.edu/ismp2000/schedule/session_pages/WEA-14-IC215.html}, CONFERENCE = {17th International Symposium on Mathematical Programming}, CONFERENCEURL = {http://www.isye.gatech.edu/ismp2000/}, ADDRESS = {Atlanta, Georgia}, MONTH = {August 7--11}, YEAR = {2000}, LENGTH = {30 minutes}, PAPERS = {SODA2001a} } @InCollection{ClickomaniaGameTheory2000, AUTHOR = {Therese C. Biedl and Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer and Lars Jacobsen and J. Ian Munro}, TITLE = {The Complexity of Clickomania}, BOOKTITLE = {More Games of No Chance}, BOOKURL = {http://www.msri.org/publications/books/Book42/}, EDITOR = {R. J. Nowakowski}, YEAR = 2002, PAGES = {389--404}, NOTE = {Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24--28, 2000.}, LENGTH = {15 pages}, COMMENTS = {This paper is also available as arXiv:cs.CC/0107031 of the Computing Research Repository (CoRR).

The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/biedl.ps.gz.} } @InCollection{Phutball, AUTHOR = {Erik D. Demaine and Martin L. Demaine and David Eppstein}, TITLE = {Phutball Endgames are Hard}, BOOKTITLE = {More Games of No Chance}, BOOKURL = {http://www.msri.org/publications/books/Book42/}, EDITOR = {R. J. Nowakowski}, YEAR = 2002, PAGES = {351--360}, NOTE = {Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24--28, 2000.}, LENGTH = {9 pages}, COMMENTS = {This paper is also available as arXiv:cs.CC/0008025 of the Computing Research Repository (CoRR).

The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/dephut.ps.gz.} } @InCollection{GameTheory2000, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Helena A. Verrill}, TITLE = {Coin-Moving Puzzles}, BOOKTITLE = {More Games of No Chance}, BOOKURL = {http://www.msri.org/publications/books/Book42/}, EDITOR = {R. J. Nowakowski}, YEAR = 2002, PAGES = {405--431}, NOTE = {Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24--28, 2000.}, LENGTH = {25 pages}, COMMENTS = {This paper is also available as arXiv:cs.DM/0204002 of the Computing Research Repository (CoRR).

The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/decoins.ps.gz.

The talk is available from MSRI in streaming video.} } @TechReport{AleksTR, AUTHOR = {Erik Demaine and Martin Demaine and Anna Lubiw and Joseph O'Rourke}, TITLE = {Examples, Counterexamples, and Enumeration Results for Foldings and Unfoldings between Polygons and Polytopes}, INSTITUTION = {Smith College}, NUMBER = {069}, MONTH = {July}, YEAR = 2000, LENGTH = {54 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/0007019 of the Computing Research Repository (CoRR).}, PAPERS = {JCDCG2000c}, WEBPAGES = {aleksandrov} } @PlenaryTalk{UWMathGradConf2000, AUTHOR = {Erik D. Demaine}, TITLE = {Research is Fun: A Brief Look at Some Work in Algorithms}, CONFERENCE = {University of Waterloo Faculty of Mathematics Graduate Student Conference}, CONFERENCEURL = {http://www.math.uwaterloo.ca/Mathgrad_Office/gradconf/}, MONTH = {June 26--27}, YEAR = {2000}, LENGTH = {50 minutes} } @InvitedTalk{DM2000, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Minisymposium on Computational Geometry: Folding}, CONFERENCE = {10th SIAM Conference on Discrete Mathematics}, CONFERENCEURL = {http://www.siam.org/meetings/dm00/}, ADDRESS = {Minneapolis, Minnesota}, MONTH = {June 12--15}, YEAR = {2000}, LENGTH = {25 minutes}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{Oberwolfach2000, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Linkages, Paper, and Polyhedra}, SERIES = {Discrete Geometry Meeting}, SERIESURL = {http://www.mfo.de/Meetings/Meeting_Program_2000.html#T0022}, CONFERENCE = {Mathematisches Forschungsinstitut Oberwolfach}, CONFERENCEURL = {http://www.mfo.de/}, ADDRESS = {Oberwolfach-Walke, Germany}, MONTH = {May 28--June 3}, YEAR = 2000, LENGTH = {50 minutes} } @InvitedTalk{StonyBrook2000a, AUTHOR = {Erik D. Demaine}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Algorithms seminar}, INSTITUTION = {Department of Computer Science, State University of New York}, INSTITUTIONURL = {http://www.cs.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {April 7}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{AMSLowell2000, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Special Session on Discrete Geometry}, CONFERENCE = {2000 AMS Spring Eastern Section Meeting \#952}, CONFERENCEURL = {http://www.ams.org/amsmtgs/2047_progfull.html}, ADDRESS = {Lowell, Massachusetts}, MONTH = {April 1-2}, YEAR = 2000, LENGTH = {30 minutes}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{Smith2000b, AUTHOR = {Erik D. Demaine}, TITLE = {PushPush is NP-hard in 2D}, SERIES = {Research Seminar}, INSTITUTION = {Department of Computer Science, Smith College}, INSTITUTIONURL = {http://www.cs.smith.edu/}, ADDRESS = {Northampton, Massachusetts}, MONTH = {March 31}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {PushPush2DTR}, WEBPAGES = {pushpush; pushingblocks} } @InvitedTalk{Smith2000a, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Cutting Paper}, SERIES = {Computational Geometry Lecture}, INSTITUTION = {Department of Computer Science, Smith College}, INSTITUTIONURL = {http://www.cs.smith.edu/}, ADDRESS = {Northampton, Massachusetts}, MONTH = {March 30}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {JCDCG98}, WEBPAGES = {foldcut} } @TechReport{BalancedColoringTR, AUTHOR = {Therese C. Biedl and Eowyn \v{C}enek and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer and Ming-Wei Wang}, TITLE = {Balanced $k$-Colorings}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-2000-08}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-2000-08/}, MONTH = {March}, YEAR = 2000, LENGTH = {11 pages}, PAPERS = {BalancedColoringDM; MFCS2000} } @InvitedTalk{Tutte2000, AUTHOR = {Erik D. Demaine}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Tutte Colloquium}, INSTITUTION = {Department of Combinatorics and Optimization, University of Waterloo}, INSTITUTIONURL = {http://www.math.uwaterloo.ca/CandO_Dept/homepage.html}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {March 17}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{Berlin2000b, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Polyhedra}, SERIES = {Informatik-Kolloquiums}, SERIESURL = {http://www.inf.fu-berlin.de/~godau/noon.html}, INSTITUTION = {Institut f\"ur Informatik, Freie Universit\"at Berlin}, INSTITUTIONURL= {http://www.inf.fu-berlin.de/}, ADDRESS = {Berlin, Germany}, MONTH = {March 10}, YEAR = 2000, LENGTH = {1 hour} } @InvitedTalk{Berlin2000a, AUTHOR = {Erik D. Demaine}, TITLE = {Matchings in Cubic Planar Graphs}, SERIES = {Mittagsseminars}, SERIESURL = {http://www.inf.fu-berlin.de/~godau/noon.html}, INSTITUTION = {Institut f\"ur Informatik, Freie Universit\"at Berlin}, INSTITUTIONURL= {http://www.inf.fu-berlin.de/}, ADDRESS = {Berlin, Germany}, MONTH = {March 9}, YEAR = 2000, LENGTH = {30 minutes}, PAPERS = {MatchingJAlgorithms; SODA99b} } @InvitedTalk{Dagstuhl2000a, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Adaptive Set Intersections, Unions, and Differences}, SERIES = {Seminar on Data Structures}, SERIESURL = {http://www.dagstuhl.de/00091/}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {February 27--March 3}, YEAR = 2000, PAPERS = {SODA2000} } @TechReport{PushPush2DTR, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph O'Rourke}, TITLE = {PushPush is NP-hard in 2D}, INSTITUTION = {Smith College}, NUMBER = {065}, MONTH = {January}, YEAR = 2000, LENGTH = {18 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/0001019 of the Computing Research Repository (CoRR).}, PAPERS = {CCCG2000b}, WEBPAGES = {pushpush; pushingblocks} } @InProceedings{EuroCG2000, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Every Polygon Can Be Untangled}, BOOKTITLE = {Proceedings of the 16th European Workshop on Computational Geometry (Euro-CG 2000)}, BOOKURL = {http://www.cs.bgu.ac.il/~cg2000/}, MONTH = {March 13--15}, YEAR = 2000, ADDRESS = {Eilat, Israel}, LENGTH = {4 pages}, PAPERTYPE = {abstract}, PAPERS = {Linkage; LinkageTR; FOCS2000a}, WEBPAGES = {linkage}, COMMENTS = {This abstract is also available from the electronic abstracts as http://www.cs.bgu.ac.il/~cg2000/PS/27.ps.} } @InvitedTalk{Courant2000, AUTHOR = {Erik D. Demaine}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Geometry Seminar}, SERIESURL = {http://www.math.nyu.edu/seminars/geometry_seminar.html}, INSTITUTION = {Courant Institute of Mathematical Sciences, New York University}, INSTITUTIONURL = {http://www.math.nyu.edu/}, ADDRESS = {New York, NY}, MONTH = {January 25}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{Waterloo2000a, AUTHOR = {Erik D. Demaine}, TITLE = {Convexifying Polygons and Straightening Polygonal Arcs}, SERIES = {Algorithms and Complexity Seminar}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {January 19}, YEAR = 2000, LENGTH = {1 hour}, PAPERS = {Linkage}, WEBPAGES = {linkage} } @InvitedTalk{Berlin99, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Cutting Paper}, SERIES = {Algorithmic Discrete Mathematics Graduate Program}, SERIESURL = {http://www.inf.fu-berlin.de/graduate-programs/adm/}, INSTITUTION = {Institut f\"ur Informatik, Freie Universit\"at Berlin}, INSTITUTIONURL= {http://www.inf.fu-berlin.de/}, ADDRESS = {Berlin, Germany}, MONTH = {December 13}, YEAR = 1999, LENGTH = {1 hour}, PAPERS = {JCDCG98}, WEBPAGES = {foldcut} } @InvitedTalk{GeomFest99, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw}, TITLE = {Collapsing Polyhedra}, CONFERENCE = {4th Geometry Festival}, CONFERENCEURL = {http://www.auburn.edu/~bezdean/4thfest.html}, ADDRESS = {Budapest, Hungary}, MONTH = {December 1}, YEAR = 1999, LENGTH = {30 minutes} } @Article{MatchingJAlgorithms, AUTHOR = {Therese C. Biedl and Prosenjit Bose and Erik D. Demaine and Anna Lubiw}, TITLE = {Efficient Algorithms for Petersen's Matching Theorem}, JOURNAL = {Journal of Algorithms}, JOURNALURL = {http://www.apnet.com/www/journal/al.htm}, VOLUME = 38, PAGES = {110--134}, YEAR = {2001}, NOTE = {Special issue of selected papers from the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000.}, LENGTH = {23 pages}, PAPERS = {MatchingBoundsISAAC2001; SODA99b}, COPYRIGHT = {The paper is \copyright Academic Press.} } @InvitedTalk{Carleton99, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, INSTITUTION = {School of Computer Science, Carleton University}, INSTITUTIONURL = {http://www.scs.carleton.ca/}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {October 27}, YEAR = 1999, LENGTH = {1 hour} } @InvitedTalk{StonyBrook99b, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Unfolding Polyhedra}, INSTITUTION = {Department of Applied Mathematics and Statistics, State University of New York}, INSTITUTIONURL = {http://www.ams.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {October 20}, YEAR = 1999, LENGTH = {1 hour} } @TechReport{3DChainsTR, AUTHOR = {T. Biedl and E. Demaine and M. Demaine and S. Lazard and A. Lubiw and J. O'Rourke and M. Overmars and S. Robbins and I. Streinu and G. Toussaint and S. Whitesides}, TITLE = {Locked and Unlocked Polygonal Chains in 3D}, INSTITUTION = {Smith College}, NUMBER = {060}, MONTH = {October}, YEAR = 1999, LENGTH = {29 pages}, PAPERS = {3DChains_DCG2001; SODA99c}, COMMENTS = {This paper is also available as arXiv:cs.CG/9910009 of the Computing Research Repository (CoRR).} } @InProceedings{SODA2000, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Adaptive Set Intersections, Unions, and Differences}, BOOKTITLE = {Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000)}, BOOKURL = {http://www.siam.org/meetings/da00/}, ADDRESS = {San Francisco, California}, MONTH = {January 9--11}, YEAR = 2000, PAGES = {743--752}, LENGTH = {10 pages; 20 minutes}, PAPERS = {ALENEX2001} } @Article{CGTA2000, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell}, TITLE = {Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami}, JOURNAL = {Computational Geometry: Theory and Applications}, JOURNALURL = {http://www.elsevier.nl/locate/comgeo}, VOLUME = 16, NUMBER = 1, YEAR = {2000}, PAGES = {3--21}, NOTE = {Special issue of selected papers from the 1998 CGC Workshop on Computational Geometry.}, LENGTH = {23 pages}, PAPERS = {SoCG99; CGC98}, WEBPAGES = {wrapping}, COPYRIGHT = {The paper is \copyright Elsevier Science Netherlands.} } @InProceedings{FSTTCS99, AUTHOR = {Erik D. Demaine and J. Ian Munro}, TITLE = {Fast Allocation and Deallocation with an Improved Buddy System}, BOOKTITLE = {Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FST \& TCS'99)}, BOOKURL = {http://www.imsc.ernet.in/~fsttcs99/}, ADDRESS = {Chennai, India}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = {1738}, MONTH = {December 13--15}, YEAR = 1999, PAGES = {84--96}, LENGTH = {12 pages}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1738/17380084.pdf.}, COPYRIGHT = {The paper is \copyright Springer-Verlag.} } @Article{CGcolumn37, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Computational Geometry Column 37}, JOURNAL = {International Journal of Computational Geometry and Applications}, JOURNALURL = {http://www.wspc.com/journals/ijcga/ijcga.html}, VOLUME = 10, NUMBER = 1, MONTH = {February}, YEAR = 2000, PAGES = {103--107}, NOTE = {Also appears in SIGACT News, volume 30, number 3, issue #112, September 1999, pages 39-42.}, LENGTH = {4 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/9908007 of the Computing Research Repository (CoRR).}, UPDATES = {I understand that Kasturi Varadarajan's problem (is there a topological cube with orthogonal opposite facets?) has been solved by Günter Ziegler.

Also, John Conway's Holyhedron Problem has been solved by Jade Vinson in ``On Holyhedra'' (with an introduction by John Conway), Discrete and Computational Geometry, volume 24, pages 85-104, 2000. See Jade's webpage or Springer's webpage. There is still work to be done in order to win the $10,000 / (number of faces) reward, because Vinson's polyhedron has 78,585,627 faces and genus 60,380,421!} } @InProceedings{ISAAC99, AUTHOR = {Therese C. Biedl and Erik D. Demaine and Sylvain Lazard and Steven M. Robbins and Michael A. Soss}, TITLE = {Convexifying Monotone Polygons}, BOOKTITLE = {Proceedings of the 10th Annual International Symposium on Algorithms and Computation (ISAAC'99)}, BOOKURL = {http://www.cs.iitm.ernet.in/~tcslab/isaac99/}, ADDRESS = {Chennai, India}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = {1741}, MONTH = {December 16--18}, YEAR = 1999, PAGES = {415--424}, LENGTH = {10 pages}, PAPERS = {MonotonePolygonsTR}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1741/17410415.pdf.}, WEBPAGES = {linkage} } @InProceedings{CGC99, AUTHOR = {Marshall Bern and Erik D. Demaine and David Eppstein and Eric Kuo and Andrea Mantler and Jack Snoeyink}, TITLE = {Ununfoldable Polyhedra with Triangular Faces}, BOOKTITLE = {Proceedings of the 4th CGC Workshop on Computational Geometry}, BOOKURL = {http://www.cs.jhu.edu/labs/cgc/cgc99}, ADDRESS = {Baltimore, Maryland}, MONTH = {October 15--16}, YEAR = 1999, LENGTH = {2 pages; 20 minutes}, COMMENTS = {Andrea Mantler gave the talk; you can find slides and cool pictures on her web page.}, PAPERKIND = {abstract}, PAPERS = {Ununfoldable; CCCG99b} } @TechReport{MonotonePolygonsTR, AUTHOR = {Therese C. Biedl and Erik D. Demaine and Sylvain Lazard and Steven M. Robbins and Michael A. Soss}, TITLE = {Convexifying Monotone Polygons}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-99-03}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-99-03/}, MONTH = {March}, YEAR = 1999, LENGTH = {12 pages}, PAPERS = {ISAAC99}, WEBPAGES = {linkage} } @InvitedTalk{Ascona99, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, CONFERENCE = {Monte Verite Conference on Discrete and Computational Geometry}, CONFERENCEURL = {http://www.inf.ethz.ch/department/TI/ew/MonteVerita/index.html}, ALTCONFURL = {http://www.csf-mv.ethz.ch/Official/Workshops/WS1999/welzl.html}, ADDRESS = {Ascona, Switzerland}, MONTH = {June 29}, YEAR = 1999, LENGTH = {30 minutes}, COMMENTS = {A photo of me giving the talk (taken by Emo Welzl):

}, WEBPAGES = {linkage} } @TechReport{CCCG99OpenTR, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG'99}}, INSTITUTION = {Smith College}, NUMBER = {066}, MONTH = {March}, YEAR = 2000, LENGTH = {6 pages}, PAPERS = {CCCG99Open} } @InProceedings{CCCG99Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG'99}}, BOOKTITLE = {Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99)}, BOOKURL = {http://www.cs.ubc.ca/conferences/CCCG/}, MONTH = {August 15--18}, YEAR = 1999, ADDRESS = {Vancouver, British Columbia, Canada}, LENGTH = {6 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.ubc.ca/conferences/CCCG/elec_proc/open.ps.gz.}, PAPERS = {CCCG2001Open; CCCG2000Open; CCCG99OpenTR} } @Misc{HingedPolyforms, AUTHOR = {Erik D. Demaine and Martin L. Demaine and David Eppstein and Greg N. Frederickson and Erich Friedman}, TITLE = {Hinged Dissection of Polyominoes and Polyforms}, HOWPUBLISHED = {Manuscript}, MONTH = {July}, YEAR = 1999, LENGTH = {26 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/9907018 of the Computing Research Repository (CoRR).}, PAPERS = {CCCG99a} } @InProceedings{CCCG99a, AUTHOR = {Erik D. Demaine and Martin L. Demaine and David Eppstein and Erich Friedman}, TITLE = {Hinged Dissection of Polyominoes and Polyiamonds}, BOOKTITLE = {Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99)}, BOOKURL = {http://www.cs.ubc.ca/conferences/CCCG/}, MONTH = {August 15--18}, YEAR = 1999, ADDRESS = {Vancouver, British Columbia, Canada}, LENGTH = {15 pages}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.ps.gz. It is also available as arXiv:cs.CG/9970183v1 of the Computing Research Repository (CoRR).} } @TechReport{UnunfoldableTR, AUTHOR = {Marshall Bern and Erik D. Demaine and David Eppstein and Eric Kuo}, TITLE = {Ununfoldable Polyhedra}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-99-04}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-99-04/}, MONTH = {August}, YEAR = 1999, LENGTH = {13 pages}, PAPERS = {Ununfoldable; CCCG99b; CGC99}, COMMENTS = {This paper is published in CCCG'99.
It is also available as arXiv:cs.CG/9908003v1 of the Computing Research Repository (CoRR).} } @InProceedings{CCCG99b, AUTHOR = {Marshall Bern and Erik D. Demaine and David Eppstein and Eric Kuo}, TITLE = {Ununfoldable Polyhedra}, BOOKTITLE = {Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99)}, BOOKURL = {http://www.cs.ubc.ca/conferences/CCCG/}, MONTH = {August 15--18}, YEAR = 1999, ADDRESS = {Vancouver, British Columbia, Canada}, LENGTH = {13 pages}, PAPERS = {Ununfoldable; CGC99}, COMMENTS = {This paper is also available from the electronic proceedings as http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp38.ps.gz.
It is also available as version 1 of arXiv:cs.CG/9908003 of the Computing Research Repository (CoRR).}, UPDATES = {We have solved some of the open problems mentioned in this paper; see the CGTA paper.} } @TechReport{ResizableArraysTR, AUTHOR = {Andrej Brodnik and Svante Carlsson and Erik D. Demaine and J. Ian Munro and Robert Sedgewick}, TITLE = {Resizable Arrays in Optimal Time and Space}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-99-09}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-99-09/}, YEAR = {1999}, LENGTH = {19 pages}, PAPERS = {WADS99a} } @InProceedings{WADS99a, AUTHOR = {Andrej Brodnik and Svante Carlsson and Erik D. Demaine and J. Ian Munro and Robert Sedgewick}, TITLE = {Resizable Arrays in Optimal Time and Space}, BOOKTITLE = {Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99)}, BOOKURL = {http://www.scs.carleton.ca/~wads/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, EDITOR = {Frank Dehne and Arvind Gupta and J\"org-R\"udiger Sack and Roberto Tamassia}, VOLUME = 1663, MONTH = {August 11--14}, YEAR = 1999, ADDRESS = {Vancouver, British Columbia, Canada}, PAGES = {37--48}, LENGTH = {12 pages}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, PAPERS = {ResizableArraysTR}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1663/16630037.pdf.} } @InProceedings{WADS99b, AUTHOR = {David Benoit and Erik D. Demaine and J. Ian Munro and Venkatesh Raman}, TITLE = {Representing Trees of Higher Degree}, BOOKTITLE = {Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99)}, BOOKURL = {http://www.scs.carleton.ca/~wads/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, EDITOR = {Frank Dehne and Arvind Gupta and J\"org-R\"udiger Sack and Roberto Tamassia}, VOLUME = 1663, MONTH = {August 11--14}, YEAR = 1999, ADDRESS = {Vancouver, British Columbia, Canada}, PAGES = {169--180}, LENGTH = {12 pages}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1663/16630169.pdf.} } @Misc{PolytopeReconstruction, AUTHOR = {Erik D. Demaine and Jeff Erickson}, TITLE = {Open Problems on Polytope Reconstruction}, HOWPUBLISHED = {Manuscript}, MONTH = {July}, YEAR = 1999, LENGTH = {2 pages} } @InvitedTalk{UIUC99, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, SERIES = {Theory Seminar}, INSTITUTION = {Department of Computer Science, University of Illinois}, INSTITUTIONURL = {http://www.cs.uiuc.edu/}, ADDRESS = {Urbana-Champaign, Illinois}, MONTH = {April 28}, YEAR = 1999, LENGTH = {1 hour}, WEBPAGES = {linkage} } @InvitedTalk{Waterloo99a, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, SERIES = {Algorithms and Complexity Seminar}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {April 7}, YEAR = 1999, LENGTH = {1 hour}, WEBPAGES = {linkage} } @InvitedTalk{McGill99a, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, SERIES = {Algorithms Seminar}, INSTITUTION = {School of Computer Science, McGill University}, INSTITUTIONURL = {http://www.cs.mcgill.ca/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {March 31}, YEAR = 1999, LENGTH = {1 hour}, WEBPAGES = {linkage} } @InvitedTalk{StonyBrook99a, AUTHOR = {Erik D. Demaine}, TITLE = {Straightening Chains and Convexifying Polygons}, INSTITUTION = {Department of Applied Mathematics and Statistics, State University of New York}, INSTITUTIONURL = {http://www.ams.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {March 17}, YEAR = 1999, LENGTH = {1 hour}, WEBPAGES = {linkage} } @InProceedings{BRIDGES99, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw}, TITLE = {Polyhedral Sculptures with Hyperbolic Paraboloids}, BOOKTITLE = {Proceedings of the 2nd Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES'99)}, BOOKURL = {http://www.sckans.edu/~bridges/}, MONTH = {July 30--August 1}, YEAR = 1999, ADDRESS = {Winfield, Kansas}, PAGES = {91--100}, LENGTH = {10 pages}, COMMENTS = {To keep the file smaller, the paper does not include the photographs in Figures 5, 6, and 7. Please refer to my hypar webpage to see these photographs.

Here are some photographs from during and after my talk, taken by Carlo Séquin.

}, WEBPAGES = {hypar}, UPDATES = {Ivars Peterson describes these results in his book, Fragments of Infinity: A Kaleidoscope of Math and Art, John Wiley & Sons, Inc., 2001, pages 79-80.} } @InProceedings{SoCG99v, AUTHOR = {Erik Demaine and Martin Demaine and Anna Lubiw and Joseph O'Rourke and Irena Pashchenko}, TITLE = {Metamorphosis of the Cube}, BOOKTITLE = {8th Annual Video Review of Computational Geometry, Proceedings of the 15th Annual ACM Symposium on Computational Geometry}, BOOKURL = {http://www.cs.miami.edu/events/SCG99}, MONTH = {June 13--16}, YEAR = 1999, ADDRESS = {Miami Beach, Florida}, PAGES = {409--410}, LENGTH = {2 pages}, WEBPAGES = {metamorphosis} } @InProceedings{SoCG99, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell}, TITLE = {Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami}, BOOKTITLE = {Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SoCG'99)}, BOOKURL = {http://www.cs.miami.edu/events/SCG99}, MONTH = {June 13--16}, YEAR = 1999, ADDRESS = {Miami Beach, Florida}, PAGES = {105--114}, LENGTH = {10 pages}, WEBPAGES = {wrapping}, PAPERS = {CGTA2000; CGC98} } @InvitedTalk{StonyBrook98, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Cutting Paper}, INSTITUTION = {Department of Applied Mathematics and Statistics, State University of New York}, INSTITUTIONURL = {http://www.ams.sunysb.edu/}, ADDRESS = {Stony Brook, New York}, MONTH = {November 25}, YEAR = 1998, LENGTH = {1 hour}, PAPERS = {JCDCG98}, WEBPAGES = {foldcut} } @InvitedTalk{Tutte98, AUTHOR = {Therese C. Biedl and Prosenjit Bose and Erik D. Demaine and Anna Lubiw}, TITLE = {Efficient Algorithms for Petersen's Matching Theorem}, SERIES = {Tutte Colloquium}, INSTITUTION = {Department of Combinatorics and Optimization, University of Waterloo}, INSTITUTIONURL = {http://www.math.uwaterloo.ca/CandO_Dept/homepage.html}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {November 20}, YEAR = 1998, LENGTH = {1 hour}, PAPERS = {SODA99b} } @InvitedTalk{McGill98, AUTHOR = {Erik D. Demaine}, TITLE = {Folding and Cutting Paper}, SERIES = {Algorithms Seminar}, SERIESURL = {http://cgm.cs.mcgill.ca/~therese/seminar}, INSTITUTION = {School of Computer Science, McGill University}, INSTITUTIONURL = {http://www.cs.mcgill.ca/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {October 28}, YEAR = 1998, LENGTH = {1 hour}, PAPERS = {JCDCG98}, WEBPAGES = {foldcut} } @InProceedings{CGC98, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell}, TITLE = {Folding Any Silhouette from a Strip}, BOOKTITLE = {Proceedings of the 3rd CGC Workshop on Computational Geometry}, BOOKURL = {http://www.cs.brown.edu/cgc/cgc98/}, ADDRESS = {Providence, Rhode Island}, MONTH = {October 11--12}, YEAR = 1998, COMMENTS = {Here is a bicolor flat origami I made for the talk.
(Photograph by Roberto Tamassia)

}, LENGTH = {2 pages; 20 minutes}, PAPERKIND = {abstract}, WEBPAGES = {wrapping}, PAPERS = {CGTA2000; SoCG99} } @ConferenceTalk{CodesTrees98, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Adaptive Computation of the Intersection of a Collection of Sets}, CONFERENCE = {DIMACS Workshop on Codes and Trees: Algorithmic and Information Theoretic Approaches}, CONFERENCEURL = {http://dimacs.rutgers.edu/Workshops/Codes/}, ADDRESS = {Piscataway, New Jersey}, MONTH = {October 5--7}, YEAR = 1998, LENGTH = {30 minutes}, PAPERS = {SODA2000; SInterectTR} } @TechReport{SIntersectTR, AUTHOR = {Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Adaptive Set Intersections}, NUMBER = {TR98-120}, INSTITUTION = {Faculty of Computer Science, University of New Brunswick}, YEAR = 1998, PAPERS = {SODA2000}, TALKS = {CodesTrees98} } @InProceedings{SODA99a, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw}, TITLE = {Folding and One Straight Cut Suffice}, BOOKTITLE = {Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99)}, BOOKURL = {http://www.siam.org/meetings/da99/}, ADDRESS = {Baltimore, Maryland}, MONTH = {January 17--19}, YEAR = 1999, PAGES = {891--892}, LENGTH = {2 pages; 20 minutes}, PAPERS = {JCDCG98}, WEBPAGES = {foldcut}, UPDATES = {Joseph O'Rourke also wrote an article describing these results, ``Computational Geometry Column 36,'' International Journal of Computational Geometry and Applications, 9(6):615-618, 1999.} } @InProceedings{SODA99b, AUTHOR = {Therese C. Biedl and Prosenjit Bose and Erik D. Demaine and Anna Lubiw}, TITLE = {Efficient Algorithms for Petersen's Matching Theorem}, BOOKTITLE = {Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99)}, BOOKURL = {http://www.siam.org/meetings/da99/}, ADDRESS = {Baltimore, Maryland}, MONTH = {January 17--19}, YEAR = 1999, PAGES = {130--139}, LENGTH = {10 pages; 20 minutes}, PAPERS = {MatchingJAlgorithms} } @InProceedings{SODA99c, AUTHOR = {T. Biedl and E. Demaine and M. Demaine and S. Lazard and A. Lubiw and J. O'Rourke and M. Overmars and S. Robbins and I. Streinu and G. Toussaint and S. Whitesides}, TITLE = {Locked and Unlocked Polygonal Chains in {3D}}, BOOKTITLE = {Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99)}, BOOKURL = {http://www.siam.org/meetings/da99/}, ADDRESS = {Baltimore, Maryland}, MONTH = {January 17--19}, YEAR = 1999, PAGES = {866--867}, LENGTH = {2 pages; 20 minutes}, PAPERs = {3DChains_DCG2001; 3DChainsTR}, COMMENTS = {This paper is also available as arXiv:cs.CG/9811019 of the Computing Research Repository (CoRR).}, UPDATES = {The pocket-flipping algorithm described in this paper has been implemented by Jean-Philippe Cote and Marc-Andre Sauve as a course project for Godfried Toussaint. Their project web page includes the detailed history of the problem, and an applet to demonstrate the motion.} } @InProceedings{JCDCG98, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw}, TITLE = {Folding and Cutting Paper}, BOOKTITLE = {Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG'98)}, BOOKURL = {http://ranran.cis.ibaraki.ac.jp/jcdcg98/jcdcg98.html}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = 1763, EDITOR = {Jin Akiyama and Mikio Kano and Masatsugu Urabe}, ADDRESS = {Tokyo, Japan}, MONTH = {December 9--12}, YEAR = 1998, PAGES = {104--117}, NOTE = {Shorter version in \emph{Proceedings of the Japan Conference on Computational Geometry}, pages 5--9.}, LENGTH = {15 pages}, PAPERS = {SODA99a}, WEBPAGES = {foldcut}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, UPDATES = {Joseph O'Rourke also wrote an article describing these results, ``Computational Geometry Column 36,'' International Journal of Computational Geometry and Applications, 9(6):615-618, 1999.} } @InProceedings{GD98, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Planar Drawings of Origami Polyhedra}, BOOKTITLE = {Proceedings of the 6th Symposium on Graph Drawing (GD'98)}, BOOKURL = {http://www-cgrl.cs.mcgill.ca/gd98/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/index.html}, VOLUME = {1547}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 13--15}, YEAR = 1998, PAGES = {438-440}, LENGTH = {2 pages}, TALKKIND = {poster}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, COMMENTS = {This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1547/15470438.pdf.}, PAPERS = {DrawingExtremeTR} } @TechReport{DrawingExtremeTR, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Planar Drawings of Origami Polyhedra}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-98-17}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-98-17/}, MONTH = {August}, YEAR = 1998, LENGTH = {13 pages}, PAPERS = {GD98} } @InProceedings{CCCG98a, AUTHOR = {Therese C. Biedl and Erik D. Demaine and Martin L. Demaine and Anna Lubiw and Godfried T. Toussaint}, TITLE = {Hiding Disks in Folded Polygons}, BOOKTITLE = {Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98)}, bookurl = {http://cgm.cs.mcgill.ca/cccg98/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 10--12}, YEAR = 1998, WEBPAGES = {wrapping}, length = {11 pages; 20 minutes}, comments = {This paper is also available from the electronic proceedings as http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-hiding.ps.gz.}, updates = {One problem explored in this paper, packing the largest pair of equal-radius disks in a given polygon, have been further developed in several followup papers. See my webpage on wrapping for a summary and references.

Erin McLeish prepared an excellent webpage describing these and related results and algorithms, including a Java applet.} } @InProceedings{CCCG98b, AUTHOR = {Therese Biedl and Erik Demaine and Martin Demaine and Anna Lubiw and Mark Overmars and Joseph O'Rourke and Steve Robbins and Sue Whitesides}, TITLE = {Unfolding Some Classes of Orthogonal Polyhedra}, BOOKTITLE = {Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98)}, BOOKURL = {http://cgm.cs.mcgill.ca/cccg98/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 10--12}, YEAR = 1998, LENGTH = {10 pages; 20 minutes}, COMMENTS = {This paper is also available from the electronic proceedings as http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-unfolding.ps.gz.} } @InProceedings{CCCG98c, AUTHOR = {Therese Biedl and Erik Demaine and Martin Demaine and Sylvain Lazard and Anna Lubiw and Joseph O'Rourke and Steve Robbins and Ileana Streinu and Godfried Toussaint and Sue Whitesides}, TITLE = {On Reconfiguring Tree Linkages: Trees can Lock}, BOOKTITLE = {Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG'98)}, BOOKURL = {http://cgm.cs.mcgill.ca/cccg98/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 10--12}, YEAR = 1998, LENGTH = {11 pages; 20 minutes}, PAPERS = {LockedTreeDAM; LockedTreeTR}, COMMENTS = {This paper is also available from the electronic proceedings as http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-reconfiguring.ps.gz.}, WEBPAGES = {linkage} } @InProceedings{FUN98, AUTHOR = {Marshall Bern and Erik Demaine and David Eppstein and Barry Hayes}, TITLE = {A Disk-Packing Algorithm for an Origami Magic Trick}, BOOKTITLE = {Proceedings of the International Conference on Fun with Algorithms (FUN'98)}, BOOKURL = {http://www.di.unipi.it/fun98/}, ADDRESS = {Isola d'Elba, Italy}, MONTH = {June 18--20}, YEAR = 1998, PAGES = {32--42}, LENGTH = {11 pages}, PAPERS = {OSME2001} } @InvitedTalk{UNB98, AUTHOR = {Erik D. Demaine}, TITLE = {Higher-Order Concurrency in Java}, INSTITUTION = {University of New Brunswick}, INSTITUTIONURL = {http://www.unb.ca/}, ADDRESS = {Fredericton, New Brunswick, Canada}, MONTH = {May 19}, YEAR = 1998, LENGTH = {1 hour}, PAPERS = {IPPS98; ProtocolsTR; WoTUG20; CCC97} } @InvitedTalk{Dagstuhl98, AUTHOR = {Therese C. Biedl and Prosenjit Bose and Erik D. Demaine and Anna Lubiw}, TITLE = {Efficient Algorithms for Petersen's Matching Theorem}, SERIES = {Seminar on Data Structures}, SERIESURL = {http://www.dagstuhl.de/98091/}, CONFERENCE = {Schloss Dagstuhl}, CONFERENCEURL = {http://www.dagstuhl.de/}, ADDRESS = {Wadern, Germany}, MONTH = {March 2--6}, YEAR = 1998, LENGTH = {45 minutes}, PAPERS = {SODA99b} } @Article{CPE98, AUTHOR = {Erik D. Demaine}, TITLE = {C to Java: Converting Pointers into References}, JOURNAL = {Concurrency: Practice and Experience}, JOURNALURL = {http://www.interscience.wiley.com/jpages/1040-3108/}, VOLUME = 10, NUMBER = {11--13}, YEAR = 1998, PAGES = {851--861}, LENGTH = {11 pages}, PAPERS = {Java98} } @InProceedings{IPPS98, AUTHOR = {Erik D. Demaine}, TITLE = {Protocols for Non-Deterministic Communication over Synchronous Channels}, BOOKTITLE = {Proceedings of the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP'98)}, BOOKURL = {http://www.ippsxx.org/ipps98/}, ADDRESS = {Orlando, Florida}, MONTH = {March 30--April 3}, YEAR = 1998, PAGES = {24--30}, LENGTH = {7 pages; 20 minutes}, PAPERS = {ProtocolsTR} } @InProceedings{Java98, AUTHOR = {Erik D. Demaine}, TITLE = {Converting C Pointers to Java References}, BOOKTITLE = {Proceedings of the ACM 1998 Workshop on Java for High-Performance Network Computing (Java'98)}, BOOKURL = {http://www.cs.ucsb.edu/conferences/java98/}, ADDRESS = {Palo Alto, California}, MONTH = {February 28 and March 1}, YEAR = 1998, LENGTH = {10 pages; 25 minutes}, PAPERS = {CPE98} } @TechReport{ProtocolsTR, AUTHOR = {Erik D. Demaine}, TITLE = {Adaptive Protocols for Negotiating Non-Deterministic Choice over Synchronous Channels}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-97-35}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-97-35/}, MONTH = {September}, YEAR = 1997, LENGTH = {16 pages}, PAPERS = {IPPS98} } @InvitedTalk{AMSMAA98, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Folding and Cutting Paper}, SERIES = {Special Session on Mathematical Methods in Paper Folding}, CONFERENCE = {Joint Mathematics Meetings of the American Mathematical Society and Mathematical Association of American}, ADDRESS = {Baltimore, Maryland}, MONTH = {January 9}, YEAR = 1998, LENGTH = {30 minutes}, WEBPAGES = {foldcut} } @TechReport{ConvexExtremeTR, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Computing Extreme Origami Bases}, INSTITUTION = {Department of Computer Science, University of Waterloo}, INSTITUTIONURL = {http://www.cs.uwaterloo.ca/}, NUMBER = {CS-97-22}, NUMBERURL = {ftp://cs-archive.uwaterloo.ca/cs-archive/CS-97-22/}, MONTH = {May}, YEAR = 1997, LENGTH = {18 pages}, WEBPAGES = {foldcut}, UPDATES = {This work on the fold-and-cut problem has been generalized to arbitrary plane graphs; see my fold-and-cut webpage for links to related papers.

Further updates concerning this technical report:

} } @InvitedTalk{RIT97, AUTHOR = {Erik D. Demaine}, TITLE = {Higher-Order Concurrency in Java}, SERIES = {Colloquia Series}, SERIESURL = {http://www.cs.rit.edu/~spr/clq.html}, INSTITUTION = {Department of Computer Science, Rochester Institute of Technology}, INSTITUTIONURL = {http://www.cs.rit.edu/}, ADDRESS = {Rochester, New York}, MONTH = {September 30}, YEAR = 1997, LENGTH = {1 hour}, PAPERS = {IPPS98; ProtocolsTR; WoTUG20; CCC97} } @InProceedings{HPCS97, AUTHOR = {Erik D. Demaine}, TITLE = {A Threads-Only MPI Implementation for the Development of Parallel Programs}, BOOKTITLE = {Proceedings of the 11th International Symposium on High Performance Computing Systems (HPCS'97)}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {July 10--12}, YEAR = 1997, PAGES = {153--163}, LENGTH = {11 pages; 20 minutes}, SOFTWARE = {TOMPI} } % No longer in service: % BOOKURL = {http://www.cs.umanitoba.ca/~hpcs97/}, @MastersThesis{mthesis, AUTHOR = {Erik D. Demaine}, TITLE = {Efficient Simulation of Message-Passing in Distributed-Memory Architectures}, SCHOOL = {Department of Computer Science, University of Waterloo}, SCHOOLURL = {http://www.cs.uwaterloo.ca/}, YEAR = 1996, LENGTH = {114 pages} } @InProceedings{WoTUG20, AUTHOR = {Erik D. Demaine}, TITLE = {Higher-Order Concurrency in {J}ava}, BOOKTITLE = {Proceedings of the Parallel Programming and Java Conference (WoTUG20)}, BOOKURL = {http://www.rt.el.utwente.nl/wotug20/}, ADDRESS = {Enschede, the Netherlands}, MONTH = {April 12--16}, YEAR = 1997, PAGES = {34--47}, COMMENTS = {Awarded best student paper.}, LENGTH = {14 pages; 45 minutes}, PAPERS = {CCC97; IPPS98; ProtocolsTR} } @InProceedings{CCC97, AUTHOR = {Erik D. Demaine}, TITLE = {Higher-Order Concurrency in {PVM}}, BOOKTITLE = {Proceedings of the Cluster Computing Conference (CCC'97)}, BOOKURL = {http://www.mathcs.emory.edu/~ccc97/sessions.html}, ADDRESS = {Atlanta, Georgia}, MONTH = {March 9--12}, YEAR = 1997, LENGTH = {17 pages; 25 minutes}, PAPERS = {WoTUG20; IPPS98; ProtocolsTR} } @InProceedings{MDC96, AUTHOR = {Erik D. Demaine}, TITLE = {First-Class Communication in {MPI}}, BOOKTITLE = {Proceedings of the 2nd MPI Developer's Conference}, ADDRESS = {Notre Dame, Indiana}, MONTH = {July 1--2}, YEAR = 1996, PAGES = {189--194} } % PUBLISHER = {IEEE Computer Society Press}, @Article{IJCSSE97, AUTHOR = {Erik D. Demaine and Sampalli Srinivas}, TITLE = {Routing Algorithms on Static Interconnection Networks: A Classification Scheme}, JOURNAL = {International Journal of Computer Systems Science and Engineering}, CITY = {London}, VOLUME = 12, NUMBER = 6, MONTH = {November}, YEAR = 1997, PAGES = {359--367} } % PUBLISHER = {CRL Publishing}, @InProceedings{HPCS96, AUTHOR = {Erik D. Demaine}, TITLE = {Evaluating the Performance of Parallel Programs in a Pseudo-Parallel {MPI} Environment}, BOOKTITLE = {Proceedings of the 10th International Symposium on High Performance Computing Systems (HPCS'96)}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {June 5--7}, YEAR = 1996 } % PUBLISHER = {Carleton University Press and Oxford University Press} @Article{IJHSC96, AUTHOR = {Erik D. Demaine and Sampalli Srinivas}, TITLE = {A Novel Routing Algorithm for \emph{k}-ary \emph{n}-cube Interconnection Networks}, JOURNAL = {International Journal of High Speed Computing}, JOURNALURL = {http://www.wspc.com/journals/ijhsc/ijhsc.html}, CITY = {Singapore}, VOLUME = 8, NUMBER = 1, YEAR = 1996, PAGES = {81--92} } % PUBLISHER = {World Scientific Publishing Company}, @InProceedings{HPCS95, AUTHOR = {Erik D. Demaine and Sampalli Srinivas}, TITLE = {Direction-First e-cube: A New Routing Algorithm for \emph{k}-ary \emph{n}-cube Networks}, BOOKTITLE = {Proceedings of the 9th International Symposium on High Performance Computing Systems (HPCS'95)}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {July 10--12}, YEAR = 1995, PAPERS = {IJHSC96} }