% 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{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}, YEAR = {to appear}, replaces = {Crystalline_ISAAC2007}, papers = {Crystalline_ISAAC2008; Crystalline_ISAAC2007; Crystalline_EGC2007}, } @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 III}, YEAR = {to appear}, 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).} } @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}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.}, papers = {DeepRhythms_CCCG2005}, replaces = {DeepRhythms_CCCG2005}, length = {39 pages}, } @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/}, YEAR = {to appear}, withstudent = 1, papers = {Ordinal_APPROX2008; Ordinal_SODA2005}, replaces = {Ordinal_SODA2005}, } @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/}, YEAR = {to appear}, 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.}, papers = {Refolding_SoCG2006; Refolding_SIGGRAPH2004; ForceLinkage_SoCG2004} } @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}, YEAR = {to appear}, NOTE = {Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006.}, papers = {GridWagner_ISAAC2006}, copyright = {The paper is \copyright Springer-Verlag.}, } @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}, YEAR = {to appear}, withstudent = 1, papers = {UniqueCoverage_SODA2006}, replaces = {UniqueCoverage_SODA2006} } @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}, YEAR = {to appear}, papers = {Orthoballs_JCDCG2004}, replaces = {Orthoballs_JCDCG2004}, } @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 Dyson Telescopes}, BOOKTITLE = {Games of No Chance III}, YEAR = {to appear}, withstudent = 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 = {to appear}, } @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 = {to appear}, papers = {NetworkCreation_PODC2007}, } @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 = {to appear}, 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 = {to appear}, 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}, } @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, comments = {See the publisher's webpage for this book. }, availability = {Available for purchase from the publisher or Amazon.}, papers = {Gardner5} } @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/}, MONTH = {December 15--17}, YEAR = 2008, PAGES = {to appear}, length = {12 pages}, withstudent = 1 } @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/}, MONTH = {December 15--17}, YEAR = 2008, PAGES = {to appear}, papers = {Crystalline_CGTA}, copyright = {Copyright held by the authors.}, length = {12 pages} } @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.}, } @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, } @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, } @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 = {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}, 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, } @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, } @Misc{CoinFlipping, AUTHOR = {Nadia Benbernou and Erik D. Demaine and Martin L. Demaine and Benjamin Rossman}, TITLE = {Coin-Flipping Magic}, HOWPUBLISHED = {Manuscript}, MONTH = {April}, YEAR = 2008, NOTE = {Presented at \emph{Gathering for Gardner 8}, Atlanta, Georgia, March 2008.}, 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}, } @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_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 = {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 } @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_STACS2009}, } @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, comments = {See the book's webpage.   }, availability = {Available for purchase from the publisher or Amazon.}, } @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, } @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.}, } @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, PAGES = {to appear}, 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}, 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} } @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 = {to appear}, award = {Invited to special issue of \emph{Journal of Natural Computing}.}, papers = {StagedAssembly_NACO}, } @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, 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 20th European Workshop on Computational Geometry (EuroCG 2007)}, bookurl = {http://ewcg07.tugraz.at/}, ADDRESS = {Graz, Austria}, MONTH = {March 19--21}, YEAR = 2007, PAGES = {14--17}, 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 20th 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 20th 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} } @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} } @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}, 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, } @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 = {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}, } @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.}, } @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) ≥ 80 (by Tristan Cazenave) and a detailed history of the lower bound G′4(A4) ≥ 170 (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.} } @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}, 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.}, paperkind = {poster}, withstudent = 1, poster = 1, } % xxx PAGES? @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_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 = {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, } @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, } @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{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, } @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 Stacking and Polygon Packing: Advances in the Theory of Origami Base Design}, 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 = {to appear}, 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 = {to appear}, 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 } @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, 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 = {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