Erik D. Demaine

Massachusetts Inst. Tech., Lab. for Computer Science
http://theory.lcs.mit.edu/~edemaine/
edemaine@mit.edu

Author, editor, or reviewer of:

• $K$-ary clustering with optimal leaf ordering for gene expression data
• 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
• A disk-packing algorithm for an origami magic trick
• A survey of folding and unfolding in computational geometry
• Approximation algorithms via contraction decomposition
• Bidimensional parameters and local treewidth
• Bidimensionality: new connections between FPT algorithms and PTASs
• Computational geometry column 37
• Computing extreme origami bases
• Efficient algorithms for Petersen's matching theorem
• Enumerating foldings and unfoldings between polygons and polytopes
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Examples, counterexamples, and enumeration results for foldings and unfoldings between polygons and polytopes
• Exponential speedup of fixed parameter algorithms on graphs excluding a graph with one crossing as a minor
• Fast algorithms for hard graph problems: bidimensionality, minors, and local treewidth
• Fixed parameter algorithms for $(k,r)$-center in planar graphs and map graphs
• Fixed-parameter algorithms for minor-closed graphs (of locally bounded treewidth)
• Fixed-parameter algorithms for the $(k,r)$-center in planar graphs and map graphs
• Fold-and-cut magic{}
• Folding and cutting paper
• Folding and one straight cut suffice
• Folding and unfolding linkages, paper, and polyhedra
• Folding flat silhouettes and wrapping polyhedral packages: new results in computational origami
• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
• Hinged dissection of polygons is hard
• Hinged dissection of polypolyhedra
• Hinged dissections of polyominoes and polyforms
• Logarithmic lower bounds in the cell-probe model
• Lower bounds for dynamic connectivity
• Open problems from CCCG 2001
• Phutball endgames are hard
• Playing games with algorithms: algorithmic combinatorial game theory
• Reaching folded states of a rectangular piece of paper
• Recent results in computational origami
• Straightening polygonal arcs and convexifying polygonal cycles
• The CCCG 2001 logo
• Tighter bounds on the genus of nonorthogonal polyhedra built from rectangles
• Ununfoldable polyhedra
• Ununfoldable polyhedra with convex faces
• Ununfoldable polyhedra with triangular faces
• Vertex-unfoldings of simplicial manifolds
• Vertex-unfoldings of simplicial polyhedra
• Tribute to a Mathemagician