Search filters

List of works by Erik Demaine

1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor

article published in 2002

A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems

Algorithms for Solving Rubik’s Cubes

An Optimal Decomposition Algorithm for Tree Edit Distance

An energy-driven approach to linkage unfolding

An optimal decomposition algorithm for tree edit distance

Area-Optimal Simple Polygonalizations: The CG Challenge 2019

scientific article published in 2022

Bidimensional Parameters and Local Treewidth

Blowing Up Polygonal Linkages

article

Cache-Oblivious B-Trees

Common Unfoldings of Polyominoes and Polycubes

Developing a tetramonohedron with minimum cut length

scientific article published in 2023

Diameter and Treewidth in Minor-Closed Graph Families, Revisited

scientific article (publication date: 9 August 2004)

Dynamic Optimality—Almost

article by Erik D. Demaine et al published January 2007 in SIAM Journal on Computing

Efficient Algorithms for Petersen's Matching Theorem

Enumerating Foldings and Unfoldings Between Polygons and Polytopes

Every Author as First Author

scientific article (April 2023)

Finding hidden independent sets in interval graphs

Geometric Folding Algorithms

scholarly article published 2007

Geometric Folding Algorithms

2007 mathematics book by Demaine and O'Rourke

Green Balance

decorative artwork by Erik Demaine, Martin Demaine, Green Balance, 2011, Mi-Teintes watercolor paper

Hinged dissections exist

article published in 2008

Hugging Circles

decorative artwork by Erik Demaine, Martin Demaine, Hugging Circles, 2011, Zanders Elefantenhaut paper (elephant hide paper)

Interlocked open and closed linkages with few joints

K-ary clustering with optimal leaf ordering for gene expression data

scientific article

Linearity of grid minors in treewidth with applications through bidimensionality

scientific article (publication date: 2008)

Logarithmic Lower Bounds in the Cell-Probe Model

article

Minimal Locked Trees

scientific article published in 2009

Morpion Solitaire

Natural Cycles

decorative artwork by Martin Demaine, Erik Demaine, Natural Cycles, 2009, Zanders Elefantenhaut paper (elephant hide paper)

On the complexity of reconfiguration problems

scientific article published in March 2011

Ordinal embeddings of minimum relaxation

article published in 2008

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

scholarly article by David Bremner et al published 21 January 2005 in Discrete and Computational Geometry

Palindrome recognition using a multidimensional tape

Particle computation: Designing worlds to control robot swarms with only global signals

Planar Embeddings of Graphs with Specified Edge Lengths

Reconfigurable asynchronous logic automata

Remarks on Separating Words

Retroactive data structures

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

scholarly article by Erik D. Demaine et al published 1 November 2005 in Journal of the ACM

Subquadratic Algorithms for 3SUM

scholarly article by Ilya Baran et al published 9 September 2007 in Algorithmica

Ununfoldable polyhedra with convex faces

You Should Be Scared of German Ghost

article