**Happy endings for flip graphs.**

D. Eppstein.

arXiv:cs.CG/0610092.

*23rd ACM Symp. Comp. Geom.,*Gyeongju, South Korea, 2007, pp. 92–101.

*J. Computational Geometry*1 (1): 3–28, 2010.We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

**Optimally fast incremental Manhattan plane embedding and planar tight span construction**.

D. Eppstein.

arXiv:0909.1866.

*J. Computational Geometry*2 (1): 144–182, 2011.Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L

_{1}plane.**Steinitz theorems for orthogonal polyhedra**.

D. Eppstein and E. Mumford.

arXiv:0912.0537.

*26th Eur. Worksh. Comp. Geom.*, Dortmund, Germany, 2010.

*26th ACM Symp. Comp. Geom.,*Snowbird, Utah, 2010, pp. 429–438.

*J. Computational Geometry*5 (1): 179–244, 2014.We provide a graph-theoretic characterization of three classes of nonconvex polyhedra with axis-parallel sides, analogous to Steinitz's theorem characterizing the graphs of convex polyhedra.

The journal version has the slightly different title "Steinitz theorems for simple orthogonal polyhedra".

(Slides)

**Adjacency-preserving spatial treemaps**.

K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira.

arXiv:1105.0398.

*12th International Symposium on Algorithms and Data Structures (WADS 2011)*, New York, 2011.

Springer,*Lecture Notes in Comp. Sci.*6844, 2011, pp. 159–170.

*J. Computational Geometry*7 (1): 100–122, 2016.We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.

**Planar and poly-arc Lombardi drawings**.

C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler.

*Proc. 19th Int. Symp. Graph Drawing*, Eindhoven, The Netherlands, 2011.

Springer,*Lecture Notes in Comp. Sci.*7034, 2012, pp. 308–319.

arXiv:1109.0345.

*J. Computational Geometry*9 (1): 328–355, 2018.We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.

**Strict confluent drawing**.

D. Eppstein, D. Holten, M. Löffler, M. Nöllenburg, and B. Speckmann, and K. Verbeek.

arXiv:1308.6824.

*21st Int. Symp. Graph Drawing*, Bordeaux, France, 2013.

Springer,*Lecture Notes in Comp. Sci.*8242, 2013, pp. 352–363.

*J. Computational Geometry*7 (1): 22–46, 2016.A confluent drawing of a graph is a set of points and curves in the plane with the property that two vertices are adjacent in the graph if and only if the corresponding points can be connected to each other by smooth paths in the drawing. We define a variant of confluent drawing, strict confluent drawing, in which a smooth path between two vertices (if it exists) must be unique. We show that it is NP-complete to test whether such drawings exist, in contrast to unrestricted confluence for which the complexity remains open. Additionally, we show that finding outerplanar drawings (in which the points are on the boundary of a disk and the curves are interior to it) with a fixed cyclic vertex ordering can be performed in polynomial time. We use circle packings to find nice versions of these drawings in which all tracks are represented by piecewise-circular curves.

**Flat foldings of plane graphs with prescribed angles and edge lengths**.

Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.

arXiv:1408.6771.

*22nd Int. Symp. Graph Drawing*, Würzburg, Germany, 2014.

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 272–283.

*J. Computational Geometry*9 (1): 74–93, 2018.Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.

**Rigid origami vertices: Conditions and forcing sets**.

Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.

arXiv:1507.01644.

*J. Computational Geometry*7 (1): 171–184, 2016.We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.

**Maximizing the sum of radii of disjoint balls or disks**.

D. Eppstein.

arXiv:1607.02184.

*Proc. 28th Canadian Conference on Computational Geometry*, Vancouver, BC, Canada, 2016, pp. 260–265.

*J. Computational Geometry*8 (1): 316–339, 2017.

We show how to find a system of disjoint balls with given centers, maximizing the sum of radius of the balls. Our algorithm takes cubic time in arbitrary metric spaces and can be sped up to subquadratic time in Euclidean spaces of any bounded dimension.

(Slides)

**Covering many points with a small-area box**.

M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.

arXiv:1612.02149.

*J. Computational Geometry*, to appear.We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.

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

Semi-automatically filtered from a common source file.