Erik Demaine's Papers

Books

• Geometric Folding Algorithms: Linkages, Origami, Polyhedra
  (joint work with Joseph O'Rourke)
  Cambridge University Press, July 2007.

• Tribute to a Mathemagician
  (edited with Barry Cipra, Martin L. Demaine, and Tom Rodgers)
  A K Peters, November 2004.

Journal articles

• The Distance Geometry of Music
  (joint work with Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David R. Wood)
  Computational Geometry: Theory and Applications, to appear. Special issue of selected papers from the 17th Canadian Conference on Computational Geometry, 2005.

• Approximability of Partitioning Graphs with Supply and Demand
  (joint work with Takehiro Ito, Xiao Zhou, and Takao Nishizeki)
  Journal of Discrete Algorithms, to appear.

• Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
  (joint work with Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine)
  Natural Computing, to appear. Special issue of selected papers from the 13th International Meeting on DNA Computing, 2007.

• Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics
  (joint work with Noga Alon, Mihai Bădoiu, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos)
  ACM Transactions on Algorithms, to appear.

• Refolding Planar Polygons
  (joint work with Hayley N. Iben and James F. O'Brien)
  Discrete & Computational Geometry, to appear. Special issue of selected papers from the 22nd Annual ACM Symposium on Computational Geometry, 2006.

• Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
  (joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
  Algorithmica, to appear. Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006.

• Combination Can Be Hard: Approximability of the Unique Coverage Problem
  (joint work with Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour)
  SIAM Journal on Computing, to appear.

• Grid Vertex-Unfolding Orthostacks
  (joint work with John Iacono and Stefan Langerman)
  International Journal of Computational Geometry and Applications, to appear.

• Communication-Aware Processor Allocation for Supercomputers
  (joint work with Michael A. Bender, David P. Bunde, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips)
  Algorithmica, to appear. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.

• Optimally Adaptive Integration of Univariate Lipschitz Functions
  (joint work with Ilya Baran and Dmitriy A. Katz)
  Algorithmica, to appear. Special issue of selected papers from the 7th Latin American Symposium on Theoretical Informatics, 2006.

• Realizing Partitions Respecting Full and Partial Order Information
  (joint work with Jeff Erickson, Danny Kri\czanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides)
  Journal of Discrete Algorithms, volume 6, 2008, pages 51–58. Special issue of selected papers from the 16th Australasian Workshop on Combinatorial Algorithms, 2005.

• The Bidimensionality Theory and Its Algorithmic Applications
  (joint work with MohammadTaghi Hajiaghayi)
  The Computer Journal, volume 51, number 3, 2008, pages 292–302.

• Subquadratic Algorithms for 3SUM
  (joint work with Ilya Baran and Mihai Pǎtraşcu)
  Algorithmica, volume 50, number 4, April 2008, pages 584–596. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.

• Linearity of Grid Minors in Treewidth with Applications through Bidimensionality
  (joint work with MohammadTaghi Hajiaghayi)
  Combinatorica, volume 28, number 1, January 2008.

• Edge-Unfolding Nested Polyhedral Bands
  (joint work with Greg Aloupis, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
  Computational Geometry: Theory and Applications, volume 39, number 1, January 2008, pages 30–42. Special issue of selected papers from the 16th Canadian Conference on Computational Geometry, 2004.

• A Unified Access Bound on Comparison-Based Dynamic Dictionaries
  (joint work with Mihai Bădoiu, Richard Cole, and John Iacono)
  Theoretical Computer Science, volume 382, number 2, August 2007, pages 86–96. Special issue of selected papers from the 6th Latin American Symposium on Theoretical Informatics, 2004.

• Planar Embeddings of Graphs with Specified Edge Lengths
  (joint work with Sergio Cabello and Günter Rote)
  Journal of Graph Algorithms and Applications, volume 11, number 1, 2007, pages 259–276.

• Plane Embeddings of Planar Graph Metrics
  (joint work with MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Mohammad Moharrami)
  Discrete & Computational Geometry, volume 38, 2007, pages 615–637.

• Sand Drawings and Gaussian Graphs
  (joint work with Martin L. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
  Journal of Mathematics and the Arts, volume 1, number 2, June 2007, pages 125–132.

• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
  (joint work with Martin L. Demaine)
  Graphs and Combinatorics, volume 23 (Supplement), June 2007, pages 195–208. Special issue on Computational Geometry and Graph Theory: The Akiyama-Chvatal Festschrift.

• Retroactive Data Structures
  (joint work with John Iacono and Stefan Langerman)
  ACM Transactions on Algorithms, volume 3, number 2, May 2007, Article 13.

• Dynamic Optimality–-Almost
  (joint work with Dion Harmon, John Iacono, and Mihai Pǎtraşcu)
  SIAM Journal on Computing, volume 37, number 1, May 2007, pages 240–251. Special issue of selected papers from the 45th Annual IEEE Symposium on Foundations of Computer Science.

• An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms
  (joint work with Lars Arge, Michael A. Bender, Bryan E. Holland-Minkley, and J. Ian Munro)
  SIAM Journal on Computing, volume 36, number 6, March 2007, pages 1672–1695.

• Geodesic Ham-Sandwich Cuts
  (joint work with Prosenjit Bose, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin)
  Discrete & Computational Geometry, volume 37, number 3, March 2007.

• Quickly Deciding Minor-Closed Parameters in General Graphs
  (joint work with MohammadTaghi Hajiaghayi)
  European Journal of Combinatorics, volume 28, number 1, January 2007, pages 311–314.

• Low-Dimensional Embedding with Extra Information
  (joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, and Piotr Indyk)
  Discrete & Computational Geometry, volume 36, number 4, December 2006, pages 609–632. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry.

• Logarithmic Lower Bounds in the Cell-Probe Model
  (joint work with Mihai Pǎtraşcu)
  SIAM Journal on Computing, volume 35, number 4, 2006, pages 932–963. Special issue of selected papers from the 36th ACM Symposium on Theory of Computing, 2004.

• The Bidimensional Theory of Bounded-Genus Graphs
  (joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
  SIAM Journal on Discrete Mathematics, volume 20, number 2, 2006, pages 357–371.

• Online Searching with Turn Cost
  (joint work with Sándor P. Fekete and Shmuel Gal)
  Theoretical Computer Science, volume 361, number 2–3, September 2006, pages 342–355. Special issue on approximation and online algorithms.

• Correlation Clustering in General Weighted Graphs
  (joint work with Dotan Emanuel, Amos Fiat, and Nicole Immorlica)
  Theoretical Computer Science, volume 361, number 2–3, September 2006, pages 172–187. Special issue on approximation and online algorithms.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Martin L. Demaine)
  Theory of Computing Systems, volume 39, number 3, June 2006, pages 473–481. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.

• Morpion Solitaire
  (joint work with Martin L. Demaine, Arthur Langerman, and Stefan Langerman)
  Theory of Computing Systems, volume 39, number 3, June 2006, pages 439–453. Special issue of selected papers from the 3rd International Conference on Fun with Algorithms, 2004.

• The Helium Stockpile: A Collaboration in Mathematical Folding Sculpture
  (joint work with Martin L. Demaine and A. Laurie Palmer)
  Leonardo, volume 39, number 3, June 2006, pages 233–235.

• Geometric Restrictions on Producible Polygonal Protein Chains
  (joint work with Stefan Langerman and Joseph O'Rourke)
  Algorithmica, volume 44, number 2, February 2006, pages 167–181. Special issue of selected papers from the 14th Annual International Symposium on Algorithms and Computation, 2003.

• Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  Journal of the ACM, volume 52, number 6, 2005, pages 866–893.

• Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
  (joint work with Ilya Baran)
  International Journal of Computational Geometry and Applications, volume 15, number 4, 2005, pages 327–350. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.

• Optimal Covering Tours with Turn Costs
  (joint work with Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia)
  SIAM Journal on Computing, volume 35, number 3, 2005, pages 531–566.

• Cache-Oblivious B-Trees
  (joint work with Michael A. Bender and Martin Farach-Colton)
  SIAM Journal on Computing, volume 35, number 2, 2005, pages 341–358.

• Representing Trees of Higher Degree
  (joint work with David Benoit, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao)
  Algorithmica, volume 43, number 4, December 2005, pages 275–292.

• PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
  (joint work with Robert A. Hearn)
  Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 72–96. Special issue ``Game Theory Meets Theoretical Computer Science''.

• Games on Triangulations
  (joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
  Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 42–71. Special issue ``Game Theory Meets Theoretical Computer Science''.

• Separating point sets in polygonal environments
  (joint work with Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides)
  International Journal of Computational Geometry and Applications, volume 15, number 4, August 2005, pages 403–419. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.

• Fixed-Parameter Algorithms for (k, r)-Center in Planar Graphs and Map Graphs
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  ACM Transactions on Algorithms, volume 1, number 1, July 2005, pages 33–47.

• Hinged Dissection of Polyominoes and Polyforms
  (joint work with Martin L. Demaine, David Eppstein, Greg N. Frederickson, and Erich Friedman)
  Computational Geometry: Theory and Applications, volume 31, number 3, June 2005, pages 237–262. Special issue of selected papers from the 11th Canadian Conference on Computational Geometry, 1999.

• Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries
  (joint work with David Bremner, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint)
  Discrete & Computational Geometry, volume 33, number 4, April 2005, pages 593–604.

• Fast Allocation and Deallocation with an Improved Buddy System
  (joint work with Gerth Stølting Brodal and J. Ian Munro)
  Acta Informatica, volume 41, number 4–5, March 2005, pages 273–291.

• Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors
  (joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
  Algorithmica, volume 41, number 4, February 2005, pages 245–267.

• Building Blocks and Excluded Sums
  (joint work with Martin L. Demaine, Alan Edelman, Charles E. Leiserson, and Per-Olof Persson)
  SIAM News, volume 38, number 1, January 2005, pages 1, 4, 6.

• Tetris is Hard, Even to Approximate
  (joint work with Ron Breukelaar, Susan Hohenberger, Hendrik Jan Hoogeboom, Walter A. Kosters, and David Liben-Nowell)
  International Journal of Computational Geometry and Applications, volume 14, number 1–2, 2004, pages 41–68.

• Bidimensional Parameters and Local Treewidth
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  SIAM Journal on Discrete Mathematics, volume 18, number 3, 2004, pages 501–511.

• Fun-Sort–-or the Chaos of Unordered Binary Search
  (joint work with Therese Biedl, Timothy Chan, Rudolf Fleischer, Mordecai Golin, James A. King, and J. Ian Munro)
  Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231–236.

• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
  (joint work with MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos)
  Journal of Computer and System Sciences, volume 69, number 2, September 2004, pages 166–195.

• When Can You Fold a Map?
  (joint work with Esther M. Arkin, Michael A. Bender, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena)
  Computational Geometry: Theory and Applications, volume 29, number 1, September 2004, pages 23–46. Special issue of selected papers from the 10th Annual Fall Workshop on Computational Geometry, 2000.

• Finding a Divisible Pair
  (joint work with Stelian Ciurea, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu)
  ACM SIGSAM Bulletin, volume 38, number 3, September 2004, pages 98–100.

• Tight Bounds on Maximal and Maximum Matchings
  (joint work with Therese Biedl, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov)
  Discrete Mathematics, volume 285, number 1–3, August 2004, pages 7–15.

• Diameter and Treewidth in Minor-Closed Graph Families, Revisited
  (joint work with MohammadTaghi Hajiaghayi)
  Algorithmica, volume 40, number 3, August 2004, pages 211–215.

• Proximate Point Searching
  (joint work with John Iacono and Stefan Langerman)
  Computational Geometry: Theory and Applications, volume 28, number 1, May 2004, pages 29–40. Special issue of selected papers from the 14th Canadian Conference on Computational Geometry, 2002.

• Open Problems at the 2002 Dagstuhl Seminar on Algorithmic Combinatorial Game Theory
  (joint work with Rudolf Fleischer, Aviezri S. Fraenkel, and Richard J. Nowakowski)
  Theoretical Computer Science, volume 313, number 3, February 2004, pages 539–543. Special issue on algorithmic combinatorial game theory.

• Solitaire Clobber
  (joint work with Martin L. Demaine and Rudolf Fleischer)
  Theoretical Computer Science, volume 313, number 3, February 2004, pages 325–338. Special issue of selected papers presented at the Schloss Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 2002.

• What is the optimal shape of a city?
  (joint work with Carl M. Bender, Michael A. Bender, and Sándor P. Fekete)
  Journal of Physics A: Mathematical and General, volume 37, number 1, January 2004, pages 147–159.

• Finding Hidden Independent Sets in Interval Graphs
  (joint work with Therese Biedl, Broňa Brejová, Angèle M. Hamel, Alejandro López-Ortiz, and Tomáš Vinař)
  Theoretical Computer Science, volume 310, number 1–3, January 2004, pages 287–307.

• Straightening Polygonal Arcs and Convexifying Polygonal Cycles
  (joint work with Robert Connelly and Günter Rote)
  Discrete & Computational Geometry, volume 30, number 2, September 2003, pages 205–239.

• A Linear Lower Bound on Index Size for Text Retrieval
  (joint work with Alejandro López-Ortiz)
  Journal of Algorithms, volume 48, number 1, August 2003, pages 2–15. Special issue of selected papers from the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001.

• Pushing Blocks is Hard
  (joint work with Martin L. Demaine, Michael Hoffmann, and Joseph O'Rourke)
  Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 21–36. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.

• Interlocked Open and Closed Linkages with Few Joints
  (joint work with Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink)
  Computational Geometry: Theory and Applications, volume 26, number 1, August 2003, pages 37–45. Special issue of selected papers from the 13th Canadian Conference on Computational Geometry, 2001.

• On Universally Easy Classes for NP-complete Problems
  (joint work with Alejandro López-Ortiz and J. Ian Munro)
  Theoretical Computer Science, volume 304, number 1–3, July 2003, pages 471–476.

• Palindrome Recognition Using a Multidimensional Tape
  (joint work with Therese C. Biedl, Jonathan F. Buss, Martin L. Demaine, Mohammadtaghi Hajiaghayi, and Tomáš Vinař)
  Theoretical Computer Science, volume 302, number 1–3, June 2003, pages 475–480.

• Long Proteins with Unique Optimal Foldings in the H-P Model
  (joint work with Oswin Aichholzer, David Bremner, Henk Meijer, Vera Sacristán, and Michael Soss)
  Computational Geometry: Theory and Applications, volume 25, number 1–2, May 2003, pages 139–159. Special issue of selected papers from the 17th European Workshop on Computational Geometry, 2001.

• Ununfoldable Polyhedra with Convex Faces
  (joint work with Marshall Bern, David Eppstein, Eric Kuo, Andrea Mantler, and Jack Snoeyink)
  Computational Geometry: Theory and Applications, volume 24, number 2, February 2003, pages 51–62. Special issue of selected papers from the 4th CGC Workshop on Computational Geometry, 1999.

• K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data
  (joint work with Ziv Bar-Joseph, David K. Gifford, Angèle M. Hamel, Tommi S. Jaakkola, and Nathan Srebro)
  Bioinformatics, volume 19, number 9, 2003, pages 1070–1078. Special issue on Microarray Analysis.

• Hinged Dissection of the Alphabet
  (joint work with Martin L. Demaine)
  Journal of Recreational Mathematics, volume 31, number 3, 2003, pages 204–207.

• Online Routing in Convex Subdivisions
  (joint work with Prosenjit Bose, Andrej Brodnik, Svante Carlsson, Rudolf Fleischer, Alejandro López-Ortiz, Pat Morin, and J. Ian Munro)
  International Journal of Computational Geometry and Applications, volume 12, number 4, August 2002, pages 283–295. Special issue of selected papers from the 11th Annual International Symposium on Algorithms and Computation, 2000.

• Flipturning Polygons
  (joint work with Oswin Aichholzer, Carmen Cortés, Vida Dujmović, Jeff Erickson, Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried T. Toussaint)
  Discrete & Computational Geometry, volume 28, number 2, August 2002, pages 231–253.

• Enumerating Foldings and Unfoldings between Polygons and Polytopes
  (joint work with Martin L. Demaine, Anna Lubiw, and Joseph O'Rourke)
  Graphs and Combinatorics, volume 18, number 1, 2002, pages 93–104.

• Balanced k-Colorings
  (joint work with Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang)
  Discrete Mathematics, volume 254, 2002, pages 19–32.

• A Note on Reconfiguring Tree Linkages: Trees can Lock
  (joint work with Therese Biedl, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides)
  Discrete Applied Mathematics, volume 117, number 1–3, 2002, pages 293–297.

• Locked and Unlocked Polygonal Chains in Three Dimensions
  (joint work with T. Biedl, M. Demaine, S. Lazard, A. Lubiw, J. O'Rourke, M. Overmars, S. Robbins, I. Streinu, G. Toussaint, and S. Whitesides)
  Discrete & Computational Geometry, volume 26, number 3, October 2001, pages 269–281.

• Polygons Cuttable by a Circular Saw
  (joint work with Martin L. Demaine and Craig S. Kaplan)
  Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 69–84. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.

• Reconfiguring Convex Polygons
  (joint work with Oswin Aichholzer, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried T. Toussaint)
  Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 85–95. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.

• Generalized Communicators in the Message Passing Interface
  (joint work with Ian Foster, Carl Kesselman, and Marc Snir)
  IEEE Transactions on Parallel and Distributed Systems, volume 12, number 6, June 2001, pages 610–616.

• Efficient Algorithms for Petersen's Matching Theorem
  (joint work with Therese C. Biedl, Prosenjit Bose, and Anna Lubiw)
  Journal of Algorithms, volume 38, 2001, pages 110–134. Special issue of selected papers from the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000.

• Computational Geometry Column 37
  (joint work with Joseph O'Rourke)
  International Journal of Computational Geometry and Applications, volume 10, number 1, February 2000, pages 103–107. Also appears in SIGACT News, volume 30, number 3, issue #112, September 1999, pages 39–42.

• Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami
  (joint work with Martin L. Demaine and Joseph S. B. Mitchell)
  Computational Geometry: Theory and Applications, volume 16, number 1, 2000, pages 3–21. Special issue of selected papers from the 3rd CGC Workshop on Computational Geometry, 1998.

• C to Java: Converting Pointers into References
  Concurrency: Practice and Experience, volume 10, number 11–13, 1998, pages 851–861.

• Routing Algorithms on Static Interconnection Networks: A Classification Scheme
  (joint work with Sampalli Srinivas)
  International Journal of Computer Systems Science and Engineering, volume 12, number 6, November 1997, pages 359–367.

• A Novel Routing Algorithm for k-ary n-cube Interconnection Networks
  (joint work with Sampalli Srinivas)
  International Journal of High Speed Computing, volume 8, number 1, 1996, pages 81–92.

Book chapters

• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
  (joint work with Robert A. Hearn)
  in Games of No Chance III, to appear.

• All Polygons Flip Finitely… Right?
  (joint work with Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint)
  in Surveys on Discrete and Computational Geometry: Twenty Years Later, edited by J. Goodman, J. Pach, and R. Pollack, Contemporary Mathematics, volume 453, 2008, pages 231–255, American Mathematical Society. Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, June 18–22, 2006, Snowbird, Utah.

• The Complexity of Dyson Telescopes
  (joint work with Martin L. Demaine, Rudolf Fleischer, Robert A. Hearn, and Timo von Oertzen)
  in Games of No Chance III, to appear.

• A Survey of Folding and Unfolding in Computational Geometry
  (joint work with Joseph O'Rourke)
  in Combinatorial and Computational Geometry, edited by Jacob E. Goodman, János Pach, and Emo Welzl, Mathematical Sciences Research Institute Publications, volume 52, August 2005, pages 167–211, Cambridge University Press.

• Sliding-Coin Puzzles
  (joint work with Martin L. Demaine)
  in Tribute to a Mathemagician, 2004, pages 63–72, A K Peters.

• Fold-and-Cut Magic
  (joint work with Martin L. Demaine)
  in Tribute to a Mathemagician, 2004, pages 23–30, A K Peters.

• Geometry and Topology of Polygonal Linkages
  (joint work with Robert Connelly)
  in CRC Handbook of Discrete and Computational Geometry, Second Edition, 2004, chapter 9, pages 197–218.

• Vertex-Unfolding of Simplicial Manifolds
  (joint work with David Eppstein, Jeff Erickson, George W. Hart, and Joseph O'Rourke)
  in Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday, 2003, pages 215–228, Marcer Dekker Inc..

• Infinitesimally Locked Self-Touching Linkages with Applications to Locked Trees
  (joint work with Robert Connelly and Günter Rote)
  in Physical Knots: Knotting, Linking, and Folding of Geometric Objects in R³, edited by Jorge Calvo, Kenneth Millett, and Eric Rawdon, 2002, pages 287–311, American Mathematical Society. Collection of papers from the Special Session on Physical Knotting and Unknotting at the AMS Spring Western Section Meeting, Las Vegas, Nevada, April 21–22, 2001.

• Cache-Oblivious Algorithms and Data Structures
  in Lecture Notes from the EEF Summer School on Massive Data Sets, Lecture Notes in Computer Science, BRICS, University of Aarhus, Denmark, June 27–July 1, 2002, to appear.

• The Complexity of Clickomania
  (joint work with Therese C. Biedl, Martin L. Demaine, Rudolf Fleischer, Lars Jacobsen, and J. Ian Munro)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 389–404, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

• Phutball Endgames are Hard
  (joint work with Martin L. Demaine and David Eppstein)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 351–360, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

• Coin-Moving Puzzles
  (joint work with Martin L. Demaine and Helena A. Verrill)
  in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 405–431, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

Conference papers

• Curved Crease Origami
  (joint work with Duks Koschitz and Martin L. Demaine)
  in Abstracts from Advances in Architectural Geometry (AAG 2008), Vienna, Austria, September 13–16, 2008, to appear.

• Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
  (joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, and Morteza Zadimoghaddam)
  in Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, Massachusetts, August 25–27, 2008, pages 21–34.

• Computational Balloon Twisting: The Theory of Balloon Polyhedra
  (joint work with Martin L. Demaine and Vi Hart)
  in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008.

• Open Problems from CCCG 2007
  (joint work with Joseph O'Rourke)
  in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008, to appear.

• Confluently Persistent Tries for Efficient Version Control
  (joint work with Stefan Langerman and Eric Price)
  in Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), Lecture Notes in Computer Science, volume 5124, Gothenburg, Sweden, July 2–4, 2008, pages 160–172.

• Constraint Logic: A Uniform Framework for Modeling Computation as Games
  (joint work with Robert A. Hearn)
  in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008), College Park, Maryland, June 23–26, 2008, pages 149–162.

• Hinged Dissections Exist
  (joint work with Timothy G. Abbott, Zachary Abel, David Charlton, Martin L. Demaine, and Scott D. Kominers)
  in Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), College Park, Maryland, June 9–11, 2008, pages 110–119.

• Linear Reconfiguration of Cube-Style Modular Robots
  (joint work with Greg Aloupis, Sébastien Collette, Mirela Damian, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer)
  in Proceedings of the 18th Annual International Symposium on Algorithms and Computation, December 17–19, 2007, pages 208–219.

• Vertex Pops and Popturns
  (joint work with Greg Aloupis, Brad Ballinger, Prosenjit Bose, Mirela Damian, Martin L. Demaine, Robin Flatland, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Perouz Taslakian, and Godfried Toussaint)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 137–140.

• On Rolling Cube Puzzles
  (joint work with Kevin Buchin, Maike Buchin, Martin L. Demaine, Dania El-Khechen, Sándor Fekete, Christian Knauer, André Schulz, and Perouz Taslakian)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007.

• Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs
  (joint work with Nadia M. Benbernou, Martin L. Demaine, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 13–16.

• Open Problems from CCCG 2006
  (joint work with Joseph O'Rourke)
  in Proceedings of the 19th Canadian Conference on Computational Geometry (CCCG 2007), Ottawa, Ontario, Canada, August 20–22, 2007, pages 277–280.

• The Stackelberg Minimum Spanning Tree Game
  (joint work with Jean Cardinal, Samuel Fiorini, Gwena\"el Joret, Stefan Langerman, Ilan Newman, and Oren Weimann)
  in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 64–76.

• A Pseudopolynomial Time O(log² n)-Approximation Algorithm for Art Gallery Problems
  (joint work with Ajay Deshpande, Taejung Kim, and Sanjay E. Sarma)
  in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 163–174.

• The Price of Anarchy in Network Creation Games
  (joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam)
  in Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, August 12–15, 2007, pages 292–298.

• Revising Quorum Systems for Energy Conservation in Sensor Networks
  (joint work with Daniela Tulone)
  in Proceedings of the International Conference on Wireless Algorithms, Systems and Applications (WASA 2007), Chicago, Illinois, August 1–3, 2007, pages 147–157.

• An Optimal Decomposition Algorithm for Tree Edit Distance
  (joint work with Shay Mozes, Benjamin Rossman, and Oren Weimann)
  in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, July 9–13, 2007, pages 146–157.

• Linear Reconfiguration of Cube-Style Modular Robots
  (joint work with Greg Aloupis, Sébastien Collette, Mirela Damian, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer)
  in Abstracts from the 12th Encuentros de Geometría Computacional (EGC 2007), June 25–27, 2007, pages 19–34.

• Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity
  (joint work with Martin L. Demaine)
  in Abstracts from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Kyoto, Japan, June 11–15, 2007, to appear.

• Deflating The Pentagon
  (joint work with Martin L. Demaine, Thomas Fevens, Antonio Mesa, Michael Soss, Diane L. Souvaine, Perouz Taslakian, and Godfried Toussaint)
  in Revised Papers from the Kyoto International Conference on Computational Geometry and Graph Theory (KyotoCGGT 2007), Lecture Notes in Computer Science, Kyoto, Japan, June 11–15, 2007, to appear.

• Scheduling to Minimize Gaps and Power Consumption
  (joint work with Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, and Morteza Zadimoghaddam)
  in Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), San Diego, California, June 9–11, 2007, pages 46–54.

• Tight Bounds for Dynamic Convex Hull Queries (Again)
  (joint work with Mihai Pǎtraşcu)
  in Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007), Gyeongju, South Korea, June 6–8, 2007, pages 354–363.

• Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
  (joint work with Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine)
  in Proceedings of the 13th International Meeting on DNA Computing (DNA 2007), Lecture Notes in Computer Science, volume 4848, Memphis, Tennessee, June 4–8, 2007, to appear.

• Wrapping the Mozartkugel
  (joint work with Martin L. Demaine, John Iacono, and Stefan Langerman)
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 14–17.

• Deflating The Pentagon
  (joint work with Martin L. Demaine, Diane L. Souvaine, and Perouz Taslakian)
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 10–13.

• Computational Geometry through the Information Lens
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2007), Graz, Austria, March 19–21, 2007, pages 81.

• Approximation Algorithms via Contraction Decomposition
  (joint work with MohammadTaghi Hajiaghayi and Bojan Mohar)
  in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 278–287.

• Minimizing Movement
  (joint work with MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam)
  in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, January 7–9, 2007, pages 258–267.

• Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction
  (joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
  in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 3–15.

• Approximability for Partitioning Graphs with Supply and Demand
  (joint work with Takehiro Ito, Xiao Zhou, and Takao Nishizeki)
  in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 121–130.

• Origami, Linkages, and Polyhedra: Folding with Algorithms
  in Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Zürich, Switzerland, September 11–13, 2006, pages 1.

• Necklaces, Convolutions, and X + Y
  (joint work with David Bremner, Timothy M. Chan, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian)
  in Proceedings of the 14th Annual European Symposium on Algorithms (ESA 2006), Zürich, Switzerland, September 11–13, 2006, pages 160–171.

• Curves in the Sand: Algorithmic Drawing
  (joint work with Mirela Damian, Martin L. Demaine, Vida Dujmović, Dania El-Khechen, Robin Flatland, John Iacono, Stefan Langerman, Henk Meijer, Suneeta Ramaswami, Diane L. Souvaine, Perouz Taslakian, and Godfried T. Toussaint)
  in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 11–14.

• Polygons Flip Finitely: Flaws and a Fix
  (joint work with Blaise Gassend, Joseph O'Rourke, and Godfried T. Toussaint)
  in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 109–112.

• Open Problems from CCCG 2005
  (joint work with Joseph O'Rourke)
  in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 75–80.

• Linkage Folding: From Erdős to Proteins
  in Proceedings of the 18th Canadian Conference on Computational Geometry (CCCG 2006), August 14–16, 2006, pages 1.

• Sand Drawings and Gaussian Graphs
  (joint work with Martin L. Demaine, Perouz Taslakian, and Godfried T. Toussaint)
  in Proceedings of the 9th Annual Conference of BRIDGES: Mathematical Connections in Art, Music, and Science (BRIDGES 2006), London, England, August 4–8, 2006, pages 79–88.

• Locked and Unlocked Chains of Planar Shapes
  (joint work with Robert Connelly, Martin L. Demaine, Sándor Fekete, Stefan Langerman, Joseph S. B. Mitchell, Ares Ribó, and Günter Rote)
  in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 61–70.

• Plane Embeddings of Planar Graph Metrics
  (joint work with MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Mohammad Moharrami)
  in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 197–206.

• Refolding Planar Polygons
  (joint work with Hayley N. Iben and James F. O'Brien)
  in Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG 2006), Sedona, Arizona, June 5–7, 2006, pages 71–79.

• Voronoi game on graphs and its complexity
  (joint work with Sachio Teramoto and Ryuhei Uehara)
  in Proceedings of the 2nd IEEE Symposium on Computational Intelligence and Games (CIG 2006), Reno, Nevada, May 22–24, 2006, pages 265–271.

• De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)
  (joint work with Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai Pǎtraşcu)
  in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 349–361.

• Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
  (joint work with Boris Aronov, Prosenjit Bose, Joachim Gudmundsson, John Iacono, Stefan Langerman, and Michiel Smid)
  in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 80–92.

• Optimally Adaptive Integration of Univariate Lipschitz Functions
  (joint work with Ilya Baran and Dmitriy A. Katz)
  in Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006), Valdivia, Chile, March 20–24, 2006, pages 142–153.

• Combination Can Be Hard: Approximability of the Unique Coverage Problem
  (joint work with Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour)
  in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 162–171.

• Lower Bounds for Asymmetric Communication Channels and Distributed Source Coding
  (joint work with Micah Adler, Nicholas J. A. Harvey, and Mihai Pǎtraşcu)
  in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, Florida, January 22–24, 2006, pages 251–260.

• Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
  (joint work with Boris Aronov, Prosenjit Bose, Joachim Gudmundsson, John Iacono, Stefan Langerman, and Michiel Smid)
  in Abstracts from the 15th Annual Fall Workshop on Computational Geometry, Philadelphia, Pennsylvania, November 18–19, 2005, pages 51–52.

• Kinematics and Dynamics of Nanostructured Origami
  (joint work with Paul Stellman, Will Arora, Satoshi Takahashi, and George Barbastathis)
  in Proceedings of the ASME International Mechanical Engineering Congress and Exposition, Orlando, Florida, November 5–11, 2005, pages 541–548.

• Design and Control of Nanostructured Origami
  (joint work with Paul Stellman, Will Arora, Satoshi Takahashi, and George Barbastathis)
  in Proceedings of the 3rd International Symposium on Nanomanufacturing, Orlando, Florida, November 3–5, 2005.

• PersiFS: A Versioned File System with an Efficient Representation
  (joint work with Dan R. K. Ports and Austin T. Clements)
  in Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP 2005), Brighton, United Kingdom, October 23–26, 2005.

• Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring
  (joint work with MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi)
  in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, PA, October 23–25, 2005, pages 637–646.

• Optimizing a 2D Function Satisfying Unimodality Properties
  (joint work with Stefan Langerman)
  in Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science, volume 3669, Mallorca, Spain, October 3–6, 2005, pages 887–898.

• Realizing Partitions Respecting Full and Partial Order Information
  (joint work with Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides)
  in Proceedings of the 16th Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), Victoria, Australia, September 18–21, 2005, pages 105–114.

• Communication-Aware Processor Allocation for Supercomputers
  (joint work with Michael A. Bender, David P. Bunde, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips)
  in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 169–181.

• Subquadratic Algorithms for 3SUM
  (joint work with Ilya Baran and Mihai Pǎtraşcu)
  in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 409–421.

• Hinged Dissection of Polypolyhedra
  (joint work with Martin L. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
  in Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005), Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 205–217.

• Open Problems from CCCG 2004
  (joint work with Joseph O'Rourke)
  in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 303–306.

• Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane
  (joint work with Timothy Abbott, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung)
  in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 61–64.

• The Distance Geometry of Deep Rhythms and Scales
  (joint work with Francisco Gomez-Martin, Henk Meijer, David Rappaport, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David R. Wood)
  in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), Windsor, Ontario, Canada, August 10–12, 2005, pages 163–166.

• Deploying Sensor Networks with Guaranteed Capacity and Fault Tolerance
  (joint work with Jonathan L. Bredin, MohammadTaghi Hajiaghayi, and Daniela Rus)
  in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2005), Urbana-Champaign, Illinois, May 25–28, 2005, pages 309–319.

• Mobile-Assisted Localization in Wireless Sensor Networks
  (joint work with Nissanka B. Priyantha, Hari Balakrishnan, and Seth Teller)
  in Proceedings of the 24th Annual Joint Conference of the IEEE Communications Society on Computer Communications (INFOCOM 2005), volume 1, Miami, Florida, March 13–17, 2005, pages 172–183.

• Bidimensionality: New Connections between FPT Algorithms and PTASs
  (joint work with MohammadTaghi Hajiaghayi)
  in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 590–601.

• Graphs Excluding a Fixed Minor have Grids as Large as Treewidth, with Combinatorial and Algorithmic Applications through Bidimensionality
  (joint work with MohammadTaghi Hajiaghayi)
  in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 682–689.

• Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and Ultrametrics
  (joint work with Noga Alon, Mihai Bădoiu, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos)
  in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, British Columbia, Canada, January 23–25, 2005, pages 650–659.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Martin L. Demaine)
  in Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, volume 3341, Hong Kong, China, 2004, pages 1.

• Hinged Dissection of Polypolyhedra
  (joint work with Martin L. Demaine, Jeffrey F. Lindy, and Diane L. Souvaine)
  in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 16–17.

• Folding Paper Shopping Bags
  (joint work with Devin J. Balkcom and Martin L. Demaine)
  in Abstracts from the 14th Annual Fall Workshop on Computational Geometry, Cambridge, Massachusetts, November 19–20, 2004, pages 14–15.

• EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management
  (joint work with Ben Leong and Barbara Liskov)
  in Proceedings of the IEEE International Conference on Networks (ICON 2004), volume 1, Singapore, November 16–19, 2004, pages 270–276.

• Dynamic Optimality–-Almost
  (joint work with Dion Harmon, John Iacono, and Mihai Pǎtraşcu)
  in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, October 17–19, 2004, pages 484–490.

• Grid Vertex-Unfolding Orthostacks
  (joint work with John Iacono and Stefan Langerman)
  in Revised Selected Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2004), Lecture Notes in Computer Science, volume 3742, Tokyo, Japan, October 8–11, 2004, pages 76–82.

• Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth
  (joint work with MohammadTaghi Hajiaghayi)
  in Proceedings of the 12th International Symposium on Graph Drawing (GD 2004), Lecture Notes in Computer Science, volume 3383, Harlem, New York, September 29–October 2, 2004, pages 517–533.

• The Bidimensional Theory of Bounded-Genus Graphs
  (joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
  in Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), Prague, Czech Republic, August 22–27, 2004, pages 191–203.

• Continuous Foldability of Polygonal Paper
  (joint work with Satyan L. Devadoss, Joseph S. B. Mitchell, and Joseph O'Rourke)
  in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 64–67.

• Unfolding Polyhedral Bands
  (joint work with Greg Aloupis, Stefan Langerman, Pat Morin, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
  in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 60–63.

• Open Problems from CCCG 2003
  (joint work with Joseph O'Rourke)
  in Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG 2004), Montréal, Québec, Canada, August 9–11, 2004, pages 209–211.

• Refolding Planar Polygons
  (joint work with Hayley N. Iben and James F. O'Brien)
  in Technical Sketchs of the 31st International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 2004), Los Angeles, California, August 8–12, 2004.

• Lower Bounds for Dynamic Connectivity
  (joint work with Mihai Pǎtraşcu)
  in Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), Chicago, Illinois, June 13–15, 2004, pages 546–553.

• An Energy-Driven Approach to Linkage Unfolding
  (joint work with Jason Cantarella, Hayley Iben, and James O'Brien)
  in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 134–143.

• Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
  (joint work with Ilya Baran)
  in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 220–229.

• Low-Dimensional Embedding with Extra Information
  (joint work with Mihai Bădoiu, MohammadTaghi Hajiaghayi, and Piotr Indyk)
  in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 320–329.

• Geodesic Ham-Sandwich Cuts
  (joint work with Prosenjit Bose, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin)
  in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 1–9.

• Separating point sets in polygonal environments
  (joint work with Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides)
  in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 10–16.

• Morpion Solitaire
  (joint work with Martin L. Demaine, Arthur Langerman, and Stefan Langerman)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 53–64.

• Finding a Divisible Pair and a Good Wooden Fence
  (joint work with Stelian Ciurea, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 206–219.

• PushPush-k is PSPACE-Complete
  (joint work with Michael Hoffmann and Markus Holzer)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 159–170.

• Puzzles, Art, and Magic with Algorithms
  (joint work with Martin L. Demaine)
  in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 7–15.

• A Simplified and Dynamic Unified Structure
  (joint work with Mihai Bădoiu)
  in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 466–473.

• Bidimensional Parameters and Local Treewidth
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 109–118.

• Optimizing a 2D Function Satisfying Unimodality Properties
  (joint work with Stefan Langerman)
  in Abstracts from the 20th European Workshop on Computational Geometry (EuroCG 2004), Seville, Spain, March 24–26, 2004, pages 107–110.

• Retroactive Data Structures
  (joint work with John Iacono and Stefan Langerman)
  in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 274–283.

• Tight Bounds for the Partial-Sums Problem
  (joint work with Mihai Pǎtraşcu)
  in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 20–29.

• Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications
  (joint work with MohammadTaghi Hajiaghayi)
  in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 833–842.

• Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 823–832.

• Interpolation Search for Non-Independent Data
  (joint work with Thouis Jones and Mihai Pǎtraşcu)
  in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 522–523.

• Geometric Restrictions on Producible Polygonal Protein Chains
  (joint work with Stefan Langerman and Joseph O'Rourke)
  in Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), Lecture Notes in Computer Science, volume 2906, Kyoto, Japan, December 15–17, 2003, pages 395–404.

• Anchor-Free Distributed Localization in Sensor Networks
  (joint work with Nissanka B. Priyantha, Hari Balakrishnan, and Seth Teller)
  in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys 2003), Los Angeles, California, USA, November 5–7, 2003, pages 340–341.

• Identifying Frequent Items in Sliding Windows over On-Line Packet Streams
  (joint work with Lukasz Golab, David DeHaan, Alejandro López-Ortiz, and J. Ian Munro)
  in Proceedings of the ACM SIGCOMM Internet Measurement Conference (IMC 2003), Miami, Florida, October 27–29, 2003, pages 173–178.

• Planar Embeddings of Graphs with Specified Edge Lengths
  (joint work with Sergio Cabello and Günter Rote)
  in Proceedings of the 11th Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, volume 2912, Perugia, Italy, September 21–24, 2003, pages 283–294.

• Optimal Dynamic Video-On-Demand using Adaptive Broadcasting
  (joint work with Therese Biedl, Alexander Golynski, Joseph D. Horton, Alejandro López-Ortiz, Guillaume Poirier, and Claude-Guy Quimper)
  in Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003), Lecture Notes in Computer Science, volume 2832, Budapest, Hungary, September 15–20, 2003, pages 90–101.

• Correlation Clustering with Partial Information
  (joint work with Nicole Immorlica)
  in Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM-APPROX 2003), Princeton, New Jersey, August 24–26, 2003, pages 1–13.

• Hinged Dissection of Polygons is Hard
  (joint work with Robert A. Hearn and Greg N. Frederickson)
  in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 98–102.

• On the Complexity of Halfspace Volume Queries
  (joint work with Jeff Erickson and Stefan Langerman)
  in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 159–160.

• Open Problems from CCCG 2002
  (joint work with Joseph O'Rourke)
  in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 178–181.

• Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries
  (joint work with David Bremner, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint)
  in Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS 2003), Lecture Notes in Computer Science, volume 2748, Ottawa, Ontario, Canada, July 30–August 1, 2003, pages 451–461.

• Tetris is Hard, Even to Approximate
  (joint work with Susan Hohenberger and David Liben-Nowell)
  in Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, July 25–28, 2003, pages 351–363.

• Finding Hidden Independent Sets in Interval Graphs
  (joint work with Therese Biedl, Broňa Brejová, Angèle M. Hamel, Alejandro López-Ortiz, and Tomáš Vinař)
  in Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003), Big Sky, Montana, July 25–28, 2003, pages 182–191.

• Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs
  (joint work with Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos)
  in Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Eindhoven, The Netherlands, June 30–July 4, 2003, pages 829–844.

• Geometric Games on Triangulations
  (joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
  in Abstracts from the 19th European Workshop of Computational Geometry (EuroCG 2003), Bonn, Germany, March 24–26, 2003, pages 89–92.

• Quartering a Square Optimally
  (joint work with Prosenjit Bose, John Iacono, and Stefan Langerman)
  in Abstracts from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), Tokyo, Japan, December 6–9, 2002, pages 5–6.

• Playing with Triangulations
  (joint work with Oswin Aichholzer, David Bremner, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia)
  in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), Lecture Notes in Computer Science, volume 2866, Tokyo, Japan, December 6–9, 2002, pages 22–37.

• Flat-State Connectivity of Linkages under Dihedral Motions
  (joint work with Greg Aloupis, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark Overmars, Michael Soss, Ileana Streinu, and Godfried Toussaint)
  in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 369–380.

• Exponential Speedup of Fixed-Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs
  (joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
  in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, volume 2518, Vancouver, British Columbia, Canada, November 20–23, 2002, pages 262–273.

• An Energy-Driven Approach to Linkage Unfolding
  (joint work with Jason Cantarella, Hayley Iben, and James O'Brien)
  in Abstracts from the 12th Annual Fall Workshop on Computational Geometry, Piscataway, New Jersey, November 14–15, 2002.

• Tetris is Hard, Even to Approximate
  (joint work with Susan Hohenberger and David Liben-Nowell)
  in Abstracts from the 12th Annual Fall Workshop on Computational Geometry, Piscataway, New Jersey, November 14–15, 2002.

• Frequency Estimation of Internet Packet Streams with Limited Space
  (joint work with Alejandro López-Ortiz and J. Ian Munro)
  in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 348–360.

• Two Simplified Algorithms for Maintaining Order in a List
  (joint work with Michael A. Bender, Richard Cole, Martin Farach-Colton, and Jack Zito)
  in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 152–164.

• Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy
  (joint work with Michael A. Bender, Richard Cole, and Martin Farach-Colton)
  in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 139–151.

• Efficient Tree Layout in a Multilevel Memory Hierarchy
  (joint work with Michael A. Bender and Martin Farach-Colton)
  in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 165–173.

• 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
  (joint work with MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos)
  in Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2002), Lecture Notes in Computer Science, volume 2462, Rome, Italy, September 17–21, 2002, pages 67–80.

• K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data
  (joint work with Ziv Bar-Joseph, David K. Gifford, Angèle M. Hamel, Tommi S. Jaakkola, and Nathan Srebro)
  in Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI 2002), Rome, Italy, September 17–21, 2002, pages 506–520.

• Open Problems from CCCG 2001
  (joint work with Joseph O'Rourke)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002.

• Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles
  (joint work with Therese Biedl, Timothy M. Chan, Martin L. Demaine, Paul Nijjar, Ryuhei Uehara, and Ming-wei Wang)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 105–108.

• Push-2-F is PSPACE-Complete
  (joint work with Robert A. Hearn and Michael Hoffmann)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 31–35.

• Computing Signed Permutations of Polygons
  (joint work with Greg Aloupis, Prosenjit Bose, Stefan Langerman, Henk Meijer, Mark Overmars, and Godfried T. Toussaint)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002.

• Proximate Point Searching
  (joint work with John Iacono and Stefan Langerman)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 1–4.

• Flat-State Connectivity of Chains with Fixed Acute Angles
  (joint work with Greg Aloupis, Henk Meijer, Joseph O'Rourke, Ileana Streinu, and Godfried Toussaint)
  in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), Lethbridge, Alberta, Canada, August 12–14, 2002, pages 27–30.

• Solitaire Clobber
  (joint work with Martin L. Demaine and Rudolf Fleischer)
  in Proceedings of the 3rd International Conference on Computers and Games (CG 2002), Lecture Notes in Computer Science, volume 2883, Edmonton, Alberta, Canada, July 25–27, 2002, pages 188–200.

• The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications
  (joint work with Robert A. Hearn)
  in Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Lecture Notes in Computer Science, volume 2380, Malaga, Spain, July 8–13, 2002, pages 401–413.

• Robot Localization without Depth Perception
  (joint work with Alejandro López-Ortiz and J. Ian Munro)
  in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), Lecture Notes in Computer Science, volume 2368, Turku, Finland, July 3–5, 2002, pages 249–259.

• Interlocked Open Linkages with Few Joints
  (joint work with Stefan Langerman, Joseph