**Separator based sparsification II: edge and vertex connectivity**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.

*SIAM J. Computing*28 (1): 341–381, 1999.Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.

**Parallel construction of quadtrees and quality triangulations**.

M. Bern, D. Eppstein, and S.-H. Teng.

*3rd Worksh. Algorithms and Data Structures,*Montreal, 1993.

Springer,*Lecture Notes in Comp. Sci.*709, 1993, pp. 188–199.

Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.

*Int. J. Comp. Geom. & Appl.*9 (6): 517–532, 1999.A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.

(BibTeX – CiteSeer – Citations – ACM DL)

**Subgraph isomorphism in planar graphs and related problems**.

D. Eppstein.

Tech. Rep. 94-25, ICS, UCI, 1994.

*6th ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1995, pp. 632–640.

arXiv:cs.DS/9911003.

*J. Graph Algorithms and Applications*3 (3): 1–27, 1999.Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.

(BibTeX – Citations – Citations from MIT hypertext bibliography – CiteSeer (SODA) – CiteSeer (JGAA))

**Linear complexity hexahedral mesh generation**.

D. Eppstein.

Tech. Rep. 95-51, ICS, UCI, 1995.

*12th ACM Symp. Comp. Geom.,*Philadelphia, 1996, pp. 58–67.

arXiv:cs.CG/9809109.

*Comp. Geom. Theory & Applications*12: 3–16, 1999 (special issue for 12th SCG).Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.

(BibTeX – Citations – SCG paper – SCG talk slides – CiteSeer – ACM DL (CGTA))

**Spanning trees and spanners**.

D. Eppstein.

Tech. Rep. 96-16, ICS, UCI, 1996.

*Handbook of Computational Geometry,*J.-R. Sack and J. Urrutia, eds., Elsevier, 1999, pp. 425–461.Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.

(BibTeX – Citations – CiteSeer)

**Optimal point placement for mesh smoothing**.

N. Amenta, M. Bern, and D. Eppstein.

*8th ACM-SIAM Symp. Discrete Algorithms,*New Orleans, 1997, pp. 528–537.

Symp. Computational Geometry Approaches to Mesh Generation, SIAM 45th Anniversary Mtg., Stanford, 1997.

arXiv:cs.CG/9809081.

*J. Algorithms*30: 302–322, 1999 (special issue for SODA 1997).We study finite element mesh smoothing problems in which we move vertex locations to optimize the shapes of nearby triangles. Many such problems can be solved in linear time using generalized linear programming; we also give efficient algorithms for some non-LP-type mesh smoothing problems. One lemma may be of independent interest: the locus of points in R

^{d}from which a d-1 dimensional convex set subtends a given solid angle is convex.(BibTeX – SODA paper – Citations – CiteSeer – ACM DL)

**Dynamic graph algorithms**.

D. Eppstein, Z. Galil, and G.F. Italiano.

Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.

*Algorithms and Theoretical Computing Handbook,*M. J. Atallah, ed., CRC Press, 1999, chapter 8.

2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.(BibTeX – Citations – CiteSeer)

**Quadrilateral meshing by circle packing**.

M. Bern and D. Eppstein.

*2nd CGC Worksh. Computational Geometry*, Durham, North Carolina, 1997.

*6th Int. Meshing Roundtable,*Park City, Utah, 1997, pp. 7–19.

arXiv:cs.CG/9908016.

*Int. J. Comp. Geom. & Appl.*10 (4): 347–360, 2000.We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:

- The elements form the cells of a Voronoi diagram,
- The elements each have two opposite 90 degree angles,
- All elements are kites, or
- All angles are at most 120 degrees.

*n*). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.(BibTeX – Citations – CiteSeer)

**Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions**.

D. Eppstein and J. Erickson.

*14th ACM Symp. Comp. Geom.,*Minneapolis, 1998, pp. 58–67.

*Disc. Comp. Geom.*22 (4): 569–592, 1999 (special issue for SCG 1998).We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the straight skeleton of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.

(Jeff's publications page and copy of the journal version – BibTeX – Citations – CiteSeer)

**Geometric thickness of complete graphs**.

M. Dillencourt, D. Eppstein, and D. S. Hirschberg.

*6th Int. Symp. Graph Drawing,*Montreal, August 1998.

Springer,*Lecture Notes in Comp. Sci.*1547, 1998, pp. 102–110.

arXiv:math.CO/9910185.

*J. Graph Algorithms and Applications*4 (3): 5–17, 2000 (special issue for GD98).We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.

(Springer abstract – BibTeX – CiteSeer – Citations – ACM DL – GDEA)

**Diameter and treewidth in minor-closed graph families**.

D. Eppstein.

arXiv:math.CO/9907126.

*Algorithmica*27: 275–291, 2000 (special issue on treewidth, graph minors, and algorithms).This paper introduces the

*diameter-treewidth property*(later known as*bounded local treewidth*): a functional relationship between the diameter of its graph and its treewidth. Previously known results imply that planar graphs have bounded local treewidth; we characterize the other minor-closed families with this property. Specifically, minor-closed family F has bounded local treewidth if and only if there exists an*apex graph*G that is not in F; an apex graph is a graph that can be made planar by removing a single vertex. The minor-free families that exclude an apex graph (and therefore have bounded local treewidth) include the bounded-genus graphs (for which, as with planar graphs, we show a linear bound for the treewidth as a function of the diameter) and K_{3,a}-free graphs. As a consequence, subgraph isomorphism for subgraphs of bounded size and approximations to several NP-hard optimization problems can be computed efficiently on these graphs, extending previous results for planar graphs.Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version. Since its publication, there have been many more works on local treewidth. The class of problems that could be solved quickly on graphs of bounded local treewidth was extended and classified by Frick and Grohe, "Deciding first-order properties of locally tree-decomposable structures",

*J. ACM*48: 1184–1206, 2001; the proof that bounded local treewidth is equivalent to having an excluded apex minor was simplified, and the dependence of the treewidth on diameter improved, by a subsequent paper of Demaine and Hajiaghayi, "Diameter and treewidth in minor-closed graph families, revisited",*Algorithmica*40: 211–215, 2004. The concept of local treewidth is the basis for the theory of*bidimensionality*, a general framework for fixed-parameter-tractable algorithms and approximation algorithms in minor-closed graph families; for a survey, see Demaine and Hajiaghayi, "The bidimensionality theory and its algorithmic applications",*The Computer J.*51: 292–302, 2008.**Shortest paths in an arrangement with**.*k*line orientations

D. Eppstein and D. Hart.

*10th ACM-SIAM Symp. Discrete Algorithms,*Baltimore, 1999, pp. 310–316.We show how to find shortest paths between two points on the lines of an arrangement of

*n*lines with*k*distinct orientations, in time O(*n*+*k*^{2}).(BibTeX – SODA paper – Citations – CiteSeer)

**A disk-packing algorithm for an origami magic trick**.

M. Bern, E. Demaine, D. Eppstein, and B. Hayes.

*Int. Conf. Fun with Algorithms*, Elba, June 1998.

Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.

*Origami*, A K Peters, 2002, pp. 17–28.^{3}: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001)We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.

(preprint at Erik's web site – BibTeX – CiteSeer)

**Algorithms for coloring quadtrees**.

M. Bern, D. Eppstein, and B. Hutchings.

arXiv:cs.CG/9907030.

*Algorithmica*32 (1): 87–94, 2002.We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.

**Incremental and decremental maintenance of planar width**.

D. Eppstein.

arXiv:cs.CG/9809038.

*10th ACM-SIAM Symp. Discrete Algorithms,*Baltimore, 1999, pp. S899-S900.

*J. Algorithms*37 (2): 570–577, 2000.We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(

*n*^{c}) per update for any*c*> 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.(BibTeX – Citations – SODA talk slides – ACM DL)

**Setting parameters by example**.

D. Eppstein.

arXiv:cs.DS/9907001.

*40th IEEE Symp. Foundations of Comp. Sci.*, 1999, pp. 309–318.

*SIAM J. Computing*32 (3): 643–653, 2003.We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We use low-dimensional linear programming and geometric sampling techniques to solve such problems for minimum spanning trees, shortest paths, and other optimal subgraph problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

(BibTeX – Citations – ACM DL (FOCS) – ACM DL (SJC))

**Ununfoldable polyhedra**.

M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.

arXiv:cs.CG/9908003.

Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.

*11th Canad. Conf. Comp. Geom.,*1999.

4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.

*Comp. Geom. Theory & Applications*(special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.

Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.

(BibTeX – Erik's publication page – CiteSeer – ACM DL)

**Hinged dissections of polyominos and polyforms**.

E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.

arXiv:cs.CG/9907018.

*11th Canad. Conf. Comp. Geom.,*1999.

*Computational Geometry: Theory and Applications*31 (3): 237–262, 2005 (special issue for 11th CCCG).We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.

(BibTeX – Erik's CCCG publication page – Erik's CGTA publication page – Citations)

**Emerging challenges in computational topology**.

M. Bern, D. Eppstein, et al.

arXiv:cs.CG/9909001.

This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.

(BibTeX – Citations – CiteSeer)

**Tangent spheres and triangle centers**.

D. Eppstein.

arXiv:math.MG/9909152.

*Amer. Math. Monthly*108 (1): 63–66, 2001.Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.

(BibTeX – Citations – CiteSeer)

**Multivariate regression depth**.

M. Bern and D. Eppstein.

arXiv:cs.CG/9912013.

*16th ACM Symp. Comp. Geom.,*Hong Kong, 2000, pp. 315–321.

*Disc. Comp. Geom.*28 (1): 1–17, 2002.We generalize regression depth to k-flats. The k=0 case gives the classical notion of center points. We prove that for any set of n points in R

^{d}there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat. The full version of this paper also includes results from "Computing the Depth of a Flat".(BibTeX – SCG paper – Citations – CiteSeer)

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.