% Papers written by Erik D. Demaine % % URL is simply "http://erikdemaine.org/papers/" followed by % the entry name. This directory is created automatically from this file. % The "talks" directory used to have this property too. @Article{NetworkCreationAdvertising_InternetMath, AUTHOR = {Erik D. Demaine and Morteza Zadimoghaddam}, TITLE = {Constant Price of Anarchy in Network-Creation Games via Public-Service Advertising}, JOURNAL = {Internet Mathematics}, YEAR = {to appear}, withstudent = 1, replaces = {NetworkCreationAdvertising_WAW2010}, papers = {NetworkCreationAdvertising_WAW2010}, copyright = {Copyright held by the authors.}, } @InCollection{Balloons_ShapingSpace2, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart}, TITLE = {Balloon Polyhedra}, BOOKTITLE = {Shaping Space: A Polyhedral Approach}, EDITION = {Second}, EDITOR = {Marjorie Senechal and George Fleck}, YEAR = {to appear}, length = {10 pages}, papers = {Balloons_CCCG2008}, category = {art}, } @Article{NetworkCreation_TALG, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Morteza Zadimoghaddam}, TITLE = {The Price of Anarchy in Network Creation Games}, JOURNAL = {ACM Transactions on Algorithms}, journalurl = {http://www.acm.org/talg/}, YEAR = {to appear}, length = {14 pages}, papers = {NetworkCreation_PODC2007; BasicNetworkCreation_SPAA2010; CooperativeNetworkCreation_STACS2009}, replaces = {NetworkCreation_PODC2007}, } @Article{HingedDissections_DCG, AUTHOR = {Timothy G. Abbott and Zachary Abel and David Charlton and Erik D. Demaine and Martin L. Demaine and Scott Duke Kominers}, TITLE = {Hinged Dissections Exist}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, volume = 47, number = 1, year = 2012, pages = {150--186}, comments = {This paper is also available from SpringerLink.}, length = {33 pages}, withstudent = 1, replaces = {HingedDissections_SoCG2008}, papers = {HingedDissections_SoCG2008} } @article{KConvex_CGTA, AUTHOR = {Oswin Aichholzer and Franz Aurenhammer and Erik D. Demaine and Ferran Hurtado and Pedro Ramos and Jorge Urrutia}, TITLE = {On $k$-convex polygons}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 45, NUMBER = 3, YEAR = 2012, PAGES = {73--87}, comments = {This paper is also available from ScienceDirect.}, } @InProceedings{PictureHanging_FUN2012, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Yair N. Minsky and Joseph S. B. Mitchell and Ronald L. Rivest and Mihai P\v{a}tra\c{s}cu}, TITLE = {Picture-Hanging Puzzles}, BOOKTITLE = {Proceedings of the 6th International Conference on Fun with Algorithms (FUN 2012)}, bookurl = {http://www.dsi.unive.it/~fun2012/}, ADDRESS = {Venice, Italy}, MONTH = {June 4--6}, YEAR = 2012, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, PAGES = {81--93}, length = {12 pages}, copyright = {Copyright held by the authors.}, comments = {The full paper is available as arXiv.org:1203.3602 of the Computing Research Repository (CoRR).}, } @Article{StackMST_Algorithmica, AUTHOR = {Jean Cardinal and Erik D. Demaine and Samuel Fiorini and Gwena\"el Joret and Stefan Langerman and Ilan Newman and Oren Weimann}, TITLE = {The Stackelberg Minimum Spanning Tree Game}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 59, NUMBER = 2, YEAR = 2011, PAGES = {129--144}, length = {17 pages}, withstudent = 1, papers = {StackMST_WADS2007; StackMST_WINE2009}, comments = {This paper is also available from SpringerLink.}, } @article{Outliers_CGTA, AUTHOR = {Hee-Kap Ahn and Sang Won Bae and Erik D. Demaine and Martin L. Demaine and Sang-Sub Kim and Matias Korman and Iris Reinbacher and Wanbin Son}, TITLE = {Covering points by disjoint boxes with outliers}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 44, NUMBER = 3, YEAR = 2011, PAGES = {178--190}, comments = {This paper is also available from ScienceDirect.}, } @Article{NPReconfiguration_TCS, AUTHOR = {Takehiro Ito and Erik D. Demaine and Nicholas J. A. Harvey and Christos H. Papadimitriou and Martha Sideri and Ryuhei Uehara and Yushi Uno}, TITLE = {On the Complexity of Reconfiguration Problems}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://www.elsevier.nl/locate/tcs}, VOLUME = {412}, NUMBER = {12-14}, YEAR = {2011}, PAGES = {1054--1065}, length = {12 pages}, comments = {This paper is also available from ScienceDirect.}, replaces = {NPReconfiguration_ISAAC2008}, papers = {NPReconfiguration_ISAAC2008; NPReconfiguration_WADS2009}, } @Article{PermutingPolygons_IJCGA, 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}, JOURNAL = {International Journal of Computational Geometry and Applications}, journalurl = {http://www.worldscinet.com/ijcga/ijcga.shtml}, VOLUME = 21, NUMBER = 1, YEAR = 2011, PAGES = {87--100}, comments = {This paper is also available from WorldSciNet.}, replaces = {PermutingPolygons_CCCG2002}, papers = {PermutingPolygons_CCCG2002}, } @article{Moteins_TRO, AUTHOR = {Kenneth C. Cheung and Erik D. Demaine and Jonathan Bachrach and Saul Griffith}, TITLE = {Programmable Assembly With Universally Foldable Strings (Moteins)}, JOURNAL = {IEEE Transactions on Robotics}, VOLUME = 27, NUMBER = 4, YEAR = 2011, PAGES = {718--729}, comments = {This paper is also available from IEEE Xplore.}, withstudent = 1, } @Article{PleatFolding_GC, AUTHOR = {Jean Cardinal and Erik D. Demaine and Martin L. Demaine and Shinji Imahori and Tsuyoshi Ito and Masashi Kiyomi and Stefan Langerman and Ryuhei Uehara and Takeaki Uno}, TITLE = {Algorithmic Folding Complexity}, JOURNAL = {Graphs and Combinatorics}, journalurl = {http://www.springer.com/mathematics/numbers/journal/373}, VOLUME = 27, NUMBER = 3, YEAR = 2011, PAGES = {341--351}, papers = {PleatFolding_ISAAC2009; PleatFolding_JCCGG2009}, replaces = {PleatFolding_ISAAC2009}, comments = {This paper is also available from SpringerLink.} } @Article{Blooming_GC, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart and John Iacono and Stefan Langerman and Joseph O'Rourke}, TITLE = {Continuous Blooming of Convex Polyhedra}, JOURNAL = {Graphs and Combinatorics}, journalurl = {http://www.springer.com/mathematics/numbers/journal/373}, VOLUME = 27, NUMBER = 3, YEAR = 2011, PAGES = {363--376}, replaces = {Blooming_JCCGG2009}, papers = {Blooming_JCCGG2009}, length = {13 pages}, comments = {The paper is also available as arXiv:0906.2461 and from SpringerLink.}, } @Article{Hypar_GC, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart and Gregory N. Price and Tomohiro Tachi}, TITLE = {(Non)existence of Pleated Folds: How Paper Folds Between Creases}, JOURNAL = {Graphs and Combinatorics}, journalurl = {http://www.springer.com/mathematics/numbers/journal/373}, VOLUME = 27, NUMBER = 3, YEAR = 2011, PAGES = {377--397}, length = {16 pages}, papers = {Hypar_JCCGG2009}, replaces = {Hypar_JCCGG2009}, comments = {This paper is also available as arXiv:0906.4747 and from SpringerLink.}, withstudent = 1, } @Article{Crystalline_Robotica, AUTHOR = {Greg Aloupis and S\'ebastien Collette and Mirela Damian and Erik D. Demaine and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Val Pinciu and Suneeta Ramaswami and Vera Sacrist\'an and Stefanie Wuhrer}, TITLE = {Efficient constant-velocity reconfiguration of crystalline robots}, JOURNAL = {Robotica}, VOLUME = 29, NUMBER = 1, YEAR = 2011, PAGES = {59--71}, NOTE = {Special issue on Robotic Self-X Systems.}, comments = {This paper is also available from Cambridge Journals Online.} } @Article{Matter_Robotica, AUTHOR = {Byoungkwon An and Nadia Benbernou and Erik D. Demaine and Daniela Rus}, TITLE = {Planning to Fold Multiple Objects from a Single Self-Folding Sheet}, JOURNAL = {Robotica}, journalurl = {http://journals.cambridge.org/action/displayJournal?jid=ROB}, VOLUME = 29, NUMBER = 1, YEAR = 2011, PAGES = {87--102}, NOTE = {Special issue on Robotic Self-X Systems.}, withstudent = 1, length = {29 pages}, comments = {This paper is also available from Cambridge Journals Online.} } @InProceedings{LinearEquilateral_ISAAC2011, AUTHOR = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Jayson Lynch and Tao B. Schardl and Isaac Shapiro-Ellowitz}, TITLE = {Folding Equilateral Plane Graphs}, BOOKTITLE = {Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011)}, bookurl = {http://www.is.titech.ac.jp/isaac11/}, MONTH = {December 5--8}, YEAR = 2011, PAGES = {574--583}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 7074, withstudent = 1, comments = {This paper is also available from SpringerLink.} } @InProceedings{CurvedCrease_IASS2011, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Duks Koschitz and Tomohiro Tachi}, TITLE = {Curved Crease Folding: a Review on Art, Design and Mathematics}, BOOKTITLE = {Proceedings of the IABSE-IASS Symposium: Taller, Longer, Lighter (IABSE-IASS 2011)}, bookurl = {http://www.iabse-iass-2011.com/}, ADDRESS = {London, England}, MONTH = {September 20--23}, YEAR = 2011, PAGES = {to appear}, length = {8 pages}, withstudent = 1, } @InProceedings{Staged1D_DNA2011, AUTHOR = {Erik D. Demaine and Sarah Eisenstat and Mashhood Ishaque and Andrew Winslow}, TITLE = {One-Dimensional Staged Self-Assembly}, BOOKTITLE = {Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA 2011)}, bookurl = {http://dna17.caltech.edu/}, ADDRESS = {Pasadena, California}, MONTH = {September 19--23}, YEAR = 2011, PAGES = {100--114}, VOLUME = 6937, SERIES = {Lecture Notes in Computer Science}, withstudent = 1, comments = {This paper is also available from SpringerLink.} } @Patent{RALA_patent, AUTHOR = {David Allen Dalrymple and Erik Demaine and Neil Gershenfeld and Forrest Green and Ara Knaian}, TITLE = {Reconfigurable Logic Automata}, NUMBER = {US 8,013,629 B2}, MONTH = {September 6}, YEAR = 2011, } @InProceedings{Rubik_ESA2011, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Anna Lubiw and Andrew Winslow}, TITLE = {Algorithms for Solving Rubik's Cubes}, BOOKTITLE = {Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011)}, bookurl = {https://algo2011.mpi-inf.mpg.de/}, MONTH = {September 5--9}, YEAR = 2011, PAGES = {689--700}, withstudent = 1, comments = {The full paper is available as arXiv:1106.5736 of the Computing Research Repository (CoRR).} } @InProceedings{Movement_APPROX2011, AUTHOR = {Piotr Berman and Erik D. Demaine and Morteza Zadimoghaddam}, TITLE = {{$O(1)$}-Approximations for Maximum Movement Problems}, BOOKTITLE = {Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2011)}, bookurl = {http://cui.unige.ch/tcs/random-approx/2011/index.php}, ADDRESS = {Princeton, New Jersey}, MONTH = {August 17--19}, YEAR = 2011, PAGES = {62--74}, length = {12 pages}, withstudent = 1, comments = {This paper is also available from SpringerLink.}, } @InProceedings{FaultTolerant_WADS2011, AUTHOR = {Paul Christiano and Erik D. Demaine and Shaunak Kishore}, TITLE = {Lossless Fault-Tolerant Data Structures with Additive Overhead}, BOOKTITLE = {Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011)}, bookurl = {http://www.wads.org/}, ADDRESS = {Brooklyn, New York}, MONTH = {August 15-17}, YEAR = 2011, PAGES = {243--254}, length = {12 pages}, withstudent = 1, } @InProceedings{FixedAngle_WADS2011, AUTHOR = {Erik D. Demaine and Sarah Eisenstat}, TITLE = {Flattening Fixed-Angle Chains Is Strongly {NP}-Hard}, BOOKTITLE = {Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011)}, bookurl = {http://www.wads.org/}, ADDRESS = {Brooklyn, New York}, MONTH = {August 15-17}, YEAR = 2011, PAGES = {314--325}, length = {12 pages}, withstudent = 1, } @InProceedings{CCCG2010Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2010}, BOOKTITLE = {Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)}, bookurl = {http://2011.cccg.ca/}, ADDRESS = {Toronto, Ontario, Canada}, MONTH = {August 10--12}, YEAR = 2011, PAGES = {to appear}, papers = {CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, length = {4 pages}, unrefereed = 1, } @InProceedings{WordSep_DFCS2011, AUTHOR = {Erik D. Demaine and Sarah Eisenstat and Jeffrey Shallit and David A. Wilson}, TITLE = {Remarks on Separating Words}, BOOKTITLE = {Proceedings of the 13th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2011)}, bookurl = {http://www.informatik.uni-giessen.de/dcfs2011/}, ADDRESS = {Giessen, Germany}, MONTH = {July 25--27}, YEAR = 2011, PAGES = {147--157}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 6808, length = {12 pages}, withstudent = 1, comments = {This paper is also available as arXiv:1103.4513 of the Computing Research Repository (CoRR). and from SpringerLink.}, } @InProceedings{SunUnfolding_EGC2011, AUTHOR = {Erik D. Demaine and Anna Lubiw}, TITLE = {A generalization of the source unfolding of convex polyhedra}, BOOKTITLE = {Proceedings of the 14th Spanish Meeting on Computational Geometry (EGC 2011)}, bookurl = {http://www2.uah.es/egc2011/}, ADDRESS = {Alcal\'a de Henares, Spain}, MONTH = {June 27--30}, YEAR = 2011, PAGES = {91--94}, unrefereed = 1, } @InProceedings{FeatureSize_EGC2011, AUTHOR = {Greg Aloupis and Erik D. Demaine and Martin L. Demaine and Vida Dujmovi\'c and John Iacono}, TITLE = {Meshes preserving minimum feature size}, BOOKTITLE = {Proceedings of the 14th Spanish Meeting on Computational Geometry (EGC 2011)}, bookurl = {http://www2.uah.es/egc2011/}, ADDRESS = {Alcal\'a de Henares, Spain}, MONTH = {June 27--30}, YEAR = 2011, PAGES = {205--208}, unrefereed = 1, } @InProceedings{ContractionMinorFree_STOC2011, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Contraction Decomposition in $H$-Minor-Free Graphs and Algorithmic Applications}, BOOKTITLE = {Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011)}, bookurl = {http://www2.research.att.com/~dsj/stoc11/stoc11.html}, MONTH = {June 6--8}, YEAR = 2011, PAGES = {441--450}, length = {10 pages}, } @InProceedings{RNAAssembly_STACS2011, AUTHOR = {Erik D. Demaine and Matthew J. Patitz and Robert T. Schweller and Scott M. Summers}, TITLE = {Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the {K}olmogorov Bound with Small Scale Factor}, BOOKTITLE = {Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, bookurl = {http://www.stacs2011.de/}, ADDRESS = {Dortmund, Germany}, MONTH = {March 10--12}, YEAR = 2011, PAGES = {201--212}, comments = {The full paper is available as arXiv.org:1004.4383 of the Computing Research Repository (CoRR).}, copyright = {Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.}, } @Article{MinAvgDistance_CGTA, AUTHOR = {Erik D. Demaine and S{\'a}ndor P. Fekete and G{\"u}nter Rote and Nils Schweer and Daria Schymura and Mariano Zelke}, TITLE = {Integer Point Sets Minimizing Average Pairwise $L_1$ Distance: What is the Optimal Shape of a Town?}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 44, NUMBER = 2, MONTH = {February}, YEAR = 2011, PAGES = {82--94}, length = {26 pages}, comments = {This paper is also available from ScienceDirect.}, replaces = {MinAvgDistance_CCCG2009}, papers = {MinAvgDistance_CCCG2009; MinAvgDistance_Algorithmica; MinAvgDistance_JPhysA}, } @InProceedings{StackedPolytopes_SODA2011, AUTHOR = {Erik D. Demaine and Andr\'e Schulz}, TITLE = {Embedding Stacked Polytopes on a Polynomial-Size Grid}, BOOKTITLE = {Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)}, bookurl = {http://www.siam.org/meetings/da11/}, ADDRESS = {San Francisco, California, USA}, MONTH = {January 22--25}, YEAR = 2011, PAGES = {1177--1187}, length = {11 pages}, comments = {This paper is also available from SIAM.}, } @Article{ConfluentTries_Algorithmica, AUTHOR = {Erik D. Demaine and Stefan Langerman and Eric Price}, TITLE = {Confluently Persistent Tries for Efficient Version Control}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 57, NUMBER = 3, YEAR = 2010, PAGES = {462--483}, NOTE = {Special issue of selected papers from 11th Scandinavian Workshop on Algorithm Theory, 2008.}, length = {18 pages}, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, papers = {ConfluentTries_SWAT2008}, withstudent = 1, } @Article{ContractionTSP_Combinatorica, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Bojan Mohar}, TITLE = {Approximation Algorithms via Contraction Decomposition}, JOURNAL = {Combinatorica}, journalurl = {http://www.springerlink.com/content/1439-6912/}, VOLUME = 30, NUMBER = 5, YEAR = 2010, PAGES = {533--552}, length = {15 pages}, papers = {ContractionTSP_SODA2007}, replaces = {ContractionTSP_SODA2007}, copyright = {Copyright held by the authors.}, } @Article{LockedShapes_DCG, AUTHOR = {Robert Connelly and Erik D. Demaine and Martin L. Demaine and S\'andor Fekete and Stefan Langerman and Joseph S. B. Mitchell and Ares Rib\'o and G\"unter Rote}, TITLE = {Locked and Unlocked Chains of Planar Shapes}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 44, NUMBER = 2, YEAR = 2010, PAGES = {439--462}, length = {23 pages}, comments = {This paper is also available as arXiv:cs.CG/0604022 of the Computing Research Repository (CoRR). and from SpringerLink.}, papers = {LockedShapes_SoCG2006}, replaces = {LockedShapes_SoCG2006}, } @InProceedings{Transmitters_COCOA2010, AUTHOR = {Brad Ballinger and Nadia Benbernou and Prosenjit Bose and Mirela Damian and Erik D. Demaine and Vida Dujmovi{\'c} and Robin Flatland and Ferran Hurtado and John Iacono and Anna Lubiw and Pat Morin and Vera Sacrist{\'a}n and Diane Souvaine and Ryuhei Uehara}, TITLE = {Coverage with $k$-Transmitters in the Presence of Obstacles}, BOOKTITLE = {Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010)}, bookurl = {http://theory.utdallas.edu/COCOA2010/}, ADDRESS = {The Big Island, Hawaii, USA}, MONTH = {December 18--20}, YEAR = 2010, PAGES = {627--652}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 6509, withstudent = 1, comments = {This paper is also available from SpringerLink.}, } @InProceedings{NetworkCreationAdvertising_WAW2010, AUTHOR = {Erik D. Demaine and Morteza Zadimoghaddam}, TITLE = {Constant Price of Anarchy in Network Creation Games via Public Service Advertising}, BOOKTITLE = {Proceedings of the 7th International Workshop on Algorithms and Models for the Web-Graph (WAW 2010)}, bookurl = {http://www.stanford.edu/group/waw/}, EDITOR = {Ravi Kumar and Dandapani Sivakumar}, VOLUME = 6516, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Stanford, California, USA}, MONTH = {December 13--14}, YEAR = 2010, PAGES = {122--131}, withstudent = 1, comments = {This paper is also available from SpringerLink.}, papers = {NetworkCreationAdvertising_InternetMath}, } @InProceedings{SimpleFoldCut_CGGA2010full, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Andrea Hawksley and Hiro Ito and Po-Ru Loh and Shelly Manber and Omari Stephens}, TITLE = {Making Polygons by Simple Folds and One Straight Cut}, BOOKTITLE = {Revised Papers from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010)}, bookurl = {http://www.dlmu.edu.cn/cgga2010/}, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Dalian, China}, MONTH = {November 3--6}, YEAR = 2010, PAGES = {27--43}, length = {17 pages}, withstudent = 1, replaces = {SimpleFoldCut_CGGA2010}, papers = {SimpleFoldCut_CGGA2010}, } @InProceedings{SimpleFoldCut_CGGA2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Andrea Hawksley and Hiro Ito and Po-Ru Loh and Shelly Manber and Omari Stephens}, TITLE = {Making Polygons by Simple Folds and One Straight Cut}, BOOKTITLE = {Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010)}, bookurl = {http://www.dlmu.edu.cn/cgga2010/}, ADDRESS = {Dalian, China}, MONTH = {November 3--6}, YEAR = 2010, PAGES = {to appear}, unrefereed = 1, paperkind = {abstract}, withstudent = 1, papers = {SimpleFoldCut_CGGA2010full}, } @InProceedings{Cubigami_CGGA2010full, AUTHOR = {Greg Aloupis and Prosenjit K. Bose and Sebastien Collette and Erik D. Demaine and Martin L. Demaine and Karim Douieb and Vida Dujmovi\'c and John Iacono and Stefan Langerman and Pat Morin}, TITLE = {Common Unfoldings of Polyominoes and Polycube}, BOOKTITLE = {Revised Papers from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010)}, bookurl = {http://www.dlmu.edu.cn/cgga2010/}, VOLUME = 7033, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Dalian, China}, MONTH = {November 3--6}, YEAR = 2010, PAGES = {44--54}, length = {11 pages}, withstudent = 1, replaces = {Cubigami_CGGA2010}, papers = {Cubigami_CGGA2010}, } @InProceedings{Cubigami_CGGA2010, AUTHOR = {Greg Aloupis and Prosenjit K. Bose and Sebastien Collette and Erik D. Demaine and Martin L. Demaine and Karim Douieb and Vida Dujmovi\'c and John Iacono and Stefan Langerman and Pat Morin}, TITLE = {Common Unfoldings of Polyominoes and Polycube}, BOOKTITLE = {Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010)}, bookurl = {http://www.dlmu.edu.cn/cgga2010/}, ADDRESS = {Dalian, China}, MONTH = {November 3--6}, YEAR = 2010, PAGES = {to appear}, unrefereed = 1, paperkind = {abstract}, withstudent = 1, papers = {Cubigami_CGGA2010full}, } @Article{Orthoballs_IJCGA, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Grid Vertex-Unfolding Orthostacks}, JOURNAL = {International Journal of Computational Geometry and Applications}, journalurl = {http://www.worldscinet.com/ijcga/ijcga.shtml}, VOLUME = 20, NUMBER = 3, YEAR = 2010, PAGES = {245--254}, comments = {This paper is also available from WorldSciNet.}, length = {10 pages}, papers = {Orthoballs_JCDCG2004}, replaces = {Orthoballs_JCDCG2004}, } @Article{Gardner_AmericanScientist2010, AUTHOR = {Erik D. Demaine}, TITLE = {Recreational Computing: Puzzles and tricks from Martin Gardner inspire math and science}, JOURNAL = {American Scientist}, journalurl = {http://www.americanscientist.org/}, VOLUME = 98, NUMBER = 6, PAGES = {452--456}, MONTH = {November--December}, YEAR = {2010}, length = {5 pages}, unrefereed = 1, comments = {The paper is also avilable from American Scientist.}, category = {art}, } @InProceedings{InterlockedPolygons_CCCG2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara}, TITLE = {Any Monotone {B}oolean Function Can Be Realized by Interlocked Polygons}, BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)}, bookurl = {http://www.cs.umanitoba.ca/~cccg2010/}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {August 9--11}, YEAR = 2010, PAGES = {139--142}, length = {4 pages}, unrefereed = 1, webpages = {interlockedpolygons} } @InProceedings{GhostChimneys_CCCG2010, AUTHOR = {David Charlton and Erik D. Demaine and Martin L. Demaine and Vida Dujmovi\'c and Pat Morin and Ryuhei Uehara}, TITLE = {Ghost Chimneys}, BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)}, bookurl = {http://www.cs.umanitoba.ca/~cccg2010/}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {August 9--11}, YEAR = 2010, PAGES = {63--66}, length = {5 pages}, unrefereed = 1, comments = {The 4-page version appeared in the printed proceedings.} } @InProceedings{Zippers_CCCG2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Anna Lubiw and Arlo Shallit and Jonah L. Shallit}, TITLE = {Zipper Unfoldings of Polyhedral Complexes}, BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)}, bookurl = {http://www.cs.umanitoba.ca/~cccg2010/}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {August 9--11}, YEAR = 2010, PAGES = {219--222}, length = {5 pages}, unrefereed = 1, comments = {The 4-page version appeared in the printed proceedings.}, webpages = {zippers}, } @InProceedings{Polyhedronization_CCCG2010, AUTHOR = {Gill Barequet and Nadia Benbernou and David Charlton and Erik D. Demaine and Martin L. Demaine and Mashhood Ishaque and Anna Lubiw and Andr\'e Schulz and Diane L. Souvaine and Godfried T. Toussaint and Andrew Winslow}, TITLE = {Bounded-Degree Polyhedronization of Point Sets}, BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)}, bookurl = {http://www.cs.umanitoba.ca/~cccg2010/}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {August 9--11}, YEAR = 2010, PAGES = {99--102}, length = {4 pages}, unrefereed = 1, } @InProceedings{CCCG2009Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2009}, BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010)}, bookurl = {http://www.cs.umanitoba.ca/~cccg2010/}, ADDRESS = {Winnipeg, Manitoba, Canada}, MONTH = {August 9--11}, YEAR = 2010, PAGES = {83--86}, papers = {CCCG2010Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, length = {4 pages}, unrefereed = 1, } @InCollection{Huffman_Origami5, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Duks Koschitz}, TITLE = {Reconstructing David Huffman's Legacy in Curved-Crease Folding}, BOOKTITLE = {Origami$^5$: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {39--52}, PUBLISHER = {A K Peters}, length = {17 pages}, withstudent = 1, papers = {Huffman_OSME2010}, replaces = {Huffman_OSME2010}, category = {art}, } @InCollection{MazeFolding_Origami5, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Jason Ku}, TITLE = {Folding Any Orthogonal Maze}, BOOKTITLE = {Origami$^5$: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {449--454}, PUBLISHER = {A K Peters}, webpages = {fonts/maze}, replaces = {MazeFolding_OSME2010}, papers = {MazeFolding_OSME2010; MazeAlphabet_G4G9}, withstudent = 1, } @InCollection{DiskPacking_Origami5, AUTHOR = {Erik D. Demaine and S\'andor P. Fekete and Robert J. Lang}, TITLE = {Circle Packing for Origami Design Is Hard}, BOOKTITLE = {Origami$^5$: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {609--626}, PUBLISHER = {A K Peters}, length = {18 pages}, replaces = {DiskPacking_OSME2010}, papers = {DiskPacking_OSME2010}, comments = {This paper is also available as arXiv:1008.1224 of the Computing Research Repository (CoRR).} } @InCollection{BoxPleating_Origami5, AUTHOR = {Nadia M. Benbernou and Erik D. Demaine and Martin L. Demaine and Aviv Ovadya}, TITLE = {Universal Hinge Patterns to Fold Orthogonal Shapes}, BOOKTITLE = {Origami$^5$: Proceedings of the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {405--420}, PUBLISHER = {A K Peters}, withstudent = 1, replaces = {BoxPleating_OSME2010}, papers = {BoxPleating_OSME2010}, comments = {This paper is also available as arXiv:0909.5388 of the Computing Research Repository (CoRR).} } @InProceedings{BoxPleating_OSME2010, AUTHOR = {Nadia M. Benbernou and Erik D. Demaine and Martin L. Demaine and Aviv Ovadya}, TITLE = {Universal Hinge Patterns to Fold Orthogonal Shapes}, BOOKTITLE = {Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {to appear}, unrefereed = 1, withstudent = 1, length = {1 page}, paperkind = {abstract}, papers = {BoxPleating_Origami5}, comments = {The full paper is available as arXiv:0909.5388 of the Computing Research Repository (CoRR).} } @InProceedings{MazeFolding_OSME2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Jason Ku}, TITLE = {Folding Any Orthogonal Maze}, BOOKTITLE = {Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {to appear}, length = {1 page}, paperkind = {abstract}, unrefereed = 1, withstudent = 1, webpages = {fonts/maze}, papers = {MazeFolding_Origami5; MazeAlphabet_G4G9}, } @InProceedings{Huffman_OSME2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Duks Koschitz}, TITLE = {Reconstructing David Huffman's Legacy in Curved-Crease Folding}, BOOKTITLE = {Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {to appear}, length = {1 page}, paperkind = {abstract}, unrefereed = 1, withstudent = 1, papers = {Huffman_Origami5}, category = {art}, } @InProceedings{AngularGrid_OSME2010, AUTHOR = {Tomohiro Tachi and Erik D. Demaine}, TITLE = {Degenerative Coordinates in 22.5$^\circ$ Grid System}, BOOKTITLE = {Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {to appear}, length = {1 page}, paperkind = {abstract}, unrefereed = 1, } @InProceedings{DiskPacking_OSME2010, AUTHOR = {Erik D. Demaine and S\'andor P. Fekete and Robert J. Lang}, TITLE = {On the Complexity of Origami Design}, BOOKTITLE = {Abstracts from the 5th International Conference on Origami in Science, Mathematics and Education (OSME 2010)}, bookurl = {http://www.origami-usa.org/5osme}, ADDRESS = {Singapore}, MONTH = {July 13--17}, YEAR = 2010, PAGES = {to appear}, length = {1 page}, paperkind = {abstract}, unrefereed = 1, papers = {DiskPacking_Origami5} } @Article{Matter_PNAS, AUTHOR = {E. Hawkes and B. An and N. M. Benbernou and H. Tanaka and S. Kim and E. D. Demaine and D. Rus and R. J. Wood}, TITLE = {Programmable matter by folding}, JOURNAL = {Proceedings of the National Academy of Sciences of the United States of America}, journalurl = {http://www.pnas.org/}, VOLUME = 107, NUMBER = 28, YEAR = 2010, PAGES = {12441--12445}, length = {5 pages}, withstudent = 1, comments = {This paper is also available from PNAS.

See the supporting video. Embedded version with voiceover by Erik Demaine:

}, } @InProceedings{Shortcuts_SWAT2010, AUTHOR = {Erik D. Demaine and Morteza Zadimoghaddam}, TITLE = {Minimizing the Diameter of a Network using Shortcut Edges}, BOOKTITLE = {Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010)}, bookurl = {http://org.uib.no/swat2010/}, ADDRESS = {Bergen, Norway}, MONTH = {June 21--23}, YEAR = 2010, PAGES = {420--431}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 6139, length = {12 pages}, copyright = {Copyright held by the authors.}, withstudent = 1, comments = {This paper is also available from SpringerLink.}, } @InProceedings{BasicNetworkCreation_SPAA2010, AUTHOR = {Noga Alon and Erik D. Demaine and MohammadTaghi Hajiaghayi and Tom Leighton}, TITLE = {Basic Network Creation Games}, BOOKTITLE = {Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010)}, bookurl = {http://www.cs.jhu.edu/~spaa/2010/}, ADDRESS = {Santorini, Greece}, MONTH = {June 13--15}, YEAR = 2010, PAGES = {21--29}, length = {8 pages}, papers = {CooperativeNetworkCreation_SIGecom; NetworkCreation_TALG}, withstudent = 1, comments = {This paper is also available from the ACM Digital Library.}, } @InProceedings{SubmodularGapScheduling_SPAA2010, AUTHOR = {Erik D. Demaine and Morteza Zadimoghaddam}, TITLE = {Scheduling to Minimize Power Consumption using Submodular Functions}, BOOKTITLE = {Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010)}, bookurl = {http://www.cs.jhu.edu/~spaa/2010/}, ADDRESS = {Santorini, Greece}, MONTH = {June 13--15}, YEAR = 2010, PAGES = {420--431}, papers = {GapScheduling_SPAA2007}, withstudent = 1, comments = {This paper is also available from the ACM Digital Library.}, } @InProceedings{Kaboozle_FUN2010, AUTHOR = {Tetsuo Asano and Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara}, TITLE = {Kaboozle is {NP}-complete, even in a Strip}, BOOKTITLE = {Proceedings of the 5th International Conference on Fun with Algorithms (FUN 2010)}, bookurl = {http://fun2010.dia.unisa.it/}, VOLUME = 6099, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Ischia, Italy}, MONTH = {June 2--4}, YEAR = 2010, PAGES = {28--36}, length = {9 pages}, } @InProceedings{Uno_FUN2010, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Ryuhei Uehara and Takeaki Uno and Yushi Uno}, TITLE = {{UNO} is hard, even for a single player}, BOOKTITLE = {Proceedings of the 5th International Conference on Fun with Algorithms (FUN 2010)}, bookurl = {http://fun2010.dia.unisa.it/}, VOLUME = 6099, SERIES = {Lecture Notes in Computer Science}, ADDRESS = {Ischia, Italy}, MONTH = {June 2--4}, YEAR = 2010, PAGES = {133--144}, length = {12 pages}, comments = {The full paper is available as arXiv:1003.2851.} } @InProceedings{MatchingPoints_LATIN2010, AUTHOR = {Greg Aloupis and Jean Cardinal and S{\'e}bastien Collette and Erik D. Demaine and Martin L. Demaine and Muriel Dulieu and Ruy Fabila-Monroy and Vi Hart and Ferran Hurtado and Stefan Langerman and Maria Saumell and Carlos Seara and Perouz Taslakian}, TITLE = {Matching Points with Things}, BOOKTITLE = {Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN 2010)}, bookurl = {http://www.cs.uwaterloo.ca/conferences/latin2010/}, ADDRESS = {Oaxaca, Mexico}, MONTH = {April 19--23}, YEAR = 2010, PAGES = {to appear}, length = {12 pages}, replaces = {MatchingPoints_JCCGG2009}, papers = {MatchingPoints_JCCGG2009}, } @InCollection{ConveyerAlphabet_Elasticity, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Bel\'en Palop}, TITLE = {Conveyer-Belt Alphabet}, BOOKTITLE = {Findings in Elasticity}, bookurl = {http://www.lars-mueller-publishers.com/en/catalogue-art/findings-on-elasticity}, EDITOR = {Hester Aardse and Astrid van Baalen}, PUBLISHER = {Pars Foundation, Lars M\"uller Publishers}, MONTH = {April}, YEAR = 2010, PAGES = {86--89}, unrefereed = 1, papers = {ConveyerAlphabet_G4G9}, webpages = {fonts/conveyer}, category = {art}, } @InCollection{ConveyerAlphabet_G4G9, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Bel\'en Palop}, TITLE = {Conveyer Belt Puzzle Font}, BOOKTITLE = {Exchange Book of the 9th Gathering for Gardner (G4G9)}, bookurl = {http://www.g4g4.com/}, ADDRESS = {Atlanta, Georgia}, MONTH = {March 24--28}, YEAR = 2010, PAGES = {to appear}, unrefereed = 1, length = {4 pages}, papers = {ConveyerAlphabet_Elasticity}, webpages = {fonts/conveyer}, category = {art}, } @InCollection{MazeAlphabet_G4G9, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Jason Ku}, TITLE = {Origami Maze Puzzle Font}, BOOKTITLE = {Exchange Book of the 9th Gathering for Gardner (G4G9)}, bookurl = {http://www.g4g4.com/}, ADDRESS = {Atlanta, Georgia}, MONTH = {March 24--28}, YEAR = 2010, PAGES = {to appear}, unrefereed = 1, length = {4 pages}, papers = {MazeFolding_OSME2010}, webpages = {fonts/maze}, withstudent = 1, category = {art}, } @Article{Sensor_TON, AUTHOR = {Jonathan L. Bredin and Erik D. Demaine and MohammadTaghi Hajiaghayi and Daniela Rus}, TITLE = {Deploying Sensor Networks with Guaranteed Fault Tolerance}, JOURNAL = {IEEE/ACM Transactions on Networking}, journalurl = {http://www.ton.cs.umass.edu/}, VOLUME = 18, NUMBER = 1, MONTH = {February}, YEAR = 2010, PAGES = {216--228}, length = {14 pages}, papers = {Sensor_MOBIHOC2005}, comments = {This paper is also available from the ACM Digital Library.}, } @InProceedings{RALA_POPL2010, AUTHOR = {Neil Gershenfeld and David Dalrymple and Kailiang Chen and Ara Knaian and Forrest Green and Erik D. Demaine and Scott Greenwald and Peter Schmidt-Nielsen}, TITLE = {Reconfigurable Asynchronous Logic Automata}, BOOKTITLE = {Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010)}, bookurl = {http://www.cse.psu.edu/popl/10/index.html}, ADDRESS = {Madrid, Spain}, MONTH = {January 17--23}, YEAR = 2010, PAGES = {1--6}, length = {6 pages}, unrefereed = 1 } @InProceedings{Replication_SODA2010, AUTHOR = {Zachary Abel and Nadia Benbernou and Mirela Damian and Erik D. Demaine and Martin L. Demaine and Robin Flatland and Scott Kominers and Robert Schweller}, TITLE = {Shape Replication Through Self-Assembly and {RNase} Enzymes}, BOOKTITLE = {Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)}, bookurl = {http://www.siam.org/meetings/da10/}, ADDRESS = {Austin, Texas}, MONTH = {January 17--19}, YEAR = 2010, PAGES = {1045--1064}, withstudent = 1 } @InProceedings{CacheTradeoff_SODA2010, AUTHOR = {Gerth St{\o}lting Brodal and Erik D. Demaine and Jeremy T. Fineman and John Iacono and Stefan Langerman and J. Ian Munro}, TITLE = {Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff}, BOOKTITLE = {Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)}, bookurl = {http://www.siam.org/meetings/da10/}, ADDRESS = {Austin, Texas}, MONTH = {January 17--19}, YEAR = 2010, PAGES = {1448--1456}, withstudent = 1 } @InProceedings{OddMinorFree_SODA2010, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs}, BOOKTITLE = {Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)}, bookurl = {http://www.siam.org/meetings/da10/}, ADDRESS = {Austin, Texas}, MONTH = {January 17--19}, YEAR = 2010, PAGES = {329--344} } @Article{DForms_DCG, AUTHOR = {Erik D. Demaine and Gregory N. Price}, TITLE = {Generalized {D}-Forms Have No Spurious Creases}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 43, NUMBER = 1, PAGES = {179--186}, YEAR = 2009, withstudent = 1, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, } @Article{SphereWrapping_CGTA, AUTHOR = {Erik D. Demaine and Martin L. Demaine and John Iacono and Stefan Langerman}, TITLE = {Wrapping Spheres with Flat Paper}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 42, NUMBER = 8, YEAR = 2009, PAGES = {748--757}, NOTE = {Special issue of selected papers from the 20th European Workshop on Computational Geometry, 2007.}, comments = {This paper is also available from ScienceDirect.}, papers = {SphereWrapping_EuroCG2007}, length = {14 pages}, } @Misc{DagstuhlFPT2009Open, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'aniel Marx}, TITLE = {Open Problems from Dagstuhl Seminar 09511: Parameterized Complexity and Approximation Algorithms}, HOWPUBLISHED = {Manuscript}, MONTH = {December}, YEAR = 2009, unrefereed = 1, length = {10 pages}, } @InCollection{AlgGameTheory_GONC3, AUTHOR = {Erik D. Demaine and Robert A. Hearn}, TITLE = {Playing Games with Algorithms: Algorithmic Combinatorial Game Theory}, BOOKTITLE = {Games of No Chance 3}, EDITOR = {Michael H. Albert and Richard J. Nowakowski}, SERIES = {Mathematical Sciences Research Institute Publications}, VOLUME = 56, PUBLISHER = {Cambridge University Press}, YEAR = 2009, PAGES = {3--56}, length = {42 pages}, papers = {AlgGameTheory_MFCS2001}, replaces = {AlgGameTheory_MFCS2001}, webpages = {games}, comments = {This paper is also available as arXiv:cs.CC/0106009 of the Computing Research Repository (CoRR).} } @InCollection{Telescopes_GameTheory2005, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer and Robert A. Hearn and Timo von Oertzen}, TITLE = {The Complexity of {D}yson Telescopes}, BOOKTITLE = {Games of No Chance 3}, EDITOR = {Michael H. Albert and Richard J. Nowakowski}, SERIES = {Mathematical Sciences Research Institute Publications}, VOLUME = 56, PUBLISHER = {Cambridge University Press}, YEAR = 2009, PAGES = {271--285}, withstudent = 1, } @Article{CooperativeNetworkCreation_SIGecom, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Morteza Zadimoghaddam}, TITLE = {The Price of Anarchy in Cooperative Network Creation Games}, JOURNAL = {ACM SIGecom Exchanges}, journalurl = {http://sigecom.org/exchanges/}, VOLUME = 8, NUMBER = 2, MONTH = {December}, YEAR = 2009, length = {20 pages}, replaces = {CooperativeNetworkCreation_STACS2009}, papers = {CooperativeNetworkCreation_STACS2009; BasicNetworkCreation_SPAA2010; NetworkCreation_PODC2007}, comments = {This paper is also available from SIGecom.}, } @InProceedings{Checkerboard_ISAAC2009, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Goran Konjevod and Robert J. Lang}, TITLE = {Folding a Better Checkerboard}, BOOKTITLE = {Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)}, bookurl = {http://theory.utdallas.edu/ISAAC2009/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5878, ADDRESS = {Hawaii, USA}, MONTH = {December 16--18}, YEAR = 2009, PAGES = {1074--1083}, comments = {This paper is also available from SpringerLink.}, } @InProceedings{PleatFolding_ISAAC2009, AUTHOR = {Jean Cardinal and Erik D. Demaine and Martin L. Demaine and Shinji Imahori and Stefan Langerman and Ryuhei Uehara}, TITLE = {Algorithmic Folding Complexity}, BOOKTITLE = {Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009)}, bookurl = {http://theory.utdallas.edu/ISAAC2009/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5878, ADDRESS = {Hawaii, USA}, MONTH = {December 16--18}, YEAR = 2009, PAGES = {452--461}, comments = {This paper is also available from SpringerLink.}, replaces = {PleatFolding_JCCGG2009}, papers = {PleatFolding_GC; PleatFolding_JCCGG2009} } @InProceedings{StackMST_WINE2009, AUTHOR = {Jean Cardinal and Erik D. Demaine and Samuel Fiorini and Gwena\"el Joret and Ilan Newman and Oren Weimann}, TITLE = {The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs}, BOOKTITLE = {Proceedings of the 5th Workshop on Internet \& Network Economics (WINE 2009)}, bookurl = {http://www.dis.uniroma1.it/~wine09/index.php}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5929, ADDRESS = {Rome, Italy}, MONTH = {December 14--18}, YEAR = 2009, PAGES = {125--136}, length = {15 pages}, papers = {StackMST_Algorithmica}, comments = {This paper is also available as arXiv:0906.3321 and from SpringerLink.} } @InProceedings{Hypar_JCCGG2009, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart and Gregory N. Price and Tomohiro Tachi}, TITLE = {(Non)existence of Pleated Folds: How Paper Folds Between Creases}, BOOKTITLE = {Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009)}, bookurl = {http://www.jaist.ac.jp/~uehara/JCCGG09/}, ADDRESS = {Kanazawa, Ishikawa, Japan}, MONTH = {November 11--13}, YEAR = 2009, PAGES = {to appear}, length = {2 pages}, papers = {Hypar_GC}, unrefereed = 1, paperkind = {abstract}, comments = {The full paper is available as arXiv:0906.4747.}, withstudent = 1, } @InProceedings{Blooming_JCCGG2009, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart and John Iacono and Stefan Langerman and Joseph O'Rourke}, TITLE = {Continuous Blooming of Convex Polyhedra}, BOOKTITLE = {Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009)}, bookurl = {http://www.jaist.ac.jp/~uehara/JCCGG09/}, ADDRESS = {Kanazawa, Ishikawa, Japan}, MONTH = {November 11--13}, YEAR = 2009, PAGES = {123--124}, unrefereed = 1, papers = {Blooming_GC}, length = {2 pages}, paperkind = {abstract}, comments = {The full paper is available as arXiv:0906.2461.} } @InProceedings{MatchingPoints_JCCGG2009, AUTHOR = {Greg Aloupis and Jean Cardinal and S{\'e}bastien Collette and Erik D. Demaine and Martin L. Demaine and Muriel Dulieu and Ruy Fabila-Monroy and Vi Hart and Ferran Hurtado and Stefan Langerman and Maria Saumell and Carlos Seara and Perouz Taslakian}, TITLE = {Matching Points with Things}, BOOKTITLE = {Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009)}, bookurl = {http://www.jaist.ac.jp/~uehara/JCCGG09/}, ADDRESS = {Kanazawa, Ishikawa, Japan}, MONTH = {November 11--13}, YEAR = 2009, PAGES = {to appear}, length = {2 pages}, unrefereed = 1, paperkind = {abstract}, papers = {MatchingPoints_LATIN2009}, } @InProceedings{PleatFolding_JCCGG2009, AUTHOR = {Jean Cardinal and Erik D. Demaine and Martin L. Demaine and Shinji Imahori and Stefan Langerman and Ryuhei Uehara}, TITLE = {Algorithmic Folding Complexity}, BOOKTITLE = {Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG 2009)}, bookurl = {http://www.jaist.ac.jp/~uehara/JCCGG09/}, ADDRESS = {Kanazawa, Ishikawa, Japan}, MONTH = {November 11--13}, YEAR = 2009, PAGES = {to appear}, length = {2 pages}, unrefereed = 1, papers = {PleatFolding_GC; PleatFolding_ISAAC2009} } @InProceedings{BoundaryDetection_IROS2009, AUTHOR = {James McLurkin and Erik D. Demaine}, TITLE = {A Distributed Boundary Detection Algorithm for Multi-Robot Systems}, BOOKTITLE = {Proceedings of the 2009 IEEE/RSJ International Conference on Intelligent RObots and Systems (IROS 2009)}, bookurl = {http://www.iros09.mtu.edu/}, ADDRESS = {St.\ Louis, Missouri}, MONTH = {October 11--15}, YEAR = 2009, PAGES = {4791--4798}, comments = {This paper is also available from IEEE Xplore.}, withstudent = 1 } @InProceedings{MTRAN_Molecube_ECMR2009, AUTHOR = {Greg Aloupis and Nadia Benbernou and Mirela Damian and Erik D. Demaine and Robin Flatland and John Iacono and Stefanie Wuhrer}, TITLE = {Efficient Reconfiguration of Lattice-Based Modular Robots}, BOOKTITLE = {Proceedings of the 4th European Conference on Mobile Robots (ECMR 2009)}, bookurl = {http://www.ecmr09.fer.hr/}, ADDRESS = {Mlini/Dubrovnik, Croatia}, MONTH = {September 23--25}, YEAR = 2009, PAGES = {81--86}, length = {6 pages}, withstudent = 1, papers = {Crystalline_WAFR2008; Crystalline_ISAAC2008; Crystalline_CGTA}, comments = {See also animations of the 6-arm module.} } @InProceedings{MovementFPT_ESA2009, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx}, TITLE = {Minimizing Movement: Fixed-Parameter Tractability}, BOOKTITLE = {Proceedings of the 17th Annual European Symposium on Algorithms (ESA 2009)}, bookurl = {http://algo2009.itu.dk/esa-2009}, VOLUME = 5757, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, ADDRESS = {Copenhagen, Denmark}, MONTH = {September 7--9}, YEAR = 2009, PAGES = {718--729}, length = {12 pages}, copyright = {Copyright held by the authors.}, } @Article{Crystalline_CGTA, AUTHOR = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian and Erik D. Demaine and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer}, TITLE = {Linear Reconfiguration of Cube-Style Modular Robots}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 42, NUMBER = {6--7}, MONTH = {August}, YEAR = 2009, PAGES = {652--663}, length = {20 pages}, replaces = {Crystalline_ISAAC2007}, papers = {Crystalline_WAFR2008; Crystalline_ISAAC2008; Crystalline_ISAAC2007; Crystalline_EGC2007}, comments = {This paper is also available from ScienceDirect.}, } @InProceedings{WADS2009i, AUTHOR = {Erik D. Demaine}, TITLE = {Algorithms Meet Art, Puzzles, and Magic}, BOOKTITLE = {Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)}, bookurl = {http://www.wads.org/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5664, ADDRESS = {Banff, Alberta, Canada}, MONTH = {August 21--23}, YEAR = 2009, PAGES = {193}, comments = {This paper is also available from SpringerLink.}, paperkind = {abstract}, length = {1 page}, unrefereed = 1, copyright = {Copyright held by the author.}, category = {art}, } %InProceedings{HingedPixels_WADS2009, AUTHOR = {Nadia M. Benbernou and Prosenjit Bose and David Bremner and Erik D. Demaine and Martin L. Demaine and Ferran Hurtado and Vera Sacrist\'an and Perouz Taslakian}, TITLE = {Efficient Reconfiguration of Pivoting Tiles}, BOOKTITLE = {Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)}, bookurl = {http://www.wads.org/}, ADDRESS = {Banff, Alberta, Canada}, MONTH = {August 21--23}, YEAR = 2009, PAGES = {to appear}, length = {12 pages}, copyright = {Copyright held by the authors.}, } @InProceedings{LockedTree_WADS2009, AUTHOR = {Brad Ballinger and David Charlton and Erik D. Demaine and Martin L. Demaine and John Iacono and Ching-Hao Liu and Sheung-Hung Poon}, TITLE = {Minimal Locked Trees}, BOOKTITLE = {Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)}, bookurl = {http://www.wads.org/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5664, ADDRESS = {Banff, Alberta, Canada}, MONTH = {August 21--23}, YEAR = 2009, PAGES = {61--73}, comments = {This paper is also available from SpringerLink.}, length = {12 pages}, copyright = {Copyright held by the authors.}, } @InProceedings{Alexandrov_WADS2009, AUTHOR = {Daniel Kane and Gregory N. Price and Erik D. Demaine}, TITLE = {A pseudopolynomial algorithm for {A}lexandrov's {T}heorem}, BOOKTITLE = {Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)}, bookurl = {http://www.wads.org/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5664, ADDRESS = {Banff, Alberta, Canada}, MONTH = {August 21--23}, YEAR = 2009, PAGES = {435--446}, comments = {This paper is also available from SpringerLink.}, length = {12 pages}, copyright = {Copyright held by the authors.}, } @InProceedings{NPReconfiguration_WADS2009, AUTHOR = {Takehiro Ito and Marcin Kami\'nski and Erik D. Demaine}, TITLE = {Reconfiguration of List Edge-Colorings in a Graph}, BOOKTITLE = {Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009)}, bookurl = {http://www.wads.org/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5664, ADDRESS = {Banff, Alberta, Canada}, MONTH = {August 21--23}, YEAR = 2009, PAGES = {375--386}, comments = {This paper is also available from SpringerLink.}, length = {12 pages}, papers = {NPReconfiguration_TCS; NPReconfiguration_ISAAC2008}, } @InProceedings{MinAvgDistance_CCCG2009, AUTHOR = {Erik D. Demaine and S{\'a}ndor P. Fekete and G{\"u}nter Rote and Nils Schweer and Daria Schymura and Mariano Zelke}, TITLE = {Integer Point Sets Minimizing Average Pairwise $\ell_1$ Distance: What is the Optimal Shape of a Town?}, BOOKTITLE = {Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009)}, bookurl = {http://www.cs.ubc.ca/conferences/CCCG09/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {August 17--19}, YEAR = 2009, PAGES = {145--148}, length = {4 pages}, papers = {MinAvgDistance_CGTA; MinAvgDistance_Algorithmica; MinAvgDistance_JPhysA}, unrefereed = 1, } @InProceedings{CCCG2008Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2008}, BOOKTITLE = {Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009)}, bookurl = {http://www.cs.ubc.ca/conferences/CCCG09/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {August 17--19}, YEAR = 2009, PAGES = {75--78}, papers = {CCCG2010Open; CCCG2009Open; CCCG2007Open; CCCG2006Open; CCCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, length = {4 pages}, unrefereed = 1, } @InProceedings{RelaxedGabriel_CCCG2009, AUTHOR = {Prosenjit Bose and Jean Cardinal and S{\'e}bastien Collette and Erik D. Demaine and Bel{\'e}n Palop and Perouz Taslakian and Norbert Zeh}, TITLE = {Relaxed {G}abriel Graphs}, BOOKTITLE = {Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009)}, bookurl = {http://www.cs.ubc.ca/conferences/CCCG09/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {August 17--19}, YEAR = 2009, PAGES = {169--172}, length = {4 pages}, unrefereed = 1, } @Article{DeepRhythms_CGTA, AUTHOR = {Erik D. Demaine and Francisco Gomez-Martin and Henk Meijer and David Rappaport and Perouz Taslakian and Godfried T. Toussaint and Terry Winograd and David R. Wood}, TITLE = {The Distance Geometry of Music}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 42, NUMBER = 5, MONTH = {July}, YEAR = 2009, PAGES = {429--454}, NOTE = {Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.}, papers = {DeepRhythms_CCCG2005}, replaces = {DeepRhythms_CCCG2005}, length = {39 pages}, category = {art}, comments = {This paper is also available from ScienceDirect.}, } @Book{GPC, AUTHOR = {Robert A. Hearn and Erik D. Demaine}, TITLE = {Games, Puzzles, and Computation}, PUBLISHER = {A K Peters}, MONTH = {July}, YEAR = {2009}, length = {250 pages}, comments = {See the publisher's webpage for this book. }, availability = {Available for purchase from the publisher or Amazon.}, } @Article{Movement_TAlg, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Amin S. Sayedi-Roshkhar and Shayan Oveisgharan and Morteza Zadimoghaddam}, JOURNAL = {ACM Transactions on Algorithms}, journalurl = {http://www.acm.org/talg/}, TITLE = {Minimizing Movement}, VOLUME = 5, NUMBER = 3, MONTH = {July}, YEAR = 2009, PAGES = {Article 30}, length = {31 pages}, withstudent = 1, papers = {Movement_SODA2007}, replaces = {Movement_SODA2007}, } @InProceedings{BRIDGES2009i, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Mathematics Is Art}, BOOKTITLE = {Proceedings of 12th Annual Conference of BRIDGES: Mathematics, Music, Art, Architecture, Culture (BRIDGES 2009)}, bookurl = {http://www.bridgesmathart.org/bridges-2009/}, ADDRESS = {Banff, Alberta, Canada}, MONTH = {July 26--29}, YEAR = 2009, PAGES = {1--10}, length = {10 pages}, unrefereed = 1, category = {art}, } @InProceedings{ApexMinorFree_ICALP2009, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs}, BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)}, bookurl = {http://icalp09.cti.gr/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5555, ADDRESS = {Rhodes, Greece}, MONTH = {July 5--12}, YEAR = 2009, PAGES = {316--327}, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, length = {12 pages} } @InProceedings{NodeSteiner_ICALP2009, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Philip Klein}, TITLE = {Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs}, BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)}, bookurl = {http://icalp09.cti.gr/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5555, ADDRESS = {Rhodes, Greece}, MONTH = {July 5--12}, YEAR = 2009, PAGES = {328--340}, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, length = {12 pages} } @InProceedings{Cartesian_ICALP2009, AUTHOR = {Erik D. Demaine and Gad Landau and Oren Weimann}, TITLE = {On {C}artesian Trees and Range Minimum Queries}, BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)}, bookurl = {http://icalp09.cti.gr/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5555, ADDRESS = {Rhodes, Greece}, MONTH = {July 5--12}, YEAR = 2009, PAGES = {341--353}, comments = {This paper is also available from SpringerLink.}, length = {12 pages} } @Article{DynamicHamSandwich_CGTA, AUTHOR = {Timothy G. Abbott and Michael A. Burr and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and John Hugg and Daniel Kane and Stefan Langerman and Jelani Nelson and Eynat Rafalin and Kathryn Seyboth and Vincent Yeung}, TITLE = {Dynamic Ham-Sandwich Cuts in the Plane}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 42, NUMBER = 5, MONTH = {July}, YEAR = 2009, PAGES = {419--428}, NOTE = {Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.}, length = {15 pages}, withstudent = 1, replaces = {DynamicHamSandwich_CCCG2005}, papers = {DynamicHamSandwich_CCCG2005}, comments = {This paper is also available from ScienceDirect.}, } @Article{GridWagner_Algorithmica, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and {W}agner's Contraction}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 54, NUMBER = 2, MONTH = {June}, YEAR = 2009, PAGES = {142--180}, NOTE = {Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006.}, comments = {This paper is also available from SpringerLink.}, papers = {GridWagner_ISAAC2006}, copyright = {The paper is \copyright Springer-Verlag.}, } @Article{Refolding_DCG, AUTHOR = {Hayley N. Iben and James F. O'Brien and Erik D. Demaine}, TITLE = {Refolding Planar Polygons}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 41, NUMBER = 3, MONTH = {April}, YEAR = 2009, PAGES = {444--460}, NOTE = {Special issue of selected papers from the 22nd Annual ACM Symposium on Computational Geometry, 2006.}, replaces = {Refolding_SoCG2006}, comments = {See also animations of this algorithm.

This paper is also available from SpringerLink.}, papers = {Refolding_SoCG2006; Refolding_SIGGRAPH2004; ForceLinkage_SoCG2004}, } @InProceedings{ThickChain_EuroCG2009, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Stefan Langerman and J{\'e}r{\^o}me Vervier}, TITLE = {Locked Thick Chains}, BOOKTITLE = {Abstracts from the 25th European Workshop on Computational Geometry (EuroCG 2009)}, bookurl = {http://2009.eurocg.org/}, ADDRESS = {Brussels, Belgium}, MONTH = {March 16--18}, YEAR = 2009, PAGES = {65--68}, paperkind = {abstract}, length = {4 pages}, unrefereed = 1, } @InProceedings{SteinerGenus_STACS2009, AUTHOR = {Glencora Borradaile and Erik D. Demaine and Siamak Tazari}, TITLE = {Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs}, BOOKTITLE = {Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)}, bookurl = {http://stacs2009.informatik.uni-freiburg.de/}, ADDRESS = {Freiburg, Germany}, MONTH = {February 26--28}, YEAR = 2009, PAGES = {171--182}, copyright = {Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.}, } @InProceedings{CooperativeNetworkCreation_STACS2009, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Morteza Zadimoghaddam}, TITLE = {The Price of Anarchy in Cooperative Network Creation Games}, BOOKTITLE = {Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)}, bookurl = {http://stacs2009.informatik.uni-freiburg.de/}, ADDRESS = {Freiburg, Germany}, MONTH = {February 26--28}, YEAR = 2009, PAGES = {301--312}, copyright = {Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.}, papers = {CooperativeNetworkCreation_SIGecom; BasicNetworkCreation_SPAA2010; NetworkCreation_TALG}, } @InProceedings{BST_SODA2009, AUTHOR = {Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai P\v{a}tra\c{s}cu}, TITLE = {The Geometry of Binary Search Trees}, BOOKTITLE = {Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)}, bookurl = {http://www.siam.org/meetings/da09/}, ADDRESS = {New York, New York}, MONTH = {January 4--6}, YEAR = 2009, PAGES = {496--505}, withstudent = 1, length = {10 pages}, } @InProceedings{ListColoring_SODA2009, AUTHOR = {Ken-ichi Kawarabayashi and Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs}, BOOKTITLE = {Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)}, bookurl = {http://www.siam.org/meetings/da09/}, ADDRESS = {New York, New York}, MONTH = {January 4--6}, YEAR = 2009, PAGES = {1166--1175}, length = {10 pages}, } @Article{SupplyDemand_JDA, AUTHOR = {Takehiro Ito and Erik D. Demaine and Xiao Zhou and Takao Nishizeki}, TITLE = {Approximability of Partitioning Graphs with Supply and Demand}, JOURNAL = {Journal of Discrete Algorithms}, journalurl = {http://www.elsevier.com/locate/jda}, VOLUME = 6, NUMBER = 4, MONTH = {December}, YEAR = 2008, PAGES = {627--650}, comments = {This paper is also available from ScienceDirect.}, replaces = {SupplyDemand_ISAAC2006}, papers = {SupplyDemand_ISAAC2006}, } @InProceedings{Crystalline_WAFR2008, AUTHOR = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian and Erik D. Demaine and Dania El-Khechen and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Val Pinciu and Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer}, TITLE = {Realistic Reconfiguration of Crystalline (and Telecube) Robots}, BOOKTITLE = {Proceedings of the 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008)}, bookurl = {http://www.wafr.org/}, SERIES = {Springer Tracts in Advanced Robotics}, VOLUME = 57, ADDRESS = {Guanajuato, M\'exico}, MONTH = {December 7--9}, YEAR = 2008, PAGES = {433--447}, comments = {This paper is also available from SpringerLink.}, length = {16 pages}, papers = {Crystalline_ISAAC2008; Crystalline_CGTA} } @InCollection{BidimensionalSurvey_Encyclopedia2008, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Bidimensionality (2004; Demaine, Fomin, Hajiaghayi, Thilikos)}, BOOKTITLE = {Encyclopedia of Algorithms}, PUBLISHER = {Springer-Verlag}, publisherurl = {http://www.springer.com/}, YEAR = 2008, PAGES = {88--90}, comments = {This paper is also available from SpringerLink.}, } @InCollection{PlanarApprox_Encyclopedia2008, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Approximation Schemes for Planar Graph Problems (1983, 1984; Baker)}, BOOKTITLE = {Encyclopedia of Algorithms}, PUBLISHER = {Springer-Verlag}, publisherurl = {http://www.springer.com/}, YEAR = 2008, PAGES = {59--62}, comments = {This paper is also available from SpringerLink.}, } @InCollection{Flips_DCG20, AUTHOR = {Erik D. Demaine and Blaise Gassend and Joseph O'Rourke and Godfried T. Toussaint}, TITLE = {All Polygons Flip Finitely\dots\ Right?}, BOOKTITLE = {Surveys on Discrete and Computational Geometry: Twenty Years Later}, SERIES = {Contemporary Mathematics}, VOLUME = 453, PUBLISHER = {American Mathematical Society}, EDITOR = {J. Goodman and J. Pach and R. Pollack}, YEAR = 2008, PAGES = {231--255}, NOTE = {Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, June 18--22, 2006, Snowbird, Utah.}, copyright = {Copyright held by the authors.}, length = {19 pages}, withstudent = 1, replaces = {Flips_CCCG2006}, papers = {Flips_CCCG2006}, } @Article{Contour_JDA, AUTHOR = {Erik D. Demaine and Jeff Erickson and Danny Kri\c{z}anc and Henk Meijer and Pat Morin and Mark Overmars and Sue Whitesides}, TITLE = {Realizing Partitions Respecting Full and Partial Order Information}, JOURNAL = {Journal of Discrete Algorithms}, journalurl = {http://www.elsevier.com/locate/jda}, VOLUME = 6, PAGES = {51--58}, YEAR = 2008, NOTE = {Special issue of selected papers from the 16th Australasian Workshop on Combinatorial Algorithms, 2005.}, comments = {This paper is also available from ScienceDirect.}, papers = {Contour_AWOCA2005}, replaces = {Contour_AWOCA2005}, } @Article{BidimensionalSurvey_CJ, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {The Bidimensionality Theory and Its Algorithmic Applications}, JOURNAL = {The Computer Journal}, VOLUME = 51, NUMBER = 3, PAGES = {292--302}, YEAR = 2008, papers = {BidimensionalSurvey_GD2004}, withstudent = 1, copyright = {Copyright held by the authors.}, comments = {This paper is also available from Oxford Journals.}, } @InProceedings{NPReconfiguration_ISAAC2008, AUTHOR = {Takehiro Ito and Erik D. Demaine and Nicholas J. A. Harvey and Christos H. Papadimitriou and Martha Sideri and Ryuhei Uehara and Yushi Uno}, TITLE = {On the Complexity of Reconfiguration Problems}, BOOKTITLE = {Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008)}, bookurl = {http://www-or.amp.i.kyoto-u.ac.jp/isaac08/}, ADDRESS = {Gold Coast, Australia}, MONTH = {December 15--17}, YEAR = 2008, PAGES = {28--39}, length = {12 pages}, withstudent = 1, comments = {This paper is also available from SpringerLink.}, papers = {NPReconfiguration_TCS; NPReconfiguration_WADS2009}, } @InProceedings{Crystalline_ISAAC2008, AUTHOR = {Greg Aloupis and S{\'e}bastien Collette and Erik D. Demaine and Stefan Langerman and Vera Sacrist{\'a}n and Stefanie Wuhrer}, TITLE = {Reconfiguration of Cube-Style Modular Robots Using {$O(\log n)$} Parallel Moves}, BOOKTITLE = {Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008)}, bookurl = {http://www-or.amp.i.kyoto-u.ac.jp/isaac08/}, ADDRESS = {Gold Coast, Australia}, MONTH = {December 15--17}, YEAR = 2008, PAGES = {342--353}, papers = {Crystalline_WAFR2008; Crystalline_CGTA}, copyright = {Copyright held by the authors.}, length = {12 pages}, comments = {This paper is also available from SpringerLink.}, } @Book{Gardner90, EDITOR = {Erik Demaine and Martin Demaine and Tom Rodgers}, TITLE = {A Lifetime of Puzzles}, PUBLISHER = {A~K~Peters}, publisherurl = {http://www.akpeters.com/}, MONTH = {October}, YEAR = 2008, length = {250 pages}, comments = {See the publisher's webpage for this book. }, availability = {Available for purchase from the publisher or Amazon.}, papers = {Gardner5} } @Article{UniqueCoverage_SICOMP, AUTHOR = {Erik D. Demaine and Uriel Feige and MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour}, TITLE = {Combination Can Be Hard: Approximability of the Unique Coverage Problem}, JOURNAL = {SIAM Journal on Computing}, journalurl = {http://www.siam.org/journals/sicomp/sicomp.htm}, VOLUME = 38, NUMBER = 4, PAGES = {1464--1483}, MONTH = {September}, YEAR = 2008, withstudent = 1, papers = {UniqueCoverage_SODA2006}, replaces = {UniqueCoverage_SODA2006}, comments = {This paper is also available from SIAM.}, } @Article{StagedAssembly_NACO, AUTHOR = {Erik D. Demaine and Martin L. Demaine and S\'andor P. Fekete and Mashhood Ishaque and Eynat Rafalin and Robert T. Schweller and Diane L. Souvaine}, TITLE = {Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with $O(1)$ Glues}, JOURNAL = {Natural Computing}, VOLUME = 7, NUMBER = 3, MONTH = {September}, YEAR = 2008, PAGES = {347--370}, NOTE = {Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007.}, replaces = {StagedAssembly_DNA2007}, papers = {StagedAssembly_DNA2007}, comments = {This paper is also available from SpringerLink.}, updates = {The tile bound of 16 in Table 1 row 5 (arbitrary shape) and in Theorem 5 is incorrect; the correct bound (for the same algorithm) is 52.} } @InProceedings{CurvedCrease_AAG2008, AUTHOR = {Duks Koschitz and Erik D. Demaine and Martin L. Demaine}, TITLE = {Curved Crease Origami}, BOOKTITLE = {Abstracts from Advances in Architectural Geometry (AAG 2008)}, bookurl = {http://www.architecturalgeometry.at/aag08/}, ADDRESS = {Vienna, Austria}, MONTH = {September 13--16}, YEAR = 2008, PAGES = {29--32}, paperkind = {abstract}, unrefereed = 1, withstudent = 1, category = {art}, } @Article{Ordinal_TAlg, AUTHOR = {Noga Alon and Mihai B\u{a}doiu and Erik D. Demaine and Martin Farach-Colton and MohammadTaghi Hajiaghayi and Anastasios Sidiropoulos}, TITLE = {Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics}, JOURNAL = {ACM Transactions on Algorithms}, journalurl = {http://www.acm.org/talg/}, VOLUME = 4, NUMBER = 4, MONTH = {August}, YEAR = 2008, PAGES = {Article 46}, length = {21 pages}, withstudent = 1, papers = {Ordinal_APPROX2008; Ordinal_SODA2005}, replaces = {Ordinal_SODA2005}, comments = {This paper is also available from the ACM Digital Library.}, } @InProceedings{Ordinal_APPROX2008, AUTHOR = {Mihai B\u{a}doiu and Erik D. Demaine and MohammadTaghi Hajiaghayi and Anastasios Sidiropoulos and Morteza Zadimoghaddam}, TITLE = {Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction}, BOOKTITLE = {Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008)}, bookurl = {http://cui.unige.ch/tcs/random-approx/2008/index.php}, ADDRESS = {Boston, Massachusetts}, MONTH = {August 25--27}, YEAR = 2008, PAGES = {21--34}, comments = {This paper is also available from SpringerLink.}, withstudent = 1, length = {14 pages}, papers = {Ordinal_TAlg}, } @InProceedings{Balloons_CCCG2008, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Vi Hart}, TITLE = {Computational Balloon Twisting: The Theory of Balloon Polyhedra}, BOOKTITLE = {Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008)}, bookurl = {http://www.cs.mcgill.ca/~cccg2008}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 13--15}, YEAR = 2008, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, comments = {A short version of the paper appeared on pages 139--142.}, length = {10 pages}, unrefereed = 1, papers = {Balloons_ShapingSpace2}, category = {art}, } @InProceedings{CCCG2007Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2007}, BOOKTITLE = {Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008)}, bookurl = {http://www.cs.mcgill.ca/~cccg2008}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 13--15}, YEAR = 2008, PAGES = {183--190}, length = {8 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2006Open; CCCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, unrefereed = 1 } @InProceedings{ConfluentTries_SWAT2008, AUTHOR = {Erik D. Demaine and Stefan Langerman and Eric Price}, TITLE = {Confluently Persistent Tries for Efficient Version Control}, BOOKTITLE = {Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008)}, bookurl = {http://www.dmist.net/swat2008}, ADDRESS = {Gothenburg, Sweden}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 5124, MONTH = {July 2--4}, YEAR = 2008, PAGES = {160--172}, papers = {ConfluentTries_Algorithmica}, comments = {This paper is also available from SpringerLink.}, withstudent = 1, copyright = {Copyright held by the authors.}, award = {Invited to special issue of \emph{Algorithmica}.}, } @InProceedings{CL_Complexity2008, AUTHOR = {Erik D. Demaine and Robert A. Hearn}, TITLE = {Constraint Logic: A Uniform Framework for Modeling Computation as Games}, BOOKTITLE = {Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008)}, bookurl = {http://ccc08.cs.washington.edu/}, ADDRESS = {College Park, Maryland}, MONTH = {June 23--26}, YEAR = 2008, PAGES = {149--162}, papers = {NCL_TCS} } @InProceedings{HingedDissections_SoCG2008, AUTHOR = {Timothy G. Abbott and Zachary Abel and David Charlton and Erik D. Demaine and Martin L. Demaine and Scott D. Kominers}, TITLE = {Hinged Dissections Exist}, BOOKTITLE = {Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008)}, bookurl = {http://www.umiacs.umd.edu/conferences/socg2008/}, ADDRESS = {College Park, Maryland}, MONTH = {June 9--11}, YEAR = 2008, PAGES = {110--119}, withstudent = 1, papers = {HingedDissections_DCG} } @InProceedings{MovingLocalization_IPSN2008, AUTHOR = {Jun-geun Park and Erik D. Demaine and Seth J. Teller}, TITLE = {Moving-Baseline Localization}, BOOKTITLE = {Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008)}, bookurl = {http://ipsn.acm.org/2008/}, ADDRESS = {St. Louis, Missouri}, MONTH = {April 22--24}, YEAR = {2008}, PAGES = {15--26}, comments = {This paper is also available from IEEE Xplore.}, withstudent = 1, } @Article{3SUM_Algorithmica, AUTHOR = {Ilya Baran and Erik D. Demaine and Mihai P\v{a}tra\c{s}cu}, TITLE = {Subquadratic Algorithms for {3SUM}}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 50, NUMBER = 4, MONTH = {April}, YEAR = 2008, PAGES = {584--596}, NOTE = {Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.}, comments = {This paper is also available from SpringerLink.}, withstudent = 1, replaces = {3SUM_WADS2005}, papers = {3SUM_WADS2005}, } @InCollection{CoinFlipping_G4G8, AUTHOR = {Nadia Benbernou and Erik D. Demaine and Martin L. Demaine and Benjamin Rossman}, TITLE = {Coin-Flipping Magic}, BOOKTITLE = {Exchange Book of the 8th Gathering for Gardner (G4G8)}, bookurl = {http://www.g4g4.com/}, ADDRESS = {Atlanta, Georgia}, MONTH = {March}, YEAR = 2008, length = {12 pages}, withstudent = 1, category = {magic}, } @Article{MinAvgDistance_Algorithmica, AUTHOR = {Michael A. Bender and David P. Bunde and Erik D. Demaine and S{\'a}ndor P. Fekete and Vitus J. Leung and Henk Meijer and Cynthia A. Phillips}, TITLE = {Communication-Aware Processor Allocation for Supercomputers}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 50, NUMBER = 2, MONTH = {February}, YEAR = 2008, PAGES = {279--298}, NOTE = {Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.}, comments = {This paper is also available from SpringerLink.}, replaces = {MinAvgDistance_WADS2005}, papers = {MinAvgDistance_WADS2005; MinAvgDistance_CCCG2009; MinAvgDistance_JPhysA}, } @Article{Integration_Algorithmica, AUTHOR = {Ilya Baran and Erik D. Demaine and Dmitriy A. Katz}, TITLE = {Optimally Adaptive Integration of Univariate {L}ipschitz Functions}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 50, NUMBER = 2, PAGES = {255--278}, MONTH = {February}, YEAR = 2008, NOTE = {Special issue of selected papers from the 7th Latin American Symposium on Theoretical Informatics, 2006.}, comments = {This paper is also available from SpringerLink.}, withstudent = 1, papers = {Integration_LATIN2006}, replaces = {Integration_LATIN2006}, } @Article{GridMinors_Combinatorica, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Linearity of Grid Minors in Treewidth with Applications through Bidimensionality}, JOURNAL = {Combinatorica}, journalurl = {http://www.springerlink.com/content/1439-6912/}, VOLUME = 28, NUMBER = 1, MONTH = {January}, YEAR = 2008, PAGES = {19--36}, withstudent = 1, length = {13 pages}, replaces = {GridMinors_SODA2005}, papers = {GridMinors_SODA2005}, comments = {This paper is also available from SpringerLink.}, } @Article{BandUnfolding_CGTA, AUTHOR = {Greg Aloupis and Erik D. Demaine and Stefan Langerman and Pat Morin and Joseph O'Rourke and Ileana Streinu and Godfried Toussaint}, TITLE = {Edge-Unfolding Nested Polyhedral Bands}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 39, NUMBER = 1, MONTH = {January}, YEAR = 2008, PAGES = {30--42}, NOTE = {Special issue of selected papers from the 16th Canadian Conference on Computational Geometry, 2004.}, comments = {This paper is also available from ScienceDirect.}, papers = {BandUnfolding_CCCG2004}, length = {19 pages}, } @Article{Unified_TCS, AUTHOR = {Mihai B\u{a}doiu and Richard Cole and Erik D. Demaine and John Iacono}, TITLE = {A Unified Access Bound on Comparison-Based Dynamic Dictionaries}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://www.elsevier.nl/locate/tcs}, VOLUME = 382, NUMBER = 2, MONTH = {August}, YEAR = 2007, PAGES = {86--96}, NOTE = {Special issue of selected papers from the 6th Latin American Symposium on Theoretical Informatics, 2004.}, comments = {This paper is also available from ScienceDirect.}, replaces = {Unified_LATIN2004}, papers = {Unified_LATIN2004}, withstudent = 1, } @Article{PlanarEmbedding_JGAA, AUTHOR = {Sergio Cabello and Erik D. Demaine and G\"unter Rote}, TITLE = {Planar Embeddings of Graphs with Specified Edge Lengths}, JOURNAL = {Journal of Graph Algorithms and Applications}, journalurl = {http://jgaa.info/}, VOLUME = 11, NUMBER = 1, YEAR = 2007, PAGES = {259--276}, comments = {This paper is also available from the journal.}, length = {18 pages}, replaces = {PlanarEmbedding_GD2003}, papers = {PlanarEmbedding_GD2003}, } @Article{PlaneEmbedding_DCG, AUTHOR = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Mohammad Moharrami}, TITLE = {Plane Embeddings of Planar Graph Metrics}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 38, YEAR = 2007, PAGES = {615--637}, papers = {PlaneEmbedding_SoCG2006}, replaces = {PlaneEmbedding_SoCG2006} } @InProceedings{Crystalline_ISAAC2007, AUTHOR = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian and Erik D. Demaine and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer}, TITLE = {Linear Reconfiguration of Cube-Style Modular Robots}, BOOKTITLE = {Proceedings of the 18th Annual International Symposium on Algorithms and Computation (ISAAC 2007)}, bookurl = {http://www.nishizeki.ecei.tohoku.ac.jp/isaac07/}, MONTH = {December 17--19}, YEAR = 2007, PAGES = {208--219}, comments = {This paper is also available from SpringerLink.}, replaces = {Crystalline_EGC2007}, papers = {Crystalline_CGTA; Crystalline_ISAAC2008; Crystalline_EGC2007}, } @InProceedings{Pops_CCCG2007, AUTHOR = {Greg Aloupis and Brad Ballinger and Prosenjit Bose and Mirela Damian and Erik D. Demaine and Martin L. Demaine and Robin Flatland and Ferran Hurtado and Stefan Langerman and Joseph O'Rourke and Perouz Taslakian and Godfried Toussaint}, TITLE = {Vertex Pops and Popturns}, BOOKTITLE = {Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007)}, bookurl = {http://2007.cccg.ca/}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {August 20--22}, YEAR = 2007, PAGES = {137--140}, length = {4 pages}, unrefereed = 1, } @InProceedings{DiceRolling_CCCG2007, AUTHOR = {Kevin Buchin and Maike Buchin and Erik D. Demaine and Martin L. Demaine and Dania El-Khechen and S\'andor Fekete and Christian Knauer and Andr\'e Schulz and Perouz Taslakian}, TITLE = {On Rolling Cube Puzzles}, BOOKTITLE = {Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007)}, bookurl = {http://2007.cccg.ca/}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {August 20--22}, YEAR = 2007, comments = {A short version of the paper appeared on pages 141-144.}, length = {30 pages}, unrefereed = 1, } @InProceedings{SegmentOrdering_CCCG2007, AUTHOR = {Nadia M. Benbernou and Erik D. Demaine and Martin L. Demaine and Michael Hoffmann and Mashhood Ishaque and Diane L. Souvaine and Csaba D. T\'oth}, TITLE = {Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs}, BOOKTITLE = {Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007)}, bookurl = {http://2007.cccg.ca/}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {August 20--22}, YEAR = 2007, PAGES = {13--16}, length = {4 pages}, withstudent = 1, unrefereed = 1, updates = {Unfortunately this paper is flawed. Read our erratum (which appears in CCCG 2008, page 223).} } @InProceedings{CCCG2006Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2006}, BOOKTITLE = {Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007)}, bookurl = {http://2007.cccg.ca/}, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {August 20--22}, YEAR = 2007, PAGES = {277--280}, length = {4 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, unrefereed = 1 } @InProceedings{StackMST_WADS2007, AUTHOR = {Jean Cardinal and Erik D. Demaine and Samuel Fiorini and Gwena\"el Joret and Stefan Langerman and Ilan Newman and Oren Weimann}, TITLE = {The Stackelberg Minimum Spanning Tree Game}, BOOKTITLE = {Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007)}, bookurl = {http://projects.cs.dal.ca/wads07/}, ADDRESS = {Halifax, Nova Scotia, Canada}, MONTH = {August 15--17}, YEAR = 2007, PAGES = {64--76}, VOLUME = 4619, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, length = {12 pages}, withstudent = 1, papers = {StackMST_Algorithmica}, } @InProceedings{ArtGallery_WADS2007, AUTHOR = {Ajay Deshpande and Taejung Kim and Erik D. Demaine and Sanjay E. Sarma}, TITLE = {A Pseudopolynomial Time $O(\log^2 n)$-Approximation Algorithm for Art Gallery Problems}, BOOKTITLE = {Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007)}, bookurl = {http://projects.cs.dal.ca/wads07/}, ADDRESS = {Halifax, Nova Scotia, Canada}, MONTH = {August 15--17}, YEAR = 2007, PAGES = {163--174}, VOLUME = 4619, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, length = {12 pages}, withstudent = 1 } @InProceedings{NetworkCreation_PODC2007, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Morteza Zadimoghaddam}, TITLE = {The Price of Anarchy in Network Creation Games}, BOOKTITLE = {Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007)}, bookurl = {http://www.podc.org/podc2007/}, ADDRESS = {Portland, Oregon}, MONTH = {August 12--15}, YEAR = 2007, PAGES = {292--298}, papers = {CooperativeNetworkCreation_SIGecom; BasicNetworkCreation_SPAA2010; NetworkCreation_TALG}, } @InProceedings{Quorum_WASA2007, AUTHOR = {Daniela Tulone and Erik D. Demaine}, TITLE = {Revising Quorum Systems for Energy Conservation in Sensor Networks}, BOOKTITLE = {Proceedings of the International Conference on Wireless Algorithms, Systems and Applications (WASA 2007)}, bookurl = {http://www.wasaconf.org/}, ADDRESS = {Chicago, Illinois}, MONTH = {August 1--3}, YEAR = 2007, PAGES = {147--157}, comments = {This paper is also available from IEEE Xplore.}, } @Book{GFALOP, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Geometric Folding Algorithms: Linkages, Origami, Polyhedra}, PUBLISHER = {Cambridge University Press}, publisherurl = {http://www.cambridge.org/}, MONTH = {July}, YEAR = 2007, length = {496 pages}, comments = {See the book's webpage.     Now available in Japanese!   }, availability = {Available for purchase from the publisher or Amazon.}, category = {art}, } @Misc{DagstuhlFPT2007Open, AUTHOR = {Erik D. Demaine and Gregory Gutin and D\'aniel Marx and Ulrike Stege}, TITLE = {Open Problems from Dagstuhl Seminar 07281: Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, HOWPUBLISHED = {Manuscript}, MONTH = {July}, YEAR = 2007, unrefereed = 1, length = {6 pages}, } @InProceedings{TreeEdit_ICALP2007, AUTHOR = {Erik D. Demaine and Shay Mozes and Benjamin Rossman and Oren Weimann}, TITLE = {An Optimal Decomposition Algorithm for Tree Edit Distance}, BOOKTITLE = {Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007)}, bookurl = {http://icalp07.ii.uni.wroc.pl/}, MONTH = {July 9--13}, YEAR = 2007, ADDRESS = {Wroclaw, Poland}, PAGES = {146--157}, withstudent = 1, award = {Invited to special issue of \emph{Theoretical Computer Science}.}, } @Article{Sona_JMA, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Perouz Taslakian and Godfried T. Toussaint}, TITLE = {Sand Drawings and {G}aussian Graphs}, JOURNAL = {Journal of Mathematics and the Arts}, journalurl = {http://www.tandf.co.uk/journals/titles/17513472.asp}, VOLUME = 1, NUMBER = 2, MONTH = {June}, YEAR = 2007, PAGES = {125--132}, length = {9 pages}, replaces = {Sona_BRIDGES2006}, papers = {Sona_BRIDGES2006}, comments = {This paper is also avilable from informaworld.}, category = {art}, } @InProceedings{Crystalline_EGC2007, AUTHOR = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian and Erik D. Demaine and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer}, TITLE = {Linear Reconfiguration of Cube-Style Modular Robots}, BOOKTITLE = {Abstracts from the 12th Encuentros de Geometr{\'\i}a Computacional (EGC 2007)}, bookurl = {http://www.infor.uva.es/egc07/}, MONTH = {June 25--27}, YEAR = 2007, PAGES = {19--34}, paperkind = {abstract}, unrefereed = 1, papers = {Crystalline_CGTA; Crystalline_ISAAC2007}, } @Article{Jigsaw_GC, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity}, JOURNAL = {Graphs and Combinatorics}, VOLUME = {23 (Supplement)}, MONTH = {June}, YEAR = 2007, PAGES = {195--208}, EDITOR = {D. Avis and A. Bondy and M. Kano and N. Katoh}, NOTE = {Special issue on Computational Geometry and Graph Theory: The Akiyama-Chvatal Festschrift.}, comments = {This paper is also available from SpringerLink.}, updates = { The last paragraph of the introduction asks about polyomino packing puzzles where each piece has just logarithmic area. Michael Brand (2007) has proved such puzzles NP-complete by following a similar approach to this paper, but going directly from 3-partition to polyomino packing. }, papers = {Jigsaw_KyotoCGGT2007}, replaces = {Jigsaw_KyotoCGGT2007}, } @InProceedings{Jigsaw_KyotoCGGT2007, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity}, BOOKTITLE = {Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/web/cggt2007/}, ADDRESS = {Kyoto, Japan}, MONTH = {June 11--15}, YEAR = 2007, info = {book has no page numbers!}, paperkind = {abstract}, length = {2 pages}, unrefereed = 1, papers = {Jigsaw_GC}, } @InProceedings{Deflation_KyotoCGGT2007, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Thomas Fevens and Antonio Mesa and Michael Soss and Diane L. Souvaine and Perouz Taslakian and Godfried Toussaint}, TITLE = {Deflating The Pentagon}, BOOKTITLE = {Revised Papers from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/web/cggt2007/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 4535, ADDRESS = {Kyoto, Japan}, MONTH = {June 11--15}, YEAR = 2007, PAGES = {56--67}, length = {12 pages}, papers = {Deflation_EuroCG2007}, comments = {This paper is also available from SpringerLink.

A short version of the paper (with fewer authors) appeared in Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory.} } @InProceedings{GapScheduling_SPAA2007, AUTHOR = {Erik D. Demaine and Mohammad Ghodsi and MohammadTaghi Hajiaghayi and Amin S. Sayedi-Roshkhar and Morteza Zadimoghaddam}, TITLE = {Scheduling to Minimize Gaps and Power Consumption}, BOOKTITLE = {Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007)}, bookurl = {http://www.spaa-conference.org/}, ADDRESS = {San Diego, California}, MONTH = {June 9--11}, YEAR = 2007, PAGES = {46--54}, length = {9 pages}, papers = {SubmodularGapScheduling_SPAA2010}, } @InProceedings{DynamicConvexHull_SoCG2007, AUTHOR = {Erik D. Demaine and Mihai P{\v{a}}tra{\c{s}}cu}, TITLE = {Tight Bounds for Dynamic Convex Hull Queries (Again)}, BOOKTITLE = {Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007)}, bookurl = {http://www.socg.org/2007/}, ADDRESS = {Gyeongju, South Korea}, MONTH = {June 6--8}, YEAR = 2007, PAGES = {354--363}, withstudent = 1 } @InProceedings{StagedAssembly_DNA2007, AUTHOR = {Erik D. Demaine and Martin L. Demaine and S\'andor P. Fekete and Mashhood Ishaque and Eynat Rafalin and Robert T. Schweller and Diane L. Souvaine}, TITLE = {Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with $O(1)$ Glues}, BOOKTITLE = {Proceedings of the 13th International Meeting on DNA Computing (DNA 2007)}, bookurl = {http://dna13.memphis.edu/}, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, VOLUME = 4848, ADDRESS = {Memphis, Tennessee}, MONTH = {June 4--8}, YEAR = 2007, PAGES = {1--14}, comments = {This paper is also available from SpringerLink.}, award = {Invited to special issue of \emph{Journal of Natural Computing}.}, papers = {StagedAssembly_NACO}, updates = {The tile bound of 16 in Table 1 row 5 (arbitrary shape) and in Theorem 5 is incorrect; the correct bound (for the same algorithm) is 52.} } @Article{Retroactive_TALG, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Retroactive Data Structures}, JOURNAL = {ACM Transactions on Algorithms}, journalurl = {http://www.acm.org/talg/}, VOLUME = 3, NUMBER = 2, MONTH = {May}, YEAR = 2007, PAGES = {Article 13}, length = {21 pages}, papers = {Retroactive_SODA2004}, replaces = {Retroactive_SODA2004}, } @Article{Tango_SICOMP, AUTHOR = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P\v{a}tra\c{s}cu}, TITLE = {Dynamic Optimality---Almost}, JOURNAL = {SIAM Journal on Computing}, journalurl = {http://www.siam.org/journals/sicomp/sicomp.htm}, VOLUME = 37, NUMBER = 1, PAGES = {240--251}, MONTH = {May}, YEAR = 2007, NOTE = {Special issue of selected papers from the 45th Annual IEEE Symposium on Foundations of Computer Science.}, comments = {This paper is also available from SIAM.}, length = {12 pages}, withstudent = 1, papers = {Tango_FOCS2004}, replaces = {Tango_FOCS2004}, } @Article{BufferTrees_SICOMP, AUTHOR = {Lars Arge and Michael A. Bender and Erik D. Demaine and Bryan E. Holland-Minkley and J. Ian Munro}, TITLE = {An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms}, JOURNAL = {SIAM Journal on Computing}, journalurl = {http://www.siam.org/journals/sicomp/sicomp.htm}, VOLUME = 36, NUMBER = 6, PAGES = {1672--1695}, MONTH = {March}, YEAR = 2007, length = {26 pages}, papers = {BufferTrees_STOC2002}, replaces = {BufferTrees_STOC2002}, } @Article{GeodesicHamSandwich_DCG, AUTHOR = {Prosenjit Bose and Erik D. Demaine and Ferran Hurtado and John Iacono and Stefan Langerman and Pat Morin}, TITLE = {Geodesic Ham-Sandwich Cuts}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 37, NUMBER = 3, MONTH = {March}, YEAR = 2007, PAGES = {325--339}, length = {13 pages}, replaces = {GeodesicHamSandwich_SoCG2004}, papers = {GeodesicHamSandwich_SoCG2004}, comments = {This paper is also available from SpringerLink.}, } @InProceedings{SphereWrapping_EuroCG2007, AUTHOR = {Erik D. Demaine and Martin L. Demaine and John Iacono and Stefan Langerman}, TITLE = {Wrapping the {M}ozartkugel}, BOOKTITLE = {Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007)}, bookurl = {http://ewcg07.tugraz.at/}, ADDRESS = {Graz, Austria}, MONTH = {March 19--21}, YEAR = 2007, PAGES = {14--17}, papers = {SphereWrapping_CGTA}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, paperkind = {abstract}, length = {4 pages}, unrefereed = 1, } @InProceedings{Deflation_EuroCG2007, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Diane L. Souvaine and Perouz Taslakian}, TITLE = {Deflating The Pentagon}, BOOKTITLE = {Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007)}, bookurl = {http://ewcg07.tugraz.at/}, ADDRESS = {Graz, Austria}, MONTH = {March 19--21}, YEAR = 2007, PAGES = {10--13}, paperkind = {abstract}, length = {4 pages}, unrefereed = 1, papers = {Deflation_KyotoCGGT2007}, } @InProceedings{EuroCG2007i, AUTHOR = {Erik D. Demaine}, TITLE = {Computational Geometry through the Information Lens}, BOOKTITLE = {Abstracts from the 24th European Workshop on Computational Geometry (EuroCG 2007)}, bookurl = {http://ewcg07.tugraz.at/}, ADDRESS = {Graz, Austria}, MONTH = {March 19--21}, YEAR = 2007, PAGES = {81}, paperkind = {abstract}, length = {1 page}, unrefereed = 1 } @Article{GeneralGraphs_EJC, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Quickly Deciding Minor-Closed Parameters in General Graphs}, JOURNAL = {European Journal of Combinatorics}, journalurl = {http://www.elsevier.com/wps/product/cws_home/622824}, VOLUME = 28, NUMBER = 1, MONTH = {January}, YEAR = 2007, PAGES = {311--314}, comments = {This paper is also available from ScienceDirect.}, length = {4 pages}, withstudent = 1, } @InProceedings{ContractionTSP_SODA2007, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Bojan Mohar}, TITLE = {Approximation Algorithms via Contraction Decomposition}, BOOKTITLE = {Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)}, bookurl = {http://www.siam.org/meetings/da07/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 7--9}, YEAR = 2007, PAGES = {278--287}, papers = {ContractionTSP_Combinatorica}, } @InProceedings{Movement_SODA2007, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Amin S. Sayedi-Roshkhar and Shayan Oveisgharan and Morteza Zadimoghaddam}, TITLE = {Minimizing Movement}, BOOKTITLE = {Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)}, bookurl = {http://www.siam.org/meetings/da07/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 7--9}, YEAR = 2007, PAGES = {258--267}, papers = {Movement_TAlg}, } @Article{Embedding_DCG, AUTHOR = {Mihai B\u{a}doiu and Erik D. Demaine and MohammadTaghi Hajiaghayi and Piotr Indyk}, TITLE = {Low-Dimensional Embedding with Extra Information}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 36, NUMBER = 4, MONTH = {December}, YEAR = 2006, PAGES = {609--632}, NOTE = {Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry.}, length = {22 pages}, withstudent = 1, replaces = {Embedding_SoCG2004}, papers = {Embedding_SoCG2004}, comments = {This paper is also available from SpringerLink.}, } @Article{DynamicConnectivity_SICOMP, AUTHOR = {Mihai P\v{a}tra\c{s}cu and Erik D. Demaine}, TITLE = {Logarithmic Lower Bounds in the Cell-Probe Model}, JOURNAL = {SIAM Journal on Computing}, journalurl = {http://www.siam.org/journals/sicomp/sicomp.htm}, VOLUME = 35, NUMBER = 4, PAGES = {932--963}, YEAR = 2006, NOTE = {Special issue of selected papers from the 36th ACM Symposium on Theory of Computing, 2004.}, comments = {This paper is also available from SIAM. This paper is also available as arXiv:cs.DS/0502041 of the Computing Research Repository (CoRR).}, length = {32 pages}, withstudent = 1, replaces = {DynamicConnectivity_STOC2004; PartialSums_SODA2004}, papers = {DynamicConnectivity_STOC2004; PartialSums_SODA2004}, } @Article{BoundedGenus_SIDMA, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {The Bidimensional Theory of Bounded-Genus Graphs}, JOURNAL = {SIAM Journal on Discrete Mathematics}, journalurl = {http://www.siam.org/journals/sidma/sidma.htm}, VOLUME = 20, NUMBER = 2, YEAR = 2006, PAGES = {357--371}, comments = {This paper is also available from SIAM.}, withstudent = 1, replaces = {BoundedGenus_MFCS2004}, papers = {BoundedGenus_MFCS2004}, } @InProceedings{GridWagner_ISAAC2006, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and {W}agner's Contraction}, BOOKTITLE = {Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006)}, bookurl = {http://www.isical.ac.in/~isaac06}, VOLUME = 4288, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, ADDRESS = {Calcutta, India}, MONTH = {December 18--20}, YEAR = 2006, PAGES = {3--15}, papers = {GridWagner_Algorithmica}, copyright = {The paper is \copyright Springer-Verlag.}, award = {Awarded Best Paper. Invited to special issue of \emph{Algorithmica}.}, comments = {This paper is also available from SpringerLink.}, } @InProceedings{SupplyDemand_ISAAC2006, AUTHOR = {Takehiro Ito and Erik D. Demaine and Xiao Zhou and Takao Nishizeki}, TITLE = {Approximability for Partitioning Graphs with Supply and Demand}, BOOKTITLE = {Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006)}, bookurl = {http://www.isical.ac.in/~isaac06}, VOLUME = 4288, SERIES = {Lecture Notes in Computer Science}, seriesurl = {http://www.springer.de/comp/lncs/}, ADDRESS = {Calcutta, India}, MONTH = {December 18--20}, YEAR = 2006, PAGES = {121--130}, papers = {SupplyDemand_JDA}, copyright = {The paper is \copyright Springer-Verlag.}, comments = {This paper is also available from SpringerLink.}, } @InProceedings{ESA2006i, AUTHOR = {Erik D. Demaine}, TITLE = {Origami, Linkages, and Polyhedra: Folding with Algorithms}, BOOKTITLE = {Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006)}, bookurl = {http://algo06.inf.ethz.ch/esa}, ADDRESS = {Z\"urich, Switzerland}, MONTH = {September 11--13}, YEAR = 2006, PAGES = {1}, paperkind = {abstract}, length = {1 page}, unrefereed = 1, copyright = {Copyright held by the authors.}, comments = {This abstract is also available from SpringerLink.}, } @InProceedings{Necklace_ESA2006, AUTHOR = {David Bremner and Timothy M. Chan and Erik D. Demaine and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Perouz Taslakian}, TITLE = {Necklaces, Convolutions, and {$X+Y$}}, BOOKTITLE = {Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006)}, bookurl = {http://algo06.inf.ethz.ch/esa}, ADDRESS = {Z\"urich, Switzerland}, MONTH = {September 11--13}, YEAR = 2006, PAGES = {160--171}, copyright = {Copyright held by the authors.}, comments = {This paper is also available from SpringerLink.}, } @Article{SearchTurnCost_TCS, AUTHOR = {Erik D. Demaine and S{\'a}ndor P. Fekete and Shmuel Gal}, TITLE = {Online Searching with Turn Cost}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://www.elsevier.com/locate/tcs}, VOLUME = 361, NUMBER = {2--3}, MONTH = {September}, YEAR = 2006, PAGES = {342--355}, NOTE = {Special issue on approximation and online algorithms.}, COMMENTS = {This paper is also available as arXiv:cs.DS/0406045 of the Computing Research Repository (CoRR), and from ScienceDirect.}, } @Article{Clustering_TCS, AUTHOR = {Erik D. Demaine and Dotan Emanuel and Amos Fiat and Nicole Immorlica}, TITLE = {Correlation Clustering in General Weighted Graphs}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://www.elsevier.com/locate/tcs}, VOLUME = 361, NUMBER = {2--3}, MONTH = {September}, YEAR = 2006, PAGES = {172--187}, NOTE = {Special issue on approximation and online algorithms.}, length = {20 pages}, papers = {Clustering_APPROX2003}, replaces = {Clustering_APPROX2003}, withstudent = 1, comments = {This paper is also available from ScienceDirect.}, } @InProceedings{Sona_CCCG2006, AUTHOR = {Mirela Damian and Erik D. Demaine and Martin L. Demaine and Vida Dujmovi\'c and Dania El-Khechen and Robin Flatland and John Iacono and Stefan Langerman and Henk Meijer and Suneeta Ramaswami and Diane L. Souvaine and Perouz Taslakian and Godfried T. Toussaint}, TITLE = {Curves in the Sand: Algorithmic Drawing}, BOOKTITLE = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006)}, bookurl = {http://www.cs.queensu.ca/cccg/index.htm}, MONTH = {August 14--16}, YEAR = 2006, PAGES = {11--14}, length = {4 pages}, unrefereed = 1, category = {art}, } @InProceedings{Flips_CCCG2006, AUTHOR = {Erik D. Demaine and Blaise Gassend and Joseph O'Rourke and Godfried T. Toussaint}, TITLE = {Polygons Flip Finitely: Flaws and a Fix}, BOOKTITLE = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006)}, bookurl = {http://www.cs.queensu.ca/cccg/index.htm}, MONTH = {August 14--16}, YEAR = 2006, PAGES = {109--112}, length = {4 pages}, withstudent = 1, unrefereed = 1, papers = {Flips_DCG20}, } @InProceedings{CCCG2005Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2005}, BOOKTITLE = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006)}, bookurl = {http://www.cs.queensu.ca/cccg/index.htm}, MONTH = {August 14--16}, YEAR = 2006, PAGES = {75--80}, length = {6 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, unrefereed = 1 } @InProceedings{CCCG2006i, AUTHOR = {Erik D. Demaine}, TITLE = {Linkage Folding: From {E}rd\H{o}s to Proteins}, BOOKTITLE = {Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006)}, bookurl = {http://www.cs.queensu.ca/cccg/index.htm}, MONTH = {August 14--16}, YEAR = 2006, PAGES = {1}, paperkind = {abstract}, length = {1 page}, unrefereed = 1 } @InProceedings{Sona_BRIDGES2006, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Perouz Taslakian and Godfried T. Toussaint}, TITLE = {Sand Drawings and {G}aussian Graphs}, BOOKTITLE = {Proceedings of the 9th Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES 2006)}, ADDRESS = {London, England}, MONTH = {August 4--8}, YEAR = 2006, PAGES = {79--88}, length = {10 pages}, papers = {Sona_JMA}, category = {art}, } @Article{FUN2004i_TheoryComputSys, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Puzzles, Art, and Magic with Algorithms}, JOURNAL = {Theory of Computing Systems}, journalurl = {http://www.springerlink.com/openurl.asp?genre=journal&issn=1432-4350}, VOLUME = 39, NUMBER = 3, MONTH = {June}, YEAR = 2006, PAGES = {473--481}, NOTE = {Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.}, length = {10 pages}, papers = {FUN2004i}, replaces = {FUN2004i}, copyright = {Copyright held by the authors.}, comments = {This paper is also available from SpringerLink.}, category = {art}, } @Article{Morpion_TheoryComputSys, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Arthur Langerman and Stefan Langerman}, TITLE = {Morpion Solitaire}, JOURNAL = {Theory of Computing Systems}, journalurl = {http://www.springerlink.com/openurl.asp?genre=journal&issn=1432-4350}, VOLUME = 39, NUMBER = 3, MONTH = {June}, YEAR = 2006, PAGES = {439--453}, NOTE = {Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.}, updates = {Christian Boyer maintains the latest Morpion results on morpionsolitaire.com. In particular, it is now known that G3(A3) = 35 and that G′3(A3) = 62 (lower bounds in "New Heuristics for Morpion Solitaire" by Heikki Hyyrö and Timo Poranen, and upper bounds by enumeration by Michael Quist). There is also a new lower bound of G4(A4) ≥ 82 (by Tristan Cazenave), proposed upper bound of G4(A4) ≤ 138, and a new lower bound of G′4(A4) ≥ 172 (by Christopher Rosin, beating the previous 34-year-old record by Charles-Henri Bruneau)}, award = {Translated into Portuguese: ``Cinco-em-linha solit\'ario'', \emph{Boletim da Sociedade Portuguesa de Matem\'atica} 54:125--142, May 2006.}, length = {16 pages}, papers = {Morpion_FUN2004}, replaces = {Morpion_FUN2004}, copyright = {Copyright held by the authors.}, comments = {This paper is also available from SpringerLink.}, } @Article{HingedPolyforms3D_Leonardo, AUTHOR = {Erik D. Demaine and Martin L. Demaine and A. Laurie Palmer}, TITLE = {The Helium Stockpile: A Collaboration in Mathematical Folding Sculpture}, JOURNAL = {Leonardo}, journalurl = {http://www.leonardo.info/}, VOLUME = 39, NUMBER = 3, MONTH = {June}, YEAR = 2006, PAGES = {233--235}, also = {color plate on page 229}, comments = {This paper is also available from MIT Press.}, category = {art}, } @InProceedings{LockedShapes_SoCG2006, AUTHOR = {Robert Connelly and Erik D. Demaine and Martin L. Demaine and S\'andor Fekete and Stefan Langerman and Joseph S. B. Mitchell and Ares Rib\'o and G\"unter Rote}, TITLE = {Locked and Unlocked Chains of Planar Shapes}, BOOKTITLE = {Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006)}, bookurl = {http://www.cs.arizona.edu/~socg06/}, ADDRESS = {Sedona, Arizona}, MONTH = {June 5--7}, YEAR = 2006, PAGES = {61--70}, papers = {LockedShapes_DCG}, length = {10 pages}, comments = {This paper is also available as arXiv:cs.CG/0604022 of the Computing Research Repository (CoRR).}, } @InProceedings{PlaneEmbedding_SoCG2006, AUTHOR = {MohammadHossein Bateni and Erik D. Demaine and MohammadTaghi Hajiaghayi and Mohammad Moharrami}, TITLE = {Plane Embeddings of Planar Graph Metrics}, BOOKTITLE = {Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006)}, bookurl = {http://www.cs.arizona.edu/~socg06/}, ADDRESS = {Sedona, Arizona}, MONTH = {June 5--7}, YEAR = 2006, PAGES = {197--206}, length = {10 pages}, papers = {PlaneEmbedding_DCG}, } @InProceedings{Refolding_SoCG2006, AUTHOR = {Hayley N. Iben and James F. O'Brien and Erik D. Demaine}, TITLE = {Refolding Planar Polygons}, BOOKTITLE = {Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006)}, bookurl = {http://www.cs.arizona.edu/~socg06/}, ADDRESS = {Sedona, Arizona}, MONTH = {June 5--7}, YEAR = 2006, PAGES = {71--79}, award = {Invited to special issue of \emph{Discrete \& Computational Geometry}.}, comments = {See also animations of this algorithm.}, papers = {Refolding_DCG; Refolding_SIGGRAPH2004; ForceLinkage_SoCG2004} } @InProceedings{VoronoiGame_CIG2006, AUTHOR = {Sachio Teramoto and Erik Demaine and Ryuhei Uehara}, TITLE = {Voronoi game on graphs and its complexity}, BOOKTITLE = {Proceedings of the 2nd IEEE Symposium on Computational Intelligence and Games (CIG 2006)}, bookurl = {http://www.cse.unr.edu/~sushil/cig06/}, ADDRESS = {Reno, Nevada}, MONTH = {May 22--24}, YEAR = 2006, PAGES = {265--271}, } @InProceedings{PerfectHashing_LATIN2006, AUTHOR = {Erik D. Demaine and Friedhelm {Meyer auf der Heide} and Rasmus Pagh and Mihai P\v{a}tra\c{s}cu}, TITLE = {De Dictionariis Dynamicis Pauco Spatio Utentibus (\emph{lat.} On Dynamic Dictionaries Using Little Space)}, BOOKTITLE = {Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006)}, bookurl = {http://www.latin06.org/}, ADDRESS = {Valdivia, Chile}, MONTH = {March 20--24}, YEAR = 2006, PAGES = {349--361}, withstudent = 1, length = {12 pages}, papers = {PerfectHashing_Manuscript}, } @InProceedings{DynamicVoronoi_LATIN2006, AUTHOR = {Boris Aronov and Prosenjit Bose and Erik D. Demaine and Joachim Gudmundsson and John Iacono and Stefan Langerman and Michiel Smid}, TITLE = {Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams}, BOOKTITLE = {Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006)}, bookurl = {http://www.latin06.org/}, ADDRESS = {Valdivia, Chile}, MONTH = {March 20--24}, YEAR = 2006, PAGES = {80--92}, copyright = {Copyright held by the authors.}, length = {12 pages}, papers = {DynamicVoronoi_Manuscript; DynamicVoronoi_CGW2005}, replaces = {DynamicVoronoi_CGW2005}, } @InProceedings{Integration_LATIN2006, AUTHOR = {Ilya Baran and Erik D. Demaine and Dmitriy A. Katz}, TITLE = {Optimally Adaptive Integration of Univariate {L}ipschitz Functions}, BOOKTITLE = {Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006)}, bookurl = {http://www.latin06.org/}, ADDRESS = {Valdivia, Chile}, MONTH = {March 20--24}, YEAR = 2006, PAGES = {142--153}, award = {Invited to special issue of \emph{Algorithmica}.}, withstudent = 1, papers = {Integration_Algorithmica}, } @Article{ProteinMachine_Algorithmica, AUTHOR = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke}, TITLE = {Geometric Restrictions on Producible Polygonal Protein Chains}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 44, NUMBER = 2, MONTH = {February}, YEAR = 2006, PAGES = {167--181}, NOTE = {Special issue of selected papers from the 14th Annual International Symposium on Algorithms and Computation, 2003.}, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, length = {17 pages}, papers = {ProteinMachine_ISAAC2003}, replaces = {ProteinMachine_ISAAC2003}, } @InProceedings{UniqueCoverage_SODA2006, AUTHOR = {Erik D. Demaine and Uriel Feige and MohammadTaghi Hajiaghayi and Mohammad R. Salavatipour}, TITLE = {Combination Can Be Hard: Approximability of the Unique Coverage Problem}, BOOKTITLE = {Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006)}, bookurl = {http://www.siam.org/meetings/da06/}, ADDRESS = {Miami, Florida}, MONTH = {January 22--24}, YEAR = 2006, PAGES = {162--171}, withstudent = 1, papers = {UniqueCoverage_SICOMP} } @InProceedings{SourceCoding_SODA2006, AUTHOR = {Micah Adler and Erik D. Demaine and Nicholas J. A. Harvey and Mihai P\v{a}tra\c{s}cu}, TITLE = {Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding}, BOOKTITLE = {Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006)}, bookurl = {http://www.siam.org/meetings/da06/}, ADDRESS = {Miami, Florida}, MONTH = {January 22--24}, YEAR = 2006, PAGES = {251--260}, withstudent = 1, } @Article{HMinorFree_JACM, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Subexponential parameterized algorithms on graphs of bounded-genus and $H$-minor-free graphs}, JOURNAL = {Journal of the ACM}, journalurl = {http://www.acm.org/jacm/}, VOLUME = 52, NUMBER = 6, YEAR = 2005, PAGES = {866--893}, length = {26 pages}, withstudent = 1, replaces = {HMinorFree_SODA2004}, papers = {HMinorFree_SODA2004}, comments = {This paper is also available from the ACM Digital Library.}, } @Article{Curves_IJCGA, AUTHOR = {Ilya Baran and Erik D. Demaine}, TITLE = {Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve}, JOURNAL = {International Journal of Computational Geometry and Applications}, journalurl = {http://www.worldscinet.com/ijcga/ijcga.shtml}, VOLUME = 15, NUMBER = 4, YEAR = 2005, PAGES = {327--350}, NOTE = {Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.}, length = {24 pages}, papers = {Curves_SoCG2004}, replaces = {Curves_SoCG2004}, comments = {This paper is also available from WorldSciNet. This paper is also available as arXiv:cs.CG/0307005 of the Computing Research Repository (CoRR).}, withstudent = 1, } @Article{Milling, 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}, JOURNAL = {SIAM Journal on Computing}, VOLUME = 35, NUMBER = 3, YEAR = {2005}, PAGES = {531--566}, length = {36 pages}, papers = {SODA2001a}, replaces = {SODA2001a}, comments = {This paper is also available from SIAM. This paper is also available as arXiv:cs.DS/0309014 of the Computing Research Repository (CoRR).}, } @Article{CacheObliviousBTrees_SICOMP, AUTHOR = {Michael A. Bender and Erik D. Demaine and Martin Farach-Colton}, TITLE = {Cache-Oblivious B-Trees}, JOURNAL = {SIAM Journal on Computing}, journalurl = {http://www.siam.org/journals/sicomp/sicomp.htm}, VOLUME = 35, NUMBER = 2, YEAR = 2005, PAGES = {341--358}, comments = {This paper is also available from SIAM.}, papers = {FOCS2000b}, replaces = {FOCS2000b}, length = {19 pages}, } @Article{MaryTrees_Algorithmica, AUTHOR = {David Benoit and Erik D. Demaine and J. Ian Munro and Rajeev Raman and Venkatesh Raman and S. Srinivasa Rao}, TITLE = {Representing Trees of Higher Degree}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 43, NUMBER = 4, MONTH = {December}, YEAR = 2005, PAGES = {275--292}, comments = {This paper is also available from SpringerLink.}, length = {24 pages}, replaces = {MaryTrees_WADS99} } @Misc{PerfectHashing_Manuscript, AUTHOR = {Erik D. Demaine and Friedhelm {Meyer auf der Heide} and Rasmus Pagh and Mihai P\v{a}tra\c{s}cu}, TITLE = {De Dictionariis Dynamicis Pauco Spatio Utentibus (\emph{lat.} On Dynamic Dictionaries Using Little Space)}, HOWPUBLISHED = {Manuscript}, MONTH = {December}, YEAR = 2005, withstudent = 1, length = {14 pages}, papers = {PerfectHashing_LATIN2006}, comments = {This paper is also available as arXiv:cs.DS/0512081 of the Computing Research Repository (CoRR).}, } @Misc{DynamicVoronoi_Manuscript, AUTHOR = {Boris Aronov and Prosenjit Bose and Erik D. Demaine and Joachim Gudmundsson and John Iacono and Stefan Langerman and Michiel Smid}, TITLE = {Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams}, HOWPUBLISHED = {Manuscript}, MONTH = {December}, YEAR = 2005, papers = {DynamicVoronoi_LATIN2006; DynamicVoronoi_CGW2005}, length = {15 pages}, comments = {This paper is also available as arXiv:cs.CG/0512091 of the Computing Research Repository (CoRR).}, } @InProceedings{DynamicVoronoi_CGW2005, AUTHOR = {Boris Aronov and Prosenjit Bose and Erik D. Demaine and Joachim Gudmundsson and John Iacono and Stefan Langerman and Michiel Smid}, TITLE = {Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams}, BOOKTITLE = {Abstracts from the 15th Annual Fall Workshop on Computational Geometry}, bookurl = {http://www.cs.utah.edu/~suresh/fwcg05/}, ADDRESS = {Philadelphia, Pennsylvania}, MONTH = {November 18--19}, YEAR = 2005, PAGES = {51--52}, papers = {DynamicVoronoi_LATIN2006; DynamicVoronoi_Manuscript}, paperkind = {abstract}, length = {2 pages}, unrefereed = 1, } @InProceedings{NanoEnergy_ASME2005, AUTHOR = {Paul Stellman and Will Arora and Satoshi Takahashi and Erik D. Demaine and George Barbastathis}, TITLE = {Kinematics and Dynamics of Nanostructured Origami}, BOOKTITLE = {Proceedings of the ASME International Mechanical Engineering Congress and Exposition}, bookurl = {http://www.asmeconferences.org/congress05/}, ADDRESS = {Orlando, Florida}, MONTH = {November 5--11}, YEAR = 2005, PAGES = {541--548}, also = {Paper IMECE2005-81824.}, withstudent = 1, length = {8 pages}, } @InProceedings{NanoEnergy_ISNM2005, AUTHOR = {Paul Stellman and Will Arora and Satoshi Takahashi and Erik D. Demaine and George Barbastathis}, TITLE = {Design and Control of Nanostructured Origami}, BOOKTITLE = {Proceedings of the 3rd International Symposium on Nanomanufacturing}, bookurl = {http://www.isnm2005.org/EN/}, ADDRESS = {Orlando, Florida}, MONTH = {November 3--5}, YEAR = 2005, also = {Poster TAP2.}, pages = {4}, paperkind = {poster}, withstudent = 1, poster = 1, } @Article{NCL_TCS, AUTHOR = {Robert A. Hearn and Erik D. Demaine}, TITLE = {{PSPACE}-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 343, NUMBER = {1--2}, MONTH = {October}, YEAR = 2005, PAGES = {72--96}, NOTE = {Special issue ``Game Theory Meets Theoretical Computer Science''.}, papers = {NCL_ICALP2002; CL_Complexity2008}, updates = {Ivars Peterson wrote an article describing these results, “Logic in the Blocks”, Science News 162(7):106-108, August 17, 2002.}, comments = {This paper is also available as arXiv:cs.CC/0205005 of the Computing Research Repository (CoRR), and from ScienceDirect.}, replaces = {NCL_ICALP2002}, withstudent = 1 } @InProceedings{PersiFS_SOSP2005, AUTHOR = {Dan R. K. Ports and Austin T. Clements and Erik D. Demaine}, TITLE = {{PersiFS}: A Versioned File System with an Efficient Representation}, BOOKTITLE = {Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP 2005)}, bookurl = {http://www.sosp-20.com/}, ADDRESS = {Brighton, United Kingdom}, MONTH = {October 23--26}, YEAR = 2005, withstudent = 1, length = {1 page}, paperkind = {poster abstract}, comments = {The poster and abstract is available from the ACM Digital Library.}, poster = 1, } % xxx PAGES = {to appear}, @InProceedings{Decomposition_FOCS2005, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi}, TITLE = {Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring}, BOOKTITLE = {Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005)}, bookurl = {http://www.cs.cornell.edu/Research/focs05/}, ADDRESS = {Pittsburgh, PA}, MONTH = {October 23--25}, YEAR = 2005, PAGES = {637--646}, withstudent = 1, length = {10 pages}, } @InProceedings{UnimodalOptimization_ESA2005, AUTHOR = {Erik D. Demaine and Stefan Langerman}, TITLE = {Optimizing a {2D} Function Satisfying Unimodality Properties}, BOOKTITLE = {Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005)}, bookurl = {http://www.lsi.upc.es/~esa05/}, ADDRESS = {Mallorca, Spain}, MONTH = {October 3--6}, YEAR = 2005, PAGES = {887--898}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 3669, comments = {This paper is also available from SpringerLink.}, copyright = {Copyright held by the authors.}, length = {12 pages}, papers = {UnimodalOptimization_EuroCG2004}, } @Article{TriangulationGames_TCS, 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 = {Games on Triangulations}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 343, NUMBER = {1--2}, MONTH = {October}, YEAR = 2005, PAGES = {42--71}, NOTE = {Special issue ``Game Theory Meets Theoretical Computer Science''.}, papers = {TriangulationGames_JCDCG2002; TriangulationGames_EuroCG2003}, length = {32 pages}, replaces = {TriangulationGames_JCDCG2002; TriangulationGames_EuroCG2003}, comments = {This paper is also available from ScienceDirect.}, } @InProceedings{Contour_AWOCA2005, AUTHOR = {Erik Demaine and Jeff Erickson and Danny Krizan\'c and Henk Meijer and Pat Morin and Mark Overmars and Sue Whitesides}, TITLE = {Realizing Partitions Respecting Full and Partial Order Information}, BOOKTITLE = {Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)}, bookurl = {http://www.ballarat.edu.au/conferences/awoca2005/}, ADDRESS = {Victoria, Australia}, MONTH = {September 18--21}, YEAR = 2005, PAGES = {105--114}, award = {Invited to special issue of \emph{Journal of Discrete Algorithms}.}, length = {9 pages}, papers = {Contour_JDA}, } @Article{ChordSeparation_IJCGA, AUTHOR = {Erik D. Demaine and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Henk Meijer and Mark Overmars and Sue Whitesides}, TITLE = {Separating point sets in polygonal environments}, JOURNAL = {International Journal of Computational Geometry and Applications}, journalurl = {http://www.worldscinet.com/ijcga/ijcga.shtml}, VOLUME = 15, NUMBER = 4, MONTH = {August}, YEAR = {2005}, PAGES = {403--419}, NOTE = {Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.}, comments = {This paper is also available from WorldSciNet.}, length = {16 pages}, papers = {ChordSeparation_SoCG2004}, replaces = {ChordSeparation_SoCG2004}, } @InCollection{FUCG_MSRI, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {A Survey of Folding and Unfolding in Computational Geometry}, BOOKTITLE = {Combinatorial and Computational Geometry}, bookurl = {http://www.cambridge.org/us/catalogue/catalogue.asp?isbn=0521848628}, EDITOR = {Jacob E. Goodman and J\'anos Pach and Emo Welzl}, VOLUME = 52, SERIES = {Mathematical Sciences Research Institute Publications}, PUBLISHER = {Cambridge University Press}, MONTH = {August}, YEAR = 2005, PAGES = {167--211}, length = {46 pages} } @InProceedings{MinAvgDistance_WADS2005, AUTHOR = {Michael A. Bender and David P. Bunde and Erik D. Demaine and S{\'a}ndor P. Fekete and Vitus J. Leung and Henk Meijer and Cynthia A. Phillips}, TITLE = {Communication-Aware Processor Allocation for Supercomputers}, BOOKTITLE = {Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005)}, bookurl = {http://www.wads.org/}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 15--17}, YEAR = 2005, PAGES = {169--181}, VOLUME = 3608, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, award = {Invited to special issue of \emph{Algorithmica}.}, copyright = {The paper is \copyright Springer-Verlag.}, papers = {MinAvgDistance_Algorithmica; MinAvgDistance_CCCG2009; MinAvgDistance_JPhysA}, comments = {This paper is also available as arXiv:cs.DS/0407058 of the Computing Research Repository (CoRR), and from SpringerLink.}, } @InProceedings{3SUM_WADS2005, AUTHOR = {Ilya Baran and Erik D. Demaine and Mihai P\v{a}tra\c{s}cu}, TITLE = {Subquadratic Algorithms for {3SUM}}, BOOKTITLE = {Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005)}, bookurl = {http://www.wads.org/}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 15--17}, YEAR = 2005, PAGES = {409--421}, VOLUME = 3608, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, award = {Invited to special issue of \emph{Algorithmica}.}, comments = {This paper is also available from SpringerLink.}, copyright = {The paper is \copyright Springer-Verlag.}, withstudent = 1, updates = {The proceedings version lists incorrect page numbers for reference [5].}, papers = {3SUM_Algorithmica}, } @InProceedings{HingedPolyforms3D_WADS2005, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Jeffrey F. Lindy and Diane L. Souvaine}, TITLE = {Hinged Dissection of Polypolyhedra}, BOOKTITLE = {Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005)}, bookurl = {http://www.wads.org/}, ADDRESS = {Waterloo, Ontario, Canada}, MONTH = {August 15--17}, YEAR = 2005, PAGES = {205--217}, VOLUME = 3608, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, papers = {HingedPolyforms3D_CGW2004; HingedPolyforms}, replaces = {HingedPolyforms3D_CGW2004}, COMMENTS = {This paper is also available from SpringerLink.}, } @InProceedings{CCCG2004Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2004}, BOOKTITLE = {Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005)}, bookurl = {http://cccg.cs.uwindsor.ca/}, ADDRESS = {Windsor, Ontario, Canada}, MONTH = {August 10--12}, YEAR = 2005, PAGES = {303--306}, length = {4 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, unrefereed = 1 } @InProceedings{DynamicHamSandwich_CCCG2005, AUTHOR = {Timothy Abbott and Erik D. Demaine and Martin L. Demaine and Daniel Kane and Stefan Langerman and Jelani Nelson and Vincent Yeung}, TITLE = {Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane}, BOOKTITLE = {Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005)}, bookurl = {http://cccg.cs.uwindsor.ca/}, ADDRESS = {Windsor, Ontario, Canada}, MONTH = {August 10--12}, YEAR = 2005, PAGES = {61--64}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, length = {4 pages}, withstudent = 1, unrefereed = 1, papers = {DynamicHamSandwich_CGTA} } @InProceedings{DeepRhythms_CCCG2005, AUTHOR = {Erik D. Demaine and Francisco Gomez-Martin and Henk Meijer and David Rappaport and Perouz Taslakian and Godfried T. Toussaint and Terry Winograd and David R. Wood}, TITLE = {The Distance Geometry of Deep Rhythms and Scales}, BOOKTITLE = {Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005)}, bookurl = {http://cccg.cs.uwindsor.ca/}, ADDRESS = {Windsor, Ontario, Canada}, MONTH = {August 10--12}, YEAR = 2005, PAGES = {163--166}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, papers = {DeepRhythms_CGTA}, length = {4 pages}, unrefereed = 1, category = {art}, } @Article{MapGraphs_TAlg, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Fixed-Parameter Algorithms for $(k,r)$-Center in Planar Graphs and Map Graphs}, JOURNAL = {ACM Transactions on Algorithms}, journalurl = {http://www.acm.org/talg/}, VOLUME = 1, NUMBER = 1, MONTH = {July}, YEAR = {2005}, PAGES = {33--47}, comments = {This paper is also available from the ACM Digital Library.}, papers = {MapGraphs_ICALP2003}, replaces = {MapGraphs_ICALP2003}, withstudent = 1 } @Article{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}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 31, NUMBER = 3, MONTH = {June}, YEAR = 2005, PAGES = {237--262}, NOTE = {Special issue of selected papers from the 11th Canadian Conference on Computational Geometry, 1999.}, length = {27 pages}, comments = {This paper is also available as arXiv:cs.CG/9907018 of the Computing Research Repository (CoRR). The paper is also available from ScienceDirect.}, papers = {CCCG99a}, replaces = {CCCG99a}, } @InProceedings{Sensor_MOBIHOC2005, AUTHOR = {Jonathan L. Bredin and Erik D. Demaine and MohammadTaghi Hajiaghayi and Daniela Rus}, TITLE = {Deploying Sensor Networks with Guaranteed Capacity and Fault Tolerance}, BOOKTITLE = {Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2005)}, bookurl = {http://www.sigmobile.org/mobihoc/2005/}, ADDRESS = {Urbana-Champaign, Illinois}, MONTH = {May 25--28}, YEAR = 2005, PAGES = {309--319}, length = {11 pages}, withstudent = 1, papers = {Sensor_TON}, } @Article{VoronoiBoundary_DCG, AUTHOR = {David Bremner and Erik Demaine and Jeff Erickson and John Iacono and Stefan Langerman and Pat Morin and Godfried Toussaint}, TITLE = {Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries}, JOURNAL = {Discrete \& Computational Geometry}, journalurl = {http://link.springer.de/link/service/journals/00454/}, VOLUME = 33, NUMBER = 4, PAGES = {593--604}, YEAR = 2005, MONTH = {April}, COMMENTS = {This paper is also available from SpringerLink.}, PAPERS = {VoronoiBoundary_WADS2003}, replaces = {VoronoiBoundary_WADS2003}, } @Article{Buddy_ActaInf, AUTHOR = {Gerth St{\o}lting Brodal and Erik D. Demaine and J. Ian Munro}, TITLE = {Fast Allocation and Deallocation with an Improved Buddy System}, JOURNAL = {Acta Informatica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0001-5903}, VOLUME = 41, NUMBER = {4--5}, MONTH = {March}, YEAR = 2005, PAGES = {273--291}, papers = {Buddy_FSTTCS99}, length = {16 pages}, comments = {This paper is also available from SpringerLink.}, replaces = {Buddy_FSTTCS99}, } @InProceedings{MobileAssist_INFOCOM2005, AUTHOR = {Nissanka B. Priyantha and Hari Balakrishnan and Erik D. Demaine and Seth Teller}, TITLE = {Mobile-Assisted Localization in Wireless Sensor Networks}, BOOKTITLE = {Proceedings of the 24th Annual Joint Conference of the IEEE Communications Society on Computer Communications (INFOCOM 2005)}, bookurl = {http://www.ieee-infocom.org/2005}, VOLUME = 1, ADDRESS = {Miami, Florida}, MONTH = {March 13--17}, YEAR = 2005, PAGES = {172--183}, withstudent = 1, length = {12 pages}, comments = {This paper is also available from IEEE Xplore.}, updates = {Proposition 2 should additionally state that n0 and n1 are known to be on the same side of the line through m0, m1, and m2.} } @Misc{MapGraphGridMinors_Manuscript, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Bidimensionality, Map Graphs, and Grid Minors}, HOWPUBLISHED = {Manuscript}, MONTH = {February}, YEAR = 2005, comments = {This paper is also available as arXiv:cs.DM/0502070 of the Computing Research Repository (CoRR).}, length = {12 pages}, withstudent = 1, } @Article{CliqueSum_Algorithmica, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 41, NUMBER = 4, MONTH = {February}, YEAR = 2005, PAGES = {245--267}, COMMENTS = {This paper is also available from SpringerLink.}, PAPERS = {CliqueSum_ISAAC2002}, replaces = {CliqueSum_ISAAC2002}, withstudent = 1 } @Article{ExcludedSums_SIAMNews, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Alan Edelman and Charles E. Leiserson and Per-Olof Persson}, TITLE = {Building Blocks and Excluded Sums}, JOURNAL = {SIAM News}, journalurl = {http://www.siam.org/news/}, VOLUME = 38, NUMBER = 1, MONTH = {January}, YEAR = 2005, PAGES = {1, 4, 6}, unrefereed = 1 } @InProceedings{GenApprox_SODA2005, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Bidimensionality: New Connections between FPT Algorithms and PTASs}, BOOKTITLE = {Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)}, bookurl = {http://www.siam.org/meetings/DA05/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {January 23--25}, YEAR = 2005, PAGES = {590--601}, withstudent = 1, length = {12 pages}, } @InProceedings{GridMinors_SODA2005, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality}, BOOKTITLE = {Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)}, bookurl = {http://www.siam.org/meetings/DA05/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {January 23--25}, YEAR = 2005, PAGES = {682--689}, withstudent = 1, length = {8 pages}, papers = {GridMinors_Combinatorica} } @InProceedings{Ordinal_SODA2005, AUTHOR = {Noga Alon and Mihai B\u{a}doiu and Erik D. Demaine and Martin Farach-Colton and MohammadTaghi Hajiaghayi and Anastasios Sidiropoulos}, TITLE = {Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics}, BOOKTITLE = {Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)}, bookurl = {http://www.siam.org/meetings/DA05/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {January 23--25}, YEAR = 2005, PAGES = {650--659}, withstudent = 1, length = {10 pages}, papers = {Ordinal_TAlg; Ordinal_APPROX2008}, } @InCollection{TreeMaker_OSME2006, AUTHOR = {Robert J. Lang and Erik D. Demaine}, TITLE = {Facet Ordering and Crease Assignment in Uniaxial Bases}, BOOKTITLE = {Origami$^4$: Proceedings of the 4th International Meeting of Origami Science, Math, and Education (OSME 2006)}, bookurl = {http://www.langorigami.com/science/4osme/4osme.php4}, ADDRESS = {Pasadena, California}, MONTH = {September 8--10}, YEAR = 2006, PAGES = {189--205}, PUBLISHER = {A K Peters}, } @InCollection{PaperBag_OSME2006, AUTHOR = {Devin J. Balkcom and Erik D. Demaine and Martin L. Demaine and John A. Ochsendorf and Zhong You}, TITLE = {Folding Paper Shopping Bags}, BOOKTITLE = {Origami$^4$: Proceedings of the 4th International Meeting of Origami Science, Math, and Education (OSME 2006)}, bookurl = {http://www.langorigami.com/science/4osme/4osme.php4}, ADDRESS = {Pasadena, California}, MONTH = {September 8--10}, YEAR = 2006, PAGES = {315--334}, PUBLISHER = {A K Peters}, replaces = {PaperBag_CGW2004}, papers = {PaperBag_CGW2004}, } @Article{Tetris_IJCGA, AUTHOR = {Ron Breukelaar and Erik D. Demaine and Susan Hohenberger and Hendrik Jan Hoogeboom and Walter A. Kosters and David Liben-Nowell}, TITLE = {Tetris is Hard, Even to Approximate}, JOURNAL = {International Journal of Computational Geometry and Applications}, journalurl = {http://www.worldscinet.com/ijcga/ijcga.shtml}, VOLUME = 14, NUMBER = {1--2}, YEAR = 2004, PAGES = {41--68}, length = {28 pages}, papers = {Tetris_COCOON2003; Tetris_CGW2002; Tetris_TR2002}, comments = {This paper is also available from WorldSciNet.}, 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.}, replaces = {Tetris_COCOON2003; Tetris_CGW2002}, withstudent = 1 } @Article{Bidimensional_SIDMA, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Bidimensional Parameters and Local Treewidth}, JOURNAL = {SIAM Journal on Discrete Mathematics}, journalurl = {http://www.siam.org/journals/sidma/sidma.htm}, VOLUME = 18, NUMBER = 3, PAGES = {501--511}, YEAR = 2004, COMMENTS = {This paper is also available from SIAM.}, PAPERS = {Bidimensional_LATIN2004}, replaces = {Bidimensional_LATIN2004}, withstudent = 1 } @InProceedings{ISAAC2004i, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Puzzles, Art, and Magic with Algorithms}, BOOKTITLE = {Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004)}, ADDRESS = {Hong Kong, China}, VOLUME = 3341, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, PAGES = {1}, YEAR = 2004, copyright = {The abstract is \copyright Springer-Verlag.}, papers = {FUN2004_TheoryComputSys; FUN2004i}, paperkind = {abstract}, length = {1 page}, unrefereed = 1, category = {art}, } @Article{FunSort_DAM, AUTHOR = {Therese Biedl and Timothy Chan and Erik D. Demaine and Rudolf Fleischer and Mordecai Golin and James A. King and J. Ian Munro}, TITLE = {{F}un-{S}ort---or the Chaos of Unordered Binary Search}, JOURNAL = {Discrete Applied Mathematics}, JOURNALURL = {http://www.elsevier.com/locate/dam}, VOLUME = 144, NUMBER = 3, MONTH = {December}, YEAR = 2004, PAGES = {231--236}, comments = {This paper is also available from ScienceDirect.}, length = {10 pages}, papers = {FUN2001; FunSort_TR2001}, replaces = {FUN2001}, } @Book{Gardner5, EDITOR = {Barry Cipra and Erik D. Demaine and Martin L. Demaine and Tom Rodgers}, TITLE = {Tribute to a Mathemagician}, PUBLISHER = {A~K~Peters}, publisherurl = {http://www.akpeters.com/}, MONTH = {November}, YEAR = 2004, length = {262 pages}, comments = {See the publisher's webpage for this book.   }, availability = {Available for purchase from the publisher or Amazon.}, papers = {SlidingCoins_G4G5; FoldCut_G4G5; Gardner90} } @InCollection{SlidingCoins_G4G5, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Sliding-Coin Puzzles}, BOOKTITLE = {Tribute to a Mathemagician}, PUBLISHER = {A~K~Peters}, publisherurl = {http://www.akpeters.com/}, YEAR = 2004, PAGES = {63--72}, length = {7 pages}, papers = {GameTheory2000; FoldCut_G4G5; Gardner5}, comments = {See also the publisher's webpage for this book.} } @InCollection{FoldCut_G4G5, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Fold-and-Cut Magic}, BOOKTITLE = {Tribute to a Mathemagician}, PUBLISHER = {A~K~Peters}, publisherurl = {http://www.akpeters.com/}, YEAR = 2004, PAGES = {23--30}, length = {6 pages}, papers = {JCDCG98; SlidingCoins_G4G5; Gardner5}, comments = {See also the publisher's webpage for this book.} } @InProceedings{HingedPolyforms3D_CGW2004, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Jeffrey F. Lindy and Diane L. Souvaine}, TITLE = {Hinged Dissection of Polypolyhedra}, BOOKTITLE = {Abstracts from the 14th Annual Fall Workshop on Computational Geometry}, bookurl = {http://cgw2004.csail.mit.edu/}, ADDRESS = {Cambridge, Massachusetts}, MONTH = {November 19--20}, YEAR = 2004, PAGES = {16--17}, length = {2 pages}, papers = {HingedPolyforms3D_WADS2005; HingedPolyforms}, unrefereed = 1, } @InProceedings{PaperBag_CGW2004, AUTHOR = {Devin J. Balkcom and Erik D. Demaine and Martin L. Demaine}, TITLE = {Folding Paper Shopping Bags}, BOOKTITLE = {Abstracts from the 14th Annual Fall Workshop on Computational Geometry}, bookurl = {http://cgw2004.csail.mit.edu/}, ADDRESS = {Cambridge, Massachusetts}, MONTH = {November 19--20}, YEAR = 2004, PAGES = {14--15}, length = {2 pages}, unrefereed = 1, papers = {PaperBag_OSME2006}, } @InProceedings{EpiChord_ICON2004, AUTHOR = {Ben Leong and Barbara Liskov and Erik Demaine}, TITLE = {{EpiChord}: Parallelizing the {C}hord Lookup Algorithm with Reactive Routing State Management}, BOOKTITLE = {Proceedings of the IEEE International Conference on Networks (ICON 2004)}, bookurl = {http://www.sp.edu.sg/icon2004/}, VOLUME = 1, ADDRESS = {Singapore}, MONTH = {November 16--19}, YEAR = 2004, PAGES = {270--276}, award = {Awarded Best Paper.}, comments = {This paper is also avilable from IEEE Xplore.}, withstudent = 1, length = {7 pages}, } @InProceedings{Tango_FOCS2004, AUTHOR = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai P\v{a}tra\c{s}cu}, TITLE = {Dynamic Optimality---Almost}, BOOKTITLE = {Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004)}, bookurl = {http://www.dis.uniroma1.it/~focs04/}, ADDRESS = {Rome, Italy}, MONTH = {October 17--19}, YEAR = 2004, PAGES = {484--490}, award = {Invited to special issue of \emph{SIAM Journal on Computing}.}, length = {7 pages}, withstudent = 1, papers = {Tango_SICOMP}, } @InProceedings{Orthoballs_JCDCG2004, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Grid Vertex-Unfolding Orthostacks}, BOOKTITLE = {Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2004)}, bookurl = {http://www.ried.tokai.ac.jp/JCDCG/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 3742, ADDRESS = {Tokyo, Japan}, MONTH = {October 8--11}, YEAR = 2004, PAGES = {76--82}, COPYRIGHT = {Copyright held by the authors.}, COMMENTS = {This paper is also available from SpringerLink.}, length = {7 pages} } @InProceedings{BidimensionalSurvey_GD2004, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth}, BOOKTITLE = {Proceedings of the 12th International Symposium on Graph Drawing (GD 2004)}, bookurl = {http://www.gd2004.org/}, VOLUME = 3383, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, ADDRESS = {Harlem, New York}, MONTH = {September 29--October 2}, YEAR = 2004, PAGES = {517--533}, copyright = {The paper is \copyright Springer-Verlag.}, comments = {This paper is also available from SpringerLink.}, withstudent = 1, length = {17 pages}, papers = {BidimensionalSurvey_CJ}, } @Article{CliqueSum_JCSS, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Naomi Nishimura and Prabhakar Ragde and Dimitrios M. Thilikos}, TITLE = {Approximation algorithms for classes of graphs excluding single-crossing graphs as minors}, JOURNAL = {Journal of Computer and System Sciences}, journalurl = {http://www.elsevier.com/locate/issn/00220000}, VOLUME = 69, NUMBER = 2, YEAR = 2004, PAGES = {166--195}, MONTH = {September}, COMMENTS = {This paper is also available from ScienceDirect.}, PAPERS = {CliqueSum_APPROX2002}, replaces = {CliqueSum_APPROX2002}, withstudent = 1, length = {30 pages}, } @Article{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?}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 29, NUMBER = 1, MONTH = {September}, YEAR = 2004, PAGES = {23--46}, NOTE = {Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.}, LENGTH = {24 pages}, COMMENTS = {This paper is also available from ScienceDirect, and 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.}, replaces = {MapFoldingWADS2001; CGW2000}, } @Article{DivisiblePair_SIGSAM, AUTHOR = {Stelian Ciurea and Erik D. Demaine and Corina E. P\v{a}tra\c{s}cu and Mihai P\v{a}tra\c{s}cu}, TITLE = {Finding a Divisible Pair}, JOURNAL = {ACM SIGSAM Bulletin}, VOLUME = 38, NUMBER = 3, MONTH = {September}, YEAR = 2004, PAGES = {98--100}, papers = {Yogi_FUN2004}, length = {2 pages}, withstudent = 1, unrefereed = 1 } @Article{MatchingBounds_DM, 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}, JOURNAL = {Discrete Mathematics}, journalurl = {http://www.elsevier.com/locate/disc}, VOLUME = 285, NUMBER = {1--3}, PAGES = {7--15}, MONTH = {August}, YEAR = 2004, COMMENTS = {This paper is also available from ScienceDirect.}, PAPERS = {MatchingBounds_ISAAC2001}, replaces = {MatchingBounds_ISAAC2001}, } @Article{DiameterTreewidth_Algorithmica, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Diameter and Treewidth in Minor-Closed Graph Families, Revisited}, JOURNAL = {Algorithmica}, journalurl = {http://springerlink.metapress.com/openurl.asp?genre=journal&issn=0178-4617}, VOLUME = 40, NUMBER = 3, MONTH = {August}, YEAR = 2004, PAGES = {211--215}, LENGTH = {5 pages}, COMMENTS = {This paper is also available from SpringerLink.}, withstudent = 1 } @InProceedings{BoundedGenus_MFCS2004, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {The Bidimensional Theory of Bounded-Genus Graphs}, BOOKTITLE = {Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004)}, ADDRESS = {Prague, Czech Republic}, PAGES = {191--203}, MONTH = {August 22--27}, YEAR = 2004, length = {12 pages}, withstudent = 1, papers = {BoundedGenus_SIDMA}, } @InProceedings{PaperReachability_CCCG2004, AUTHOR = {Erik D. Demaine and Satyan L. Devadoss and Joseph S. B. Mitchell and Joseph O'Rourke}, TITLE = {Continuous Foldability of Polygonal Paper}, BOOKTITLE = {Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004)}, bookurl = {http://www.cs.concordia.ca/cccg/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 9--11}, YEAR = 2004, PAGES = {64--67}, comments = {This paper is also available from the electronic proceedings as http://www.cs.concordia.ca/cccg/papers/55.pdf.}, length = {4 pages}, papers = {PaperReachability_CCCG2001}, unrefereed = 1 } @InProceedings{BandUnfolding_CCCG2004, AUTHOR = {Greg Aloupis and Erik D. Demaine and Stefan Langerman and Pat Morin and Joseph O'Rourke and Ileana Streinu and Godfried Toussaint}, TITLE = {Unfolding Polyhedral Bands}, BOOKTITLE = {Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004)}, bookurl = {http://www.cs.concordia.ca/cccg/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 9--11}, YEAR = 2004, PAGES = {60--63}, papers = {BandUnfolding_CGTA}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, comments = {This paper is also available from the electronic proceedings as http://www.cs.concordia.ca/cccg/papers/45.pdf.}, length = {4 pages}, unrefereed = 1 } @InProceedings{CCCG2003Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2003}, BOOKTITLE = {Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004)}, bookurl = {http://www.cs.concordia.ca/cccg/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {August 9--11}, YEAR = 2004, PAGES = {209--211}, comments = {This paper is also available from the electronic proceedings as http://www.cs.concordia.ca/cccg/papers/open03.pdf.}, updates = {The solution to Ferran Hurtado's “Painting a Polyhedron” problem, along with closely related results, is now published: Richard Nowakowski and Norbert Zeh, “Boundary-Optimal Triangulation Flooding”, in Proceedings of ISAAC 2004.}, length = {4 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2004Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, unrefereed = 1 } @InProceedings{Refolding_SIGGRAPH2004, AUTHOR = {Hayley N. Iben and James F. O'Brien and Erik D. Demaine}, TITLE = {Refolding Planar Polygons}, BOOKTITLE = {Technical Sketchs of the 31st International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 2004)}, ADDRESS = {Los Angeles, California}, MONTH = {August 8--12}, YEAR = 2004, papers = {Refolding_SoCG2006; ForceLinkage_SoCG2004}, comments = {See also animations of this algorithm.}, paperkind = {technical sketch}, length = {1 page}, unrefereed = 1, } @Misc{TreeLayoutWorstCase, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Worst-Case Optimal Tree Layout in a Memory Hierarchy}, HOWPUBLISHED = {Manuscript}, MONTH = {August}, YEAR = 2004, LENGTH = {9 pages}, COMMENTS = {This paper is also available as arXiv:cs.DS/0410048 of the Computing Research Repository (CoRR).}, } @InProceedings{DynamicConnectivity_STOC2004, AUTHOR = {Mihai P\v{a}tra\c{s}cu and Erik D. Demaine}, TITLE = {Lower Bounds for Dynamic Connectivity}, BOOKTITLE = {Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004)}, bookurl = {http://www.cs.uchicago.edu/~stoc04/}, MONTH = {June 13--15}, YEAR = 2004, ADDRESS = {Chicago, Illinois}, PAGES = {546--553}, award = {Invited to special issue of \emph{SIAM Journal on Computing}.}, length = {8 pages}, comments = {This paper is also available from the ACM Digital Library.}, withstudent = 1, papers = {DynamicConnectivity_SICOMP}, } @InProceedings{ForceLinkage_SoCG2004, 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 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)}, bookurl = {http://socg.poly.edu/home.htm}, MONTH = {June 9--11}, YEAR = 2004, ADDRESS = {Brooklyn, New York}, PAGES = {134--143}, award = {Invited to special issue of \emph{Discrete \& Computational Geometry}.}, length = {10 pages}, papers = {ForceLinkage_CGW2002; Refolding_SIGGRAPH2004}, replaces = {ForceLinkage_CGW2002}, comments = {This paper is also available from the ACM Digital Library.

See also animations and a Java applet implementation of this algorithm.}, updates = {Michael Zilske and Günter Rote have another implementation as a Java applet that draws the trace of vertices.}, } @InProceedings{Curves_SoCG2004, AUTHOR = {Ilya Baran and Erik D. Demaine}, TITLE = {Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve}, BOOKTITLE = {Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)}, bookurl = {http://socg.poly.edu/home.htm}, MONTH = {June 9--11}, YEAR = 2004, ADDRESS = {Brooklyn, New York}, PAGES = {220--229}, award = {Invited to special issue of \emph{International Journal of Computational Geometry and Applications}.}, papers = {Curves_IJCGA}, length = {10 pages}, comments = {This paper is also available from the ACM Digital Library.}, withstudent = 1 } @InProceedings{Embedding_SoCG2004, AUTHOR = {Mihai B\u{a}doiu and Erik D. Demaine and MohammadTaghi Hajiaghayi and Piotr Indyk}, TITLE = {Low-Dimensional Embedding with Extra Information}, BOOKTITLE = {Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)}, bookurl = {http://socg.poly.edu/home.htm}, MONTH = {June 9--11}, YEAR = 2004, ADDRESS = {Brooklyn, New York}, PAGES = {320--329}, award = {Invited to special issue of \emph{Discrete \& Computational Geometry}.}, length = {10 pages}, comments = {This paper is also available from the ACM Digital Library.}, withstudent = 1, papers = {Embedding_DCG}, } @InProceedings{GeodesicHamSandwich_SoCG2004, AUTHOR = {Prosenjit Bose and Erik D. Demaine and Ferran Hurtado and John Iacono and Stefan Langerman and Pat Morin}, TITLE = {Geodesic Ham-Sandwich Cuts}, BOOKTITLE = {Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)}, bookurl = {http://socg.poly.edu/home.htm}, MONTH = {June 9--11}, YEAR = 2004, ADDRESS = {Brooklyn, New York}, PAGES = {1--9}, length = {9 pages}, comments = {This paper is also available from the ACM Digital Library.}, papers = {GeodesicHamSandwich_DCG}, } @InProceedings{ChordSeparation_SoCG2004, AUTHOR = {Erik D. Demaine and Jeff Erickson and Ferran Hurtado and John Iacono and Stefan Langerman and Henk Meijer and Mark Overmars and Sue Whitesides}, TITLE = {Separating point sets in polygonal environments}, BOOKTITLE = {Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)}, bookurl = {http://socg.poly.edu/home.htm}, MONTH = {June 9--11}, YEAR = 2004, ADDRESS = {Brooklyn, New York}, PAGES = {10--16}, award = {Invited to special issue of \emph{International Journal of Computational Geometry and Applications}.}, papers = {ChordSeparation_IJCGA}, length = {7 pages}, comments = {This paper is also available from the ACM Digital Library.}, } @InProceedings{Morpion_FUN2004, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Arthur Langerman and Stefan Langerman}, TITLE = {Morpion Solitaire}, BOOKTITLE = {Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004)}, bookurl = {http://www.di.unipi.it/fun04/}, MONTH = {May 26--28}, YEAR = 2004, ADDRESS = {Isola d'Elba, Italy}, PAGES = {53--64}, award = {Invited to special issue of \emph{Theory of Computing Systems}.}, papers = {Morpion_TCS}, length = {12 pages} } @InProceedings{Yogi_FUN2004, AUTHOR = {Stelian Ciurea and Erik D. Demaine and Corina E. P\v{a}tra\c{s}cu and Mihai P\v{a}tra\c{s}cu}, TITLE = {Finding a Divisible Pair and a Good Wooden Fence}, BOOKTITLE = {Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004)}, bookurl = {http://www.di.unipi.it/fun04/}, MONTH = {May 26--28}, YEAR = 2004, ADDRESS = {Isola d'Elba, Italy}, PAGES = {206--219}, papers = {DivisiblePair_SIGSAM}, length = {12 pages}, withstudent = 1 } @InProceedings{PushPush1_PSPACE_FUN2004, AUTHOR = {Erik D. Demaine and Michael Hoffmann and Markus Holzer}, TITLE = {PushPush-$k$ is PSPACE-Complete}, BOOKTITLE = {Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004)}, bookurl = {http://www.di.unipi.it/fun04/}, MONTH = {May 26--28}, YEAR = 2004, ADDRESS = {Isola d'Elba, Italy}, PAGES = {159--170}, LENGTH = {12 pages} } @InProceedings{FUN2004i, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Puzzles, Art, and Magic with Algorithms}, BOOKTITLE = {Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004)}, bookurl = {http://www.di.unipi.it/fun04/}, MONTH = {May 26--28}, YEAR = 2004, ADDRESS = {Isola d'Elba, Italy}, PAGES = {7--15}, award = {Invited to special issue of \emph{Theory of Computing Systems}.}, length = {9 pages}, papers = {FUN2004i_TheoryComputSys}, unrefereed = 1, category = {art}, } @Article{PointSearching_CGTA, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Proximate Point Searching}, JOURNAL = {Computational Geometry: Theory and Applications}, journalurl = {http://www.elsevier.com/locate/issn/09257721}, VOLUME = 28, NUMBER = 1, MONTH = {May}, YEAR = {2004}, PAGES = {29--40}, NOTE = {Special issue of selected papers from the 14th Canadian Conference on Computational Geometry, 2002.}, LENGTH = {15 pages}, PAPERS = {PointSearching_CCCG2002}, replaces = {PointSearching_CCCG2002}, COMMENTS = {This paper is also available from ScienceDirect.}, } @InProceedings{Unified_LATIN2004, AUTHOR = {Mihai B\u{a}doiu and Erik D. Demaine}, TITLE = {A Simplified and Dynamic Unified Structure}, BOOKTITLE = {Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004)}, bookurl = {http://www.latintcs.org/2004/}, ADDRESS = {Buenos Aires, Argentina}, MONTH = {April 5--8}, YEAR = 2004, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2976, PAGES = {466--473}, papers = {Unified_TCS}, award = {Invited to special issue of \emph{Theoretical Computer Science}.}, comments = {This paper is also available from SpringerLink.}, copyright = {The paper is \copyright Springer-Verlag.}, length = {8 pages}, withstudent = 1 } @InProceedings{Bidimensional_LATIN2004, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Bidimensional Parameters and Local Treewidth}, BOOKTITLE = {Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004)}, bookurl = {http://www.latintcs.org/2004/}, ADDRESS = {Buenos Aires, Argentina}, MONTH = {April 5--8}, YEAR = {2004}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2976, PAGES = {109--118}, comments = {This paper is also available from SpringerLink.}, copyright = {The paper is \copyright Springer-Verlag.}, length = {10 pages}, papers = {Bidimensional_SIDMA}, withstudent = 1 } @InProceedings{UnimodalOptimization_EuroCG2004, AUTHOR = {Erik D. Demaine and Stefan Langerman}, TITLE = {Optimizing a {2D} Function Satisfying Unimodality Properties}, BOOKTITLE = {Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2004)}, bookurl = {http://www.congreso.us.es/ewcg04/}, ADDRESS = {Seville, Spain}, MONTH = {March 24--26}, YEAR = 2004, PAGES = {107--110}, paperkind = {abstract}, length = {4 pages}, comments = {This abstract is also available from the electronic proceedings as http://www.congreso.us.es/ewcg04/Articulos/demaine.ps.}, unrefereed = 1, papers = {UnimodalOptimization_ESA2005}, } @Article{DagstuhlGames2002Open, AUTHOR = {Erik D. Demaine and Rudolf Fleischer and Aviezri S. Fraenkel and Richard J. Nowakowski}, TITLE = {Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 313, NUMBER = 3, MONTH = {February}, YEAR = 2004, PAGES = {539--543}, NOTE = {Special issue on algorithmic combinatorial game theory.}, comments = {This paper is also available from ScienceDirect.}, unrefereed = 1, } @Article{Clobber_TCS, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Rudolf Fleischer}, TITLE = {Solitaire Clobber}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 313, NUMBER = 3, MONTH = {February}, YEAR = 2004, PAGES = {325--338}, NOTE = {Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 2002.}, LENGTH = {15 pages}, PAPERS = {Clobber_CGames2002; Clobber_TR2002}, replaces = {Clobber_CGames2002}, COMMENTS = {This paper is also available from ScienceDirect.}, UPDATES = {Ivars Peterson wrote an article describing these results, “Getting Clobbered”, Science News 161(17), April 27, 2002.} } @InProceedings{Retroactive_SODA2004, AUTHOR = {Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Retroactive Data Structures}, BOOKTITLE = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)}, bookurl = {http://www.siam.org/meetings/da04/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 11--13}, YEAR = 2004, PAGES = {274--283}, length = {10 pages}, papers = {Retroactive_TALG}, } @InProceedings{PartialSums_SODA2004, AUTHOR = {Mihai P\v{a}tra\c{s}cu and Erik D. Demaine}, TITLE = {Tight Bounds for the Partial-Sums Problem}, BOOKTITLE = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)}, bookurl = {http://www.siam.org/meetings/da04/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 11--13}, YEAR = 2004, PAGES = {20--29}, LENGTH = {10 pages}, withstudent = 1, papers = {DynamicConnectivity_SICOMP}, } @InProceedings{ApexMinorFree_SODA2004, AUTHOR = {Erik D. Demaine and MohammadTaghi Hajiaghayi}, TITLE = {Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications}, BOOKTITLE = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)}, bookurl = {http://www.siam.org/meetings/da04/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 11--13}, YEAR = 2004, PAGES = {833--842}, LENGTH = {10 pages}, withstudent = 1 } @InProceedings{HMinorFree_SODA2004, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Subexponential parameterized algorithms on graphs of bounded-genus and $H$-minor-free graphs}, BOOKTITLE = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)}, bookurl = {http://www.siam.org/meetings/da04/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 11--13}, YEAR = 2004, PAGES = {823--832}, length = {10 pages}, withstudent = 1, papers = {HMinorFree_JACM}, } @InProceedings{InterpolationSearch_SODA2004, AUTHOR = {Erik D. Demaine and Thouis Jones and Mihai P\v{a}tra\c{s}cu}, TITLE = {Interpolation Search for Non-Independent Data}, BOOKTITLE = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)}, bookurl = {http://www.siam.org/meetings/da04/}, ADDRESS = {New Orleans, Louisiana}, MONTH = {January 11--13}, YEAR = 2004, PAGES = {522--523}, LENGTH = {2 pages}, withstudent = 1 } @Article{MinAvgDistance_JPhysA, AUTHOR = {Carl M. Bender and Michael A. Bender and Erik D. Demaine and S\'andor P. Fekete}, TITLE = {What is the optimal shape of a city?}, JOURNAL = {Journal of Physics A: Mathematical and General}, journalurl = {http://www.iop.org/EJ/journal/JPhysA}, VOLUME = 37, NUMBER = 1, PAGES = {147--159}, MONTH = {January}, YEAR = 2004, length = {13 pages}, papers = {MinAvgDistance_CCCG2009; MinAvgDistance_Algorithmica; MinAvgDistance_WADS2005} } @InCollection{CRCLinkage, AUTHOR = {Robert Connelly and Erik D. Demaine}, TITLE = {Geometry and Topology of Polygonal Linkages}, BOOKTITLE = {CRC Handbook of Discrete and Computational Geometry}, bookurl = {http://cs.smith.edu/~orourke/books/discrete.html}, EDITION = {Second}, CHAPTER = 9, YEAR = 2004, PAGES = {197--218}, LENGTH = {24 pages} } @Article{PCR_TCS, 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}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 310, NUMBER = {1--3}, MONTH = {January}, YEAR = {2004}, PAGES = {287--307}, PAPERS = {PCR_COCOON2003; PCR_TR2001}, replaces = {PCR_COCOON2003}, LENGTH = {21 pages}, COMMENTS = {This paper is also available from ScienceDirect.}, } @InProceedings{ProteinMachine_ISAAC2003, AUTHOR = {Erik D. Demaine and Stefan Langerman and Joseph O'Rourke}, TITLE = {Geometric Restrictions on Producible Polygonal Protein Chains}, BOOKTITLE = {Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003)}, bookurl = {http://isaac.lab2.kuis.kyoto-u.ac.jp/}, ADDRESS = {Kyoto, Japan}, MONTH = {December 15--17}, YEAR = 2003, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2906, PAGES = {395--404}, award = {Invited to special issue of \emph{Algorithmica}.}, length = {10 pages}, copyright = {The paper is \copyright Springer-Verlag.}, comments = {This paper is also available from SpringerLink.}, papers = {ProteinMachine_Algorithmica}, } @Misc{TreeLayout_Manuscript2003, 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 = {December}, YEAR = 2003, 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.} } @InProceedings{Autolocalization_SenSys2003, AUTHOR = {Nissanka B. Priyantha and Hari Balakrishnan and Erik Demaine and Seth Teller}, TITLE = {Anchor-Free Distributed Localization in Sensor Networks}, BOOKTITLE = {Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys 2003)}, bookurl = {http://www.cens.ucla.edu/sensys03/}, ADDRESS = {Los Angeles, California, USA}, MONTH = {November 5--7}, YEAR = 2003, PAGES = {340--341}, PAPERKIND = {poster abstract}, LENGTH = {2 pages}, withstudent = 1, poster = 1, } @InProceedings{SlidingWindow_IMC2003, AUTHOR = {Lukasz Golab and David DeHaan and Erik D. Demaine and Alejandro L\'opez-Ortiz and J. Ian Munro}, TITLE = {Identifying Frequent Items in Sliding Windows over On-Line Packet Streams}, BOOKTITLE = {Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC 2003)}, bookurl = {http://www.icir.org/vern/imc-2003/}, ADDRESS = {Miami, Florida}, MONTH = {October 27--29}, YEAR = 2003, PAGES = {173--178}, LENGTH = {6 pages}, PAPERS = {NetworkStats_ESA2002} } @InProceedings{PlanarEmbedding_GD2003, AUTHOR = {Sergio Cabello and Erik D. Demaine and G\"unter Rote}, TITLE = {Planar Embeddings of Graphs with Specified Edge Lengths}, BOOKTITLE = {Proceedings of the 11th Symposium on Graph Drawing (GD 2003)}, bookurl = {http://www.gd2003.org/}, VOLUME = 2912, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, ADDRESS = {Perugia, Italy}, MONTH = {September 21--24}, YEAR = 2003, PAGES = {283--294}, copyright = {The paper is \copyright Springer-Verlag.}, length = {12 pages}, papers = {PlanarEmbedding_JGAA}, } @InProceedings{Harmonic_ESA2003, AUTHOR = {Therese Biedl and Erik D. Demaine and Alexander Golynski and Joseph D. Horton and Alejandro L\'opez-Ortiz and Guillaume Poirier and Claude-Guy Quimper}, TITLE = {Optimal Dynamic Video-On-Demand using Adaptive Broadcasting}, BOOKTITLE = {Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003)}, bookurl = {http://web.archive.org/web/20040202073828/http://www.conferences.hu/ALGO2003/ESA.htm}, SERIES = {Lecture Notes in Computer Science}, VOLUME = 2832, ADDRESS = {Budapest, Hungary}, MONTH = {September 15--20}, YEAR = 2003, PAGES = {90--101}, comments = {This paper is also available from SpringerLink.}, } @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/}, VOLUME = 30, NUMBER = 2, MONTH = {September}, YEAR = 2003, PAGES = {205--239}, LENGTH = {36 pages}, PAPERS = {LinkageTR; FOCS2000a; EuroCG2000}, replaces = {FOCS2000a; EuroCG2000}, WEBPAGES = {linkage}, comments = {This paper is also available from SpringerLink.}, 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.}, } @Article{TextSearchLB_JAlgorithms, 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.elsevier.com/locate/jalgor}, VOLUME = 48, NUMBER = 1, MONTH = {August}, YEAR = 2003, PAGES = {2--15}, NOTE = {Special issue of selected papers from the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.}, PAPERS = {SODA2001b}, replaces = {SODA2001b}, LENGTH = {14 pages}, COMMENTS = {This paper is also available from the ScienceDirect.} } @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.com/locate/issn/09257721}, VOLUME = 26, NUMBER = 1, MONTH = {August}, YEAR = 2003, PAGES = {21--36}, NOTE = {Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.}, comments = {This paper is also available from ScienceDirect.}, webpages = {pushingblocks}, papers = {PushXCCCG2001}, replaces = {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.com/locate/issn/09257721}, VOLUME = 26, NUMBER = 1, MONTH = {August}, YEAR = 2003, PAGES = {37--45}, NOTE = {Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.}, COMMENTS = {This paper is available from ScienceDirect.}, PAPERS = {InterlockedLinkages_CCCG2001; InterlockedLinkages_SoCG2002}, replaces = {InterlockedLinkages_CCCG2001}, LENGTH = {10 pages} } %Misc{NCL_Manuscript, AUTHOR = {Robert A. Hearn and Erik D. Demaine}, TITLE = {PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation}, HOWPUBLISHED = {Manuscript}, MONTH = {August}, YEAR = 2003, LENGTH = {18 pages}, PAPERS = {NCL_TCS; 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.}, } @InProceedings{Clustering_APPROX2003, AUTHOR = {Erik D. Demaine and Nicole Immorlica}, TITLE = {Correlation Clustering with Partial Information}, BOOKTITLE = {Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-APPROX 2003)}, ADDRESS = {Princeton, New Jersey}, MONTH = {August 24--26}, YEAR = 2003, PAGES = {1--13}, papers = {Clustering_TCS}, length = {12 pages}, comments = {This paper is also available from SpringerLink.}, withstudent = 1 } @InProceedings{HingedDissections_CCCG2003, AUTHOR = {Robert A. Hearn and Erik D. Demaine and Greg N. Frederickson}, TITLE = {Hinged Dissection of Polygons is Hard}, BOOKTITLE = {Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003)}, bookurl = {http://www.cs.dal.ca/~cccg/}, ADDRESS = {Halifax, Nova Scotia, Canada}, MONTH = {August 11--13}, YEAR = 2003, PAGES = {98--102}, LENGTH = {4 pages}, withstudent = 1, unrefereed = 1 } @InProceedings{VolumeQueries_CCCG2003, AUTHOR = {Erik D. Demaine and Jeff Erickson and Stefan Langerman}, TITLE = {On the Complexity of Halfspace Volume Queries}, BOOKTITLE = {Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003)}, bookurl = {http://www.cs.dal.ca/~cccg/}, ADDRESS = {Halifax, Nova Scotia, Canada}, MONTH = {August 11--13}, YEAR = 2003, PAGES = {159--160}, LENGTH = {2 pages}, unrefereed = 1 } @InProceedings{CCCG2002Open, AUTHOR = {Erik D. Demaine and Joseph O'Rourke}, TITLE = {Open Problems from {CCCG} 2002}, BOOKTITLE = {Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003)}, bookurl = {http://www.cs.dal.ca/~cccg/}, ADDRESS = {Halifax, Nova Scotia, Canada}, MONTH = {August 11--13}, YEAR = 2003, PAGES = {178--181}, length = {4 pages}, papers = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2001Open; CCCG2000Open; CCCG99Open}, comments = {This paper is also available as arXiv:cs.CG/0212050 of the Computing Research Repository (CoRR).}, xxxcomments = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.}, updates = {Two new related references on the Sailor-in-the-Fog problem are "Lost at Sea" by Steven R. Finch and John A. Shonder and "Finding the shore of a lake" by Klaus Reinhardt.}, unrefereed = 1 } @InProceedings{VoronoiBoundary_WADS2003, AUTHOR = {David Bremner and Erik Demaine and Jeff Erickson and John Iacono and Stefan Langerman and Pat Morin and Godfried Toussaint}, TITLE = {Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries}, BOOKTITLE = {Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS 2003)}, BOOKURL = {http://www.wads.org/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2748, ADDRESS = {Ottawa, Ontario, Canada}, MONTH = {July 30--August 1}, YEAR = 2003, PAGES = {451--461}, copyright = {The paper is \copyright Springer-Verlag.}, length = {12 pages}, papers = {VoronoiBoundary_DCG}, comments = {This paper is also available from SpringerLink.}, } @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://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 304, NUMBER = {1--3}, MONTH = {July}, YEAR = 2003, PAGES = {471--476}, PAPERS = {SODA2001c}, replaces = {SODA2001c}, LENGTH = {6 pages}, COMMENTS = {This paper is also available from ScienceDirect.}, } @InProceedings{Tetris_COCOON2003, AUTHOR = {Erik D. Demaine and Susan Hohenberger and David Liben-Nowell}, TITLE = {Tetris is Hard, Even to Approximate}, BOOKTITLE = {Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003)}, BOOKURL = {http://www.cs.montana.edu/bhz/cocoon03.html}, ADDRESS = {Big Sky, Montana}, MONTH = {July 25--28}, YEAR = 2003, PAGES = {351--363}, PAPERS = {Tetris_IJCGA; Tetris_CGW2002; Tetris_TR2002}, LENGTH = {12 pages}, 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.} } @InProceedings{PCR_COCOON2003, 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}, BOOKTITLE = {Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003)}, BOOKURL = {http://www.cs.montana.edu/bhz/cocoon03.html}, ADDRESS = {Big Sky, Montana}, MONTH = {July 25--28}, YEAR = 2003, PAGES = {182--191}, PAPERS = {PCR_TCS; PCR_TR2001}, LENGTH = {10 pages} } @InProceedings{MapGraphs_ICALP2003, AUTHOR = {Erik D. Demaine and Fedor V. Fomin and MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos}, TITLE = {Fixed-Parameter Algorithms for the $(k,r)$-Center in Planar Graphs and Map Graphs}, BOOKTITLE = {Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003)}, BOOKURL = {http://www.win.tue.nl/icalp2003/}, ADDRESS = {Eindhoven, The Netherlands}, MONTH = {June 30--July 4}, YEAR = 2003, PAGES = {829--844}, LENGTH = {12 pages}, PAPERS = {MapGraphs_TAlg}, withstudent = 1 } @Article{Palindromes_TCS, AUTHOR = {Therese C. Biedl and Jonathan F. Buss and Erik D. Demaine and Martin L. Demaine and Mohammadtaghi Hajiaghayi and Tom\'a\v{s} Vina\v{r}}, TITLE = {Palindrome Recognition Using a Multidimensional Tape}, JOURNAL = {Theoretical Computer Science}, journalurl = {http://authors.elsevier.com/JournalDetail.html?PubID=505625}, VOLUME = 302, NUMBER = {1--3}, MONTH = {June}, YEAR = 2003, PAGES = {475--480}, LENGTH = {7 pages}, COMMENTS = {This paper is also available from ScienceDirect.}, } @Article{RedBlue_CGTA2003, 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.com/locate/issn/09257721}, VOLUME = 25, NUMBER = {1--2}, MONTH = {May}, YEAR = {2003}, PAGES = {139--159}, NOTE = {Special issue of selected papers from the 17th European Workshop on Computational Geometry, 2001.}, LENGTH = {27 pages}, PAPERS = {EuroCG2001}, replaces = {EuroCG2001}, COMMENTS = {This paper is also available from the ScienceDirect.

This paper is also available as arXiv:cs.CG/0201018 of the Computing Research Repository (CoRR).}, } @InProceedings{TriangulationGames_EuroCG2003, 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 = {Geometric Games on Triangulations}, BOOKTITLE = {Abstracts from the 19th European Workshop of Computational Geometry (EuroCG 2003)}, ADDRESS = {Bonn, Germany}, MONTH = {March 24--26}, YEAR = 2003, PAGES = {89--92}, paperkind = {abstract}, papers = {TriangulationGames_TCS; TriangulationGames_JCDCG2002}, length = {4 pages}, unrefereed = 1, } @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.com/locate/issn/09257721}, VOLUME = 24, NUMBER = 2, MONTH = {February}, YEAR = 2003, PAGES = {51--62}, NOTE = {Special issue of selected papers from the 4th CGC Workshop on Computational Geometry, 1999.}, PAPERS = {CGC99; CCCG99b}, replaces = {CGC99; CCCG99b}, LENGTH = {14 pages}, COMMENTS = {This paper is also available as arXiv:cs.CG/9908003 of the Computing Research Repository (CoRR).} } @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/}, VOLUME = 19, NUMBER = 9, YEAR = 2003, PAGES = {1070--1078}, NOTE = {Special issue on Microarray Analysis.}, COMMENTS = {This paper is available from Oxford University Press.}, PAPERS = {GeneExpression_WABI2002; GeneExpression_UWTR2001}, replaces = {GeneExpression_WABI2002}, LENGTH = {12 pages} } @InCollection{VertexUnfolding_Kuperberg2003, 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}, bookurl = {http://www.crcpress.com/shopping_cart/products/product_detail.asp?sku=DK2123}, PUBLISHER = {Marcer Dekker Inc.}, YEAR = 2003, PAGES = {215--228}, replaces = {VertexUnfolding_SoCG2002}, papers = {VertexUnfolding_SoCG2002; VertexUnfolding2}, length = {15 pages}, comments = {The book is searchable on Amazon.}, } @Article{HingedAlphabet, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Hinged Dissection of the Alphabet}, JOURNAL = {Journal of Recreational Mathematics}, journalurl = {http://www.baywood.com/journals/previewJournals.asp?ID=0022-412x}, VOLUME = 31, NUMBER = 3, PAGES = {204--207}, YEAR = 2003, papers = {HingedPolyforms}, length = {4 pages}, webpages = {fonts/hinged}, category = {art}, } @InProceedings{SquareCutting_JCDCG2002, AUTHOR = {Prosenjit Bose and Erik D. Demaine and John Iacono and Stefan Langerman}, TITLE = {Quartering a Square Optimally}, BOOKTITLE = {Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002)}, ADDRESS = {Tokyo, Japan}, MONTH = {December 6--9}, YEAR = 2002, PAGES = {5--6}, unrefereed = 1, } @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 = {Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002)}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2866, ADDRESS = {Tokyo, Japan}, MONTH = {December 6--9}, YEAR = 2002, PAGES = {22--37}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, PAPERS = {TriangulationGames_TCS; TriangulationGames_EuroCG2003}, LENGTH = {17 pages} } @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://cg.scs.carleton.ca/~isaac02/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {November 20--23}, YEAR = 2002, PAGES = {369--380}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2518, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {Flat2Flat_CCCG2002}, COMMENTS = {This paper is also available from SpringerLink.}, } @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://cg.scs.carleton.ca/~isaac02/}, ADDRESS = {Vancouver, British Columbia, Canada}, MONTH = {November 20--23}, YEAR = 2002, PAGES = {262--273}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2518, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {CliqueSum_Algorithmica; CliqueSum_TR2002; CliqueSum_APPROX2002}, COMMENTS = {This paper is also available from SpringerLink.}, withstudent = 1 } @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 = {Abstracts from 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, PAPERKIND = {abstract}, LENGTH = {2 pages}, COMMENTS = {See also animations and a Java applet implementation of this algorithm.}, PAPERS = {ForceLinkage_SoCG2004}, unrefereed = 1, } @InProceedings{Tetris_CGW2002, AUTHOR = {Erik D. Demaine and Susan Hohenberger and David Liben-Nowell}, TITLE = {Tetris is Hard, Even to Approximate}, BOOKTITLE = {Abstracts from 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, PAPERKIND = {abstract}, LENGTH = {2 pages}, PAPERS = {Tetris_IJCGA; Tetris_COCOON2003; 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.}, unrefereed = 1, } @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_IJCGA; Tetris_COCOON2003; Tetris_CGW2002}, COMMENTS = {This paper is also available as arXiv:cs.CC/0210020 of the Computing Research Repository (CoRR).}, 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.} } @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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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.}, updates = {Our deterministic algorithm is identical to an earlier algorithm of J. Misra and D. Gries, “Finding repeated elements”, Science of Programming, 2:143–152, 1982.} } @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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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_Manuscript2003}, 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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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_JCSS; CliqueSum_ISAAC2002}, withstudent = 1, } @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 = {506--520}, 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/2452/24520506.pdf.}, 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://www.worldscinet.com/ijcga/ijcga.shtml}, 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}, replaces = {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 = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2000Open; CCCG99Open}, comments = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf.}, unrefereed = 1 } @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.}, unrefereed = 1 } @InProceedings{Push2F_CCCG2002, AUTHOR = {Erik D. Demaine and Robert A. Hearn and Michael Hoffmann}, TITLE = {Push-2-F 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.

This version is updated from the original conference version in order to fix an error discovered in January 2003.}, unrefereed = 1, withstudent = 1, } @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).}, unrefereed = 1, papers = {PermutingPolygons_CGTA}, } @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}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, length = {4 pages}, comments = {This paper is also available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/22.ps.}, PAPERS = {PointSearching_CGTA}, unrefereed = 1 } @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.}, unrefereed = 1 } @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/}, VOLUME = 28, NUMBER = 2, PAGES = {231--253}, MONTH = {August}, YEAR = 2002, LENGTH = {22 pages}, PAPERS = {JCDCG2000a}, replaces = {JCDCG2000a}, COMMENTS = {This paper is also available from SpringerLink. An older but longer version is also available as arXiv:cs.CG/0008010 of the Computing Research Repository (CoRR).} } @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 $\mathbb{R}^3$}, EDITOR = {Jorge Calvo and Kenneth Millett and Eric Rawdon}, PUBLISHER = {American Mathematical Society}, YEAR = {2002}, PAGES = {287--311}, 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.}, papers = {InfinitesimallyLocked_CGW2001}, replaces = {InfinitesimallyLocked_CGW2001} } @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 (CG 2002)}, BOOKURL = {http://www.cs.ualberta.ca/~cg2002/}, VOLUME = 2883, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, ADDRESS = {Edmonton, Alberta, Canada}, MONTH = {July 25--27}, YEAR = 2002, actualyear = 2003, PAGES = {188--200}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {13 pages}, PAPERS = {Clobber_TCS; Clobber_TR2002}, COMMENTS = {This paper is also available from SpringerLink, and 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://polux.lcc.uma.es/ICALP2002/index.html}, ADDRESS = {Malaga, Spain}, MONTH = {July 8--13}, YEAR = 2002, PAGES = {401--413}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2380, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, LENGTH = {12 pages}, PAPERS = {NCL_TCS}, 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.}, withstudent = 1, } @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}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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.} } @InCollection{BRICS2002, AUTHOR = {Erik D. Demaine}, TITLE = {Cache-Oblivious Algorithms and Data Structures}, BOOKTITLE = {Lecture Notes from the EEF Summer School on Massive Data Sets}, BOOKURL = {http://www.brics.dk/MassiveData02/}, ADDRESS = {BRICS, University of Aarhus, Denmark}, MONTH = {June 27--July 1}, YEAR = 2002, length = {29 pages} } @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}, award = {Invited to special issue of \emph{Discrete \& Computational Geometry}.}, 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://www.crm.umontreal.ca/STOC02/}, ADDRESS = {Montr\'eal, Qu\'ebec, Canada}, MONTH = {May 19--21}, YEAR = 2002, PAGES = {268--276}, LENGTH = {9 pages}, PAPERS = {BufferTrees_SICOMP} } @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.}, } @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} } @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}, replaces = {JCDCG2000c}, 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{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}, replaces = {MFCS2000}, } @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}, replaces = {CCCG98c}, LENGTH = {5 pages}, WEBPAGES = {linkage} } @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.}, } @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/}, PUBLISHER = {Cambridge University Press}, 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/}, PUBLISHER = {Cambridge University Press}, 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/}, PUBLISHER = {Cambridge University Press}, 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.}, UPDATES = {Ivars Peterson wrote an article describing these results, “Sliding-Coin Puzzles”, Science News 163(5), February 1, 2003.}, } @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}, PAPERS = {PCR_TCS; PCR_COCOON2003} } @InProceedings{MatchingBounds_ISAAC2001, 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)}, ADDRESS = {Christchurch, New Zealand}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2223, MONTH = {December 19--21}, YEAR = 2001, PAGES = {308--319}, LENGTH = {12 pages}, PAPERS = {MatchingBounds_DM; 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.}, } @InProceedings{InfinitesimallyLocked_CGW2001, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Infinitesimally Locked Linkages with Applications to Locked Trees}, BOOKTITLE = {Abstracts from the 11th Annual Fall Workshop on Computational Geometry}, BOOKURL = {http://geometry.poly.edu/cgw2001/}, ADDRESS = {New York, New York}, MONTH = {November 2--3}, YEAR = 2001, PAPERKIND = {abstract}, LENGTH = {2 pages}, PAPERS = {InfinitesimallyLocked_LasVegas}, unrefereed = 1, } @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} } @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}, replaces = {SODA99c}, COMMENTS = {This paper is also available from the publisher's website.} } @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} } @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.com/locate/issn/09257721}, 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}, replaces = {CCCG2000a}, COMMENTS = {This paper is also available from ScienceDirect.}, } @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.com/locate/issn/09257721}, 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}, replaces = {CCCG2000c}, WEBPAGES = {linkage}, COMMENTS = {This paper is also available from ScienceDirect.}, } @InProceedings{AlgGameTheory_MFCS2001, 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}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = {2136}, xEDITOR = {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 = {AlgGameTheory_GONC3}, 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{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 = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG99Open}, unrefereed = 1 } @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}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, papers = {PushingBlocks_CGTA}, 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.gz.}, unrefereed = 1 } @InProceedings{PaperReachability_CCCG2001, 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.gz.

Photos of Victoria Hart folding a crane by our algorithm }, PAPERS = {PaperReachability_CCCG2004}, unrefereed = 1 } @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}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, 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.gz.}, unrefereed = 1 } @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.gz.}, unrefereed = 1, category = {art}, } @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/}, xEDITOR = {Frank Dehne and J\"org-R\"udiger Sack and Roberto Tamassia}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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.}, } @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} } 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 = {AlgGameTheory_MFCS2001}, WEBPAGES = {games}, } @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.} } 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} } @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/}, xEDITOR = {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_DAM; FunSort_TR2001} } @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} } % 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 = {Abstracts from the 17th European Workshop on Computational Geometry (EuroCG 2001)}, BOOKURL = {http://www.eurocg.org/cg01/www/}, MONTH = {March 26--28}, YEAR = 2001, ADDRESS = {Berlin, Germany}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, length = {4 pages}, paperkind = {abstract}, papers = {RedBlue_CGTA2003}, unrefereed = 1, } @InProceedings{OSME2001, AUTHOR = {Erik D. Demaine and Martin L. Demaine}, TITLE = {Recent Results in Computational Origami}, BOOKTITLE = {Origami$^3$: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001)}, BOOKURL = {http://mars.wnec.edu/~thull/osm/osm.html}, ADDRESS = {Monterey, California}, MONTH = {March 9--11}, YEAR = 2001, PAGES = {3--16}, PUBLISHER = {A K Peters}, award = {Translated into Japanese in a book of selected papers from OSME 2001, Morikita Publishing Co., 2005, 3--16.}, length = {10 pages}, paperkind = {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 = {Origami$^3$: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education (OSME 2001)}, BOOKURL = {http://mars.wnec.edu/~thull/osm/osm.html}, ADDRESS = {Monterey, California}, MONTH = {March 9--11}, YEAR = 2001, PAGES = {17--28}, PUBLISHER = {A K Peters}, award = {Translated into Japanese in a book of selected papers from OSME 2001, Morikita Publishing Co., 2005, 17--28.}, length = {10 pages}, papers = {FUN98} } @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 = {FunSort_DAM; FUN2001} } @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}, papers = {Milling} } @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}, award = {Invited to special issue of \emph{Journal of Algorithms}.}, length = {6 pages}, papers = {TextSearchLB_JAlgorithms} } @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}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2153, MONTH = {January 5--6}, YEAR = 2001, PAGES = {91--104}, COPYRIGHT = {The paper is \copyright Springer-Verlag.}, 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{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.elsevier.com/locate/jalgor}, 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 = {MatchingBounds_DM; SODA99b}, replaces = {SODA99b}, COPYRIGHT = {The paper is \copyright Academic Press.} } @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)}, YEAR = 2000, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 1969, ADDRESS = {Taipei, Taiwan}, MONTH = {December 18--20}, PAGES = {47--59}, award = {Invited to special issue of \emph{International Journal of Computational Geometry and Applications}.}, copyright = {The paper is \copyright Springer-Verlag.}, length = {12 pages}, papers = {ObliviousRouting_IJCGA2002} } @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 = {Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2000)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/web/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).}, unrefereed = 1, } @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/web/jcdcg2000/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 2098, xEDITOR = {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 = {Abstracts of the Japan Conference on Discrete and Computational Geometry (JCDCG 2000)}, bookurl = {http://gorogoro.cis.ibaraki.ac.jp/web/jcdcg2000/}, ADDRESS = {Tokyo, Japan}, MONTH = {November 22--25}, YEAR = 2000, PAGES = {107--108}, length = {2 pages}, paperkind = {abstract}, papers = {Flipturns}, unrefereed = 1 } @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_SICOMP} } @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.}, } @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 = {Abstracts from 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, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, 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.}, unrefereed = 1, } @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/}, 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.} } @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/research/reports/00/SOCS.00.7.ps.gz}, 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}, award = {Invited to a special issue of \emph{Computational Geometry: Theory and Applications}.}, 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.}, unrefereed = 1 } @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}, unrefereed = 1 } @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}, award = {Invited to a special issue of \emph{Computational Geometry: Theory and Applications}.}, 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}, unrefereed = 1 } @TechReport{FlipturnsTR2000, 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}, INSTITUTION = {Universiteit Utrecht}, NUMBER = {UU-CS-2000-31}, NUMBERURL = {http://www.cs.uu.nl/research/techreps/UU-CS-2000-31.html}, MONTH = {July}, YEAR = 2000, length = {26 pages}, PAPERS = {Flipturns} } @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 = {Aleks_GC2002; JCDCG2000c}, WEBPAGES = {aleksandrov} } @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-2000/CS-2000.shtml#08}, MONTH = {March}, YEAR = 2000, LENGTH = {11 pages}, PAPERS = {BalancedColoringDM; MFCS2000} } @InProceedings{EuroCG2000, AUTHOR = {Robert Connelly and Erik D. Demaine and G\"unter Rote}, TITLE = {Every Polygon Can Be Untangled}, BOOKTITLE = {Abstracts from the 16th European Workshop on Computational Geometry (EuroCG 2000)}, BOOKURL = {http://www.cs.bgu.ac.il/~cg2000/}, MONTH = {March 13--15}, YEAR = 2000, ADDRESS = {Eilat, Israel}, PAGES = {62--65}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, length = {4 pages}, paperkind = {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.}, unrefereed = 1, } @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} } @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.worldscinet.com/ijcga/ijcga.shtml}, 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.

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, number 1, pages 85-104, 2000. 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! Don Hatch reports some further progress: a 492-face holyhedron.

John Conway's Angel and Devil Problem has been solved, even for power-2 angel, by András Máthé and Oddvar Kloster. See this blog post. There are other solutions, for higher-power angels, by Brian Bowditch and Peter Gács.}, unrefereed = 1, } @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{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.com/locate/issn/09257721}, VOLUME = 16, NUMBER = 1, YEAR = 2000, PAGES = {3--21}, NOTE = {Special issue of selected papers from the 3rd CGC Workshop on Computational Geometry, 1998.}, LENGTH = {23 pages}, PAPERS = {SoCG99; CGC98}, replaces = {SoCG99; CGC98}, WEBPAGES = {wrapping}, COPYRIGHT = {The paper is \copyright Elsevier Science Netherlands.} } @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.nishizeki.ecei.tohoku.ac.jp/nszk/nishi/isaac/isaac99/content99.html}, ADDRESS = {Chennai, India}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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{Buddy_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.res.in/~fsttcs99/}, ADDRESS = {Chennai, India}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, 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.}, PAPERS = {Buddy_ActaInf} } @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 = {Abstracts from the 4th CGC Workshop on Computational Geometry (CGC'99)}, ADDRESS = {Baltimore, Maryland}, MONTH = {October 15--16}, YEAR = 1999, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, 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}, unrefereed = 1, } @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{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 = {CCCG2010Open; CCCG2009Open; CCCG2008Open; CCCG2007Open; CCCG2006Open; CCG2005Open; CCCG2004Open; CCCG2003Open; CCCG2002Open; CCCG2001Open; CCCG2000Open; CCCG99OpenTR}, unrefereed = 1 } @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}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, 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).}, updates = {There is a revised paper with new results and a new coauthor (Greg Frederickson).}, papers = {HingedPolyforms}, unrefereed = 1 } @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1999/CS-1999.shtml#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}, PAGES = {13--16}, 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.}, unrefereed = 1 } @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1999/CS-1999.shtml#09}, YEAR = {1999}, LENGTH = {19 pages}, PAPERS = {ResizableArrays_WADS99} } @InProceedings{ResizableArrays_WADS99, 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.wads.org/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, xEDITOR = {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{MaryTrees_WADS99, 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.wads.org/}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, xEDITOR = {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.} } @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.}, category = {art}, } @Misc{PolytopeReconstruction, AUTHOR = {Erik D. Demaine and Jeff Erickson}, TITLE = {Open Problems on Polytope Reconstruction}, HOWPUBLISHED = {Manuscript}, MONTH = {July}, YEAR = 1999, LENGTH = {2 pages} } @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 (SoCG'99)}, MONTH = {June 13--16}, YEAR = 1999, ADDRESS = {Miami Beach, Florida}, PAGES = {409--410}, length = {2 pages}, webpages = {metamorphosis}, category = {art}, } @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)}, MONTH = {June 13--16}, YEAR = 1999, ADDRESS = {Miami Beach, Florida}, PAGES = {105--114}, award = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.}, length = {10 pages}, webpages = {wrapping}, papers = {CGTA2000; CGC98} } @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1999/CS-1999.shtml#03}, MONTH = {March}, YEAR = 1999, LENGTH = {12 pages}, PAPERS = {ISAAC99}, WEBPAGES = {linkage} } @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 = {Ivars Peterson wrote an article describing these results, “Fold-and-Cut Magic”, Science News 162(22), November 30, 2002.

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}, award = {Invited to special issue of \emph{Journal of Algorithms}.}, 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)}, bookurldead = {http://ranran.cis.ibaraki.ac.jp/jcdcg98/jcdcg98.html}, SERIES = {Lecture Notes in Computer Science}, SERIESURL = {http://www.springer.de/comp/lncs/}, VOLUME = 1763, xEDITOR = {Jin Akiyama and Mikio Kano and Masatsugu Urabe}, ADDRESS = {Tokyo, Japan}, MONTH = {December 9--12}, YEAR = 1998, PAGES = {104--117}, length = {15 pages}, papers = {SODA99a}, webpages = {foldcut}, copyright = {The paper is \copyright Springer-Verlag.}, comments = {Shorter version in \emph{Abstracts from the Japan Conference on Computational Geometry}, pages 5--9.}, updates = {Ivars Peterson wrote an article describing these results, “Fold-and-Cut Magic”, Science News 162(22), November 30, 2002.

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{CGC98, AUTHOR = {Erik D. Demaine and Martin L. Demaine and Joseph S. B. Mitchell}, TITLE = {Folding Any Silhouette from a Strip}, BOOKTITLE = {Abstracts from the 3rd CGC Workshop on Computational Geometry (CGC'98)}, 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}, unrefereed = 1, } @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{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/}, 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}, poster = 1, category = {art}, } @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1998/CS-1998.shtml#17}, MONTH = {August}, YEAR = 1998, length = {13 pages}, papers = {GD98}, category = {art}, } @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.}, unrefereed = 1 } @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.}, unrefereed = 1 } @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}, unrefereed = 1 } @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 = {OSME2001b} } @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.ipdps.org/ipps98/}, ADDRESS = {Orlando, Florida}, MONTH = {March 30--April 3}, YEAR = 1998, PAGES = {24--30}, LENGTH = {7 pages; 20 minutes}, PAPERS = {ProtocolsTR} } @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}, replaces = {Java98}, } @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--March 1}, YEAR = 1998, LENGTH = {10 pages; 25 minutes}, PAPERS = {CPE98} } @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}, VOLUME = 12, NUMBER = 6, MONTH = {November}, YEAR = 1997, PAGES = {359--367} } % PUBLISHER = {CRL Publishing}, % ADDRESS = {London}, @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1997/CS-1997.shtml#35}, MONTH = {September}, YEAR = 1997, LENGTH = {16 pages}, PAPERS = {IPPS98} } @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/}, @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 = {http://www.cs.uwaterloo.ca/cs-archive/CS-1997/CS-1997.shtml#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:

} } @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}, award = {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} } @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{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}, @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, length = {21 pages} } % PUBLISHER = {Carleton University Press and Oxford University Press} @Article{IJHSC96, AUTHOR = {Erik D. Demaine and Sampalli Srinivas}, TITLE = {A Novel Routing Algorithm for $k$-ary $n$-cube Interconnection Networks}, JOURNAL = {International Journal of High Speed Computing}, journalurl = {http://www.worldscinet.com/ijhsc/ijhsc.shtml}, 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, PAGES = {329--338}, papers = {IJHSC96} }