**Horizon theorems for lines and polygons**.

M. Bern, D. Eppstein, P. Plassman, and F. Yao.

*Discrete and Computational Geometry: Papers from the DIMACS Special Year*, J. Goodman, R. Pollack, and W. Steiger, eds.,

*DIMACS Series in Discrete Mathematics and Theoretical Computer Science*6, Amer. Math. Soc., 1991, 45–66.The total complexity of the cells in a line arrangement that are cut by another line is at most 15

*n*/2. The complexity of cells cut by a convex*k*-gon is O(*n*α(*n,**k*)). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.**The expected extremes in a Delaunay triangulation**.

M. Bern, D. Eppstein, and F. Yao.

*18th Int. Coll. Automata, Languages and Programming,*Madrid, Spain, 1991.

Springer,*Lecture Notes in Comp. Sci.*510, 1991, 674–685.

*Int. J. Comp. Geom. & Appl.*1 (1): 79–92, 1991.Discusses the expected behavior of Delaunay triangulations for points chosen uniformly at random (without edge effects). The main result is that within a region containing \(n\) points, the expected maximum degree is \(O(\log n / \log\log n)\).

**Equipartitions of graphs**.

D. Eppstein, J. Feigenbaum, and C.L. Li.

*Discrete Mathematics*91 (3): 239–248, 1991.Considers partitions of the vertices of a graph into equal subsets, with few pairs of subsets connected by edges. (Equivalently we view the graph as a subgraph of a product in which one factor is sparse.) A random graph construction shows that such a factorization does not always exist.

**Sets of points with many halving lines**.

D. Eppstein.

Tech. Rep. 92-86, ICS, UCI, 1992.I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.

**The farthest point Delaunay triangulation minimizes angles**.

D. Eppstein.

Tech. Rep. 90-45, ICS, UCI, 1990.

*Comp. Geom. Theory & Applications*1: 143–148, 1992.Given a collection of points in convex position, the sharpest angle determined by any triple can be found as a corner of a triangle in the farthest point Delaunay triangulation.

**Parallel recognition of series parallel graphs**.

D. Eppstein.

*Information & Computation*98: 41–55, 1992.Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions.

**Improved bounds for intersecting triangles and halving planes**.

D. Eppstein.

Tech. Rep. 91-60, ICS, UCI, 1991.

*J. Combinatorial Theory Ser. A*62: 176–182, 1993.Reduces the polylogarithmic term in an upper bound for the three-dimensional

*k*-set problem.A bug in the proof was corrected by Nivasch and Sharir.

**Connectivity, graph minors, and subgraph multiplicity**.

D. Eppstein.

Tech. Rep. 92-06, ICS, UCI, 1992.

*J. Graph Th.*17: 409–416, 1993.It was known that planar graphs have O(

*n*) subgraphs isomorphic to K_{3}or K_{4}. That is, K_{3}and K_{4}have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.More generally, let F be a minor-closed family, and let x be the smallest number such that some complete bipartite graph K

_{x,y}is a forbidden minor for F. Then the x-connected graphs have linear subgraph multiplicity for F, and there exists an (x − 1)-connected graph (namely K_{x − 1,x − 1}) that does not have linear subgraph multiplicity. When x ≤ 3 or when x = 4 and the minimal forbidden minors for F are triangle-free, then the graphs with linear subgraph multiplicity for F are exactly the x-connected graphs.Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.

**Approximating the minimum weight Steiner triangulation**.

D. Eppstein.

Tech. Rep. 91-55, ICS, UCI, 1991.

*3rd ACM-SIAM Symp. Discrete Algorithms,*Orlando, 1992, pp. 48–57.

*Disc. Comp. Geom.*11: 163–191, 1994.Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.

**On the number of minimal 1-Steiner trees**.

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

*Disc. & Comp. Geom.*12: 29–34, 1994.Given a

*d*-dimensional set of*n*points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of*n*^{d}.**Arboricity and bipartite subgraph listing algorithms**.

D. Eppstein.

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

*Inf. Proc. Lett.*51: 207–211, 1994.For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are O(n) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also O(n).

Nowadays these results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given O(1) attributes and each newly-added attribute is held by O(1) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.

**Worst-case bounds for subadditive geometric graphs**.

M. Bern and D. Eppstein.

*9th ACM Symp. Comp. Geom.,*San Diego, 1993, pp. 183–188.For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt

*n*) and the sum of*d*th powers of edge lengths is O(log*n*). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(*n*). For traveling salesmen the O(log*n*) bound is tight but for some other graphs the sum of*d*th powers of edge lengths is O(1).**Dihedral bounds for mesh generation in high dimensions**.

M. Bern, L.P. Chew, D. Eppstein, and J. Ruppert.

*892nd Meeting Amer. Math. Soc.,*Brooklyn, 1994.

Abstract in*Abs. Amer. Math. Soc.*15, 1994, p. 366.

*6th ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1995, pp. 189–196.Any

*d*-dimensional point set can be triangulated with O(*n*^{ceil(d/2)}) simplices, none of which has an obtuse dihedral angle. No bound depending only on*n*is possible if we require the maximum dihedral angle to measure at most 90-epsilon degrees or the minimum dihedral to measure at least epsilon. Includes a classification of simplices in terms of their bad angles.**Geometric lower bounds for parametric matroid optimization**.

D. Eppstein.

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

*27th ACM Symp. Theory of Computing,*Las Vegas, 1995, pp. 662–671.

*Disc. Comp. Geom.*20: 463–476, 1998.Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric

*k*-set problem.**The centroid of points with approximate weights**.

M. Bern, D. Eppstein, L. J. Guibas, J. Hershberger, S. Suri, and J. Wolter.

*3rd Eur. Symp. Algorithms,*Corfu, 1995.

Springer,*Lecture Notes in Comp. Sci.*979, 1995, pp. 460–472.Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.

(BibTeX – Citations – CiteSeer – ACM DL)

**The diameter of nearest neighbor graphs**.

D. Eppstein.

Tech. Rep. 92-76, ICS, UCI, 1992.Any connected nearest neighbor forest with diameter

*D*has O(*D*^{6}) vertices. This was later further improved to O(*D*^{5}) and merged with results of Paterson and Yao into "On nearest neighbor graphs".**Representing all minimum spanning trees with applications to counting and generation**.

D. Eppstein.

Tech. Rep. 95-50, ICS, UCI, 1995.Shows how to find for any edge weighted graph G an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

**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.

**On nearest-neighbor graphs**.

D. Eppstein, M. S. Paterson, and F. F. Yao.

*Disc. Comp. Geom.*17: 263–282, 1997.Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter

*D*has O(*D*^{9}) vertices. This paper is the journal version; my contribution consists of improving that bound to O(*D*^{5}), which is tight.**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.**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.

**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.**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.

**Regression depth and center points**.

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

arXiv:cs.CG/9809037.

*3rd CGC Worksh. Computational Geometry*, Brown Univ., 1998.

*Disc. Comp. Geom.*23 (3): 305–323, 2000.We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.

**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.

**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.

**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.

**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".**Small maximal independent sets and faster exact graph coloring**.

D. Eppstein.

arXiv:cs.DS/0011009.

*7th Worksh. Algorithms and Data Structures,*Providence, Rhode Island, 2001.

Springer,*Lecture Notes in Comp. Sci.*2125, 2001, pp. 462–470.

*J. Graph Algorithms and Applications*(special issue for WADS'01) 7 (2): 131–140, 2003.We show that any graph can be colored in time O(2.415

^{n}), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.**Hinged kite mirror dissection**.

D. Eppstein.

arXiv:cs.CG/0106032.We show that any polygon can be cut into kites, connected into a chain by hinges at their vertices, and that this hinged assemblage can be unfolded and refolded to form the mirror image of the polygon.

**Vertex-unfoldings of simplicial manifolds**.

E. Demaine, D. Eppstein, J. Erickson, G. Hart, and J. O'Rourke.

Tech. Reps. 071 and 072, Smith College, 2001.

arXiv:cs.CG/0107023 and cs.CG/0110054.

*18th ACM Symp. Comp. Geom.,*Barcelona, 2002, pp. 237–243.

*Discrete Geometry: In honor of W. Kuperberg's 60th birthday*, Pure and Appl. Math. 253, Marcel Dekker, pp. 215–228, 2003.We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex

**Topological issues in hexahedral meshing**.

D. Eppstein.

Invited talk at Conf. Algebraic Topology Methods in Computer Science, Stanford, 2001.We consider the problem of subdividing a polyhedral domain in R^3 into cuboids meeting face-to-face. For topological subdivisions (cell complexes in which each cell is combinatorially equivalent to a cube, but may not be embedded as a polyhedron) and simply-connected domains, a simple necessary and sufficient condition for the existence of a hexahedral mesh is known: a domain with quadrilateral faces can be meshed if and only if there is an even number of faces. However, conditions for the existence of polyhedral meshes remain open, as do the topological versions of the problem for more complicated domain topologies.

(Slides)

**Flipping cubical meshes**.

M. Bern D. Eppstein, and J. Erickson.

arXiv:cs.CG/0108020.

10th Int. Meshing Roundtable, Newport Beach, 2001, pp. 19–29.

*Engineering with Computers*18 (3): 173–187, 2002.We examine

*flips*in which a set of mesh cells connected in a similar pattern to a subset of faces of a cube or hypercube is replaced by cells in the pattern of the complementary subset. We show that certain flip types preserve geometric realizability of a mesh, and use this to study the question of whether every topologically meshable domain is geometrically meshable. We also study flip graph connectivity, and prove that the flip graph of quadrilateral meshes has exactly two connected components.Note that the Meshing Roundtable version was by Bern and Eppstein. Erickson was added as a co-author during the revisions for the journal version.

(Slides)

**Triangles and squares**.

D. Eppstein.

Invited talk at EuroConf. Combinatorics, Graph Theory, and Applications, Bellaterra, Spain, 2001, p. 114.Which unit-side-length convex polygons can be formed by packing together unit squares and unit equilateral triangles? For instance one can pack six triangles around a common vertex to form a regular hexagon. It turns out that there is a pretty set of 11 solutions. We describe connections from this puzzle to the combinatorics of 3- and 4-dimensional polyhedra, using illustrations from the works of M. C. Escher and others.

(Slides)

**Separating geometric thickness from book thickness**.

D. Eppstein.

arXiv:math.CO/0109195.We show that geometric thickness and book thickness are not asymptotically equivalent: for every

*t*, there exists a graph with geometric thickness two and book thickness__>__*t*.**Fat 4-polytopes and fatter 3-spheres**.

D. Eppstein, G. Kuperberg, and G. Ziegler.

arXiv:math.CO/0204007.

*Discrete Geometry: In honor of W. Kuperberg's 60th birthday*, Pure and Appl. Math. 253, Marcel Dekker, pp. 239–265, 2003.We introduce the fatness parameter of a 4-dimensional polytope P, (f

_{1}+f_{2})/(f_{0}+f_{3}). It is open whether all 4-polytopes have bounded fatness. We describe a hyperbolic geometry construction that produces 4-polytopes with fatness > 5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes and an improved lower bound on the average kissing number of finite sphere packings in R^{3}. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.**Separating thickness from geometric thickness**.

D. Eppstein.

arXiv:math.CO/0204252.

10th Int. Symp. Graph Drawing, Irvine, 2002.

Springer,*Lecture Notes in Comp. Sci.*2528, 2002, pp. 150–161.

In*Towards a Theory of Geometric Graphs*, AMS, 2004, Contemporary Math 342, J. Pach, ed., pp. 75–86.We show that thickness and geometric thickness are not asymptotically equivalent: for every

*t*, there exists a graph with thickness three and geometric thickness__>__*t*. The proof uses Ramsey-theoretic arguments similar to those in "Separating book thickness from thickness".**Uninscribable four-regular polyhedron**.

M. Dillencourt and D. Eppstein.

*Electronic Geometry Models*2003.08.001.We find an example of a three-dimensional polyhedron, with four edges per vertex, that can not be placed in convex position with all vertices on the surface of a sphere.

**The geometric thickness of low degree graphs.**

C. Duncan, D. Eppstein, and S. Kobourov.

arXiv:cs.CG/0312056.

*20th ACM Symp. Comp. Geom.,*Brooklyn, 2004, pp. 340–346.We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.

**The lattice dimension of a graph.**

D. Eppstein.

arXiv:cs.DS/0402028.

*Eur. J. Combinatorics*26 (6): 585–592, 2005.Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.

**Cubic partial cubes from simplicial arrangements.**

D. Eppstein.

arXiv:math.CO/0510263.

*Electronic J. Combinatorics*13(1), Paper R79, 2006.We show how to construct a cubic partial cube from any simplicial arrangement of lines or pseudolines in the projective plane. As a consequence, we find nine new infinite families of cubic partial cubes as well as many sporadic examples.

**Manhattan orbifolds.**

D. Eppstein.

arXiv:math.MG/0612109.

*Topology and its Applications*157 (2): 494–507, 2009.We investigate a class of metrics for 2-manifolds in which, except for a discrete set of singular points, the metric is locally isometric to an L

_{1}metric, and show that with certain additional conditions such metrics are injective. We use this construction to find the tight span of squaregraphs and related graphs, and we find an injective metric that approximates the distances in the hyperbolic plane analogously to the way the rectilinear metrics approximate the Euclidean distance.**Geometry of partial cubes**.

D. Eppstein.

Invited talk at 6th Slovenian International Conference on Graph Theory, Bled, Slovenia, 2007.I survey some of my recent results on geometry of partial cubes, including lattice dimension, graph drawing, cubic partial cubes, and partial cube flip graphs of triangulations.

(Slides)

**The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing**.

D. Eppstein.

arXiv:0709.4087.

*Proc. 16th Int. Symp. Graph Drawing*, Heraklion, Crete, 2008.

Springer,*Lecture Notes in Comp. Sci.*5417, 2009, pp. 78–89.

*J. Graph Algorithms and Applications*17 (1): 35–55, 2013.Defines a class of orthogonal graph drawings formed by a point set in three dimensions for which axis-parallel line contains zero or two vertices, with edges connecting pairs of points on each nonempty axis-parallel line. Shows that the existence of such a drawing can be defined topologically, in terms of certain two-dimensional surface embeddings of the same graph. Based on this equivalence, describes algorithms, graph-theoretic properties, and hardness results for graphs of this type.

(Slides from talk at U. Arizona, February 2008 – Slides from GD08) )

**Media Theory: Interdisciplinary Applied Mathematics**.

D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.

Springer, 2007, ISBN 978-3-540-71696-9.Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings. It incorporates material from several of my papers including "Algorithms for Media", "Algorithms for Drawing Media", "Upright-Quad Drawing of st-Planar Learning Spaces", and "The Lattice Dimension of a Graph".

(Publisher's web site – Reinhard Suck's review in J. Math. Psych. – Reinhard Suck's review in MathSciNet)

**Isometric diamond subgraphs**.

D. Eppstein.

arXiv:0807.2218.

*Proc. 16th Int. Symp. Graph Drawing*, Heraklion, Crete, 2008.

Springer,*Lecture Notes in Comp. Sci.*5417, 2009, pp. 384–389.

We describe polynomial time algorithms for determining whether an undirected graph may be embedded in a distance-preserving way into the hexagonal tiling of the plane, the diamond structure in three dimensions, or analogous structures in higher dimensions. The graphs that may be embedded in this way form an interesting subclass of the partial cubes.

(Slides)

**Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation**.

M. Dickerson, D. Eppstein, and K. Wortman.

arXiv:0812.0607.

*7th Int. Symp. Voronoi Diagrams in Science and Engineering (ISVD 2010)*, Quebec City, Canada, pp. 13–22.Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.

**The Fibonacci dimension of a graph**.

S. Cabello, D. Eppstein, and S. Klavžar.

IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.

arXiv:0903.2507.

*Electronic J. Combinatorics*18(1), Paper P55, 2011.We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.

**Combinatorics and geometry of finite and infinite squaregraphs**.

H.-J. Bandelt, V. Chepoi, and D. Eppstein.

arXiv:0905.4537.

*SIAM J. Discrete Math.*24 (4): 1399–1440, 2010.Characterizes squaregraphs as duals of triangle-free hyperbolic line arrangements, provides a forbidden subgraph characterization of them, describes an algorithm for finding minimum subsets of vertices that generate the whole graph by medians, and shows that they may be isometrically embedded into Cartesian products of five (but not, in general, fewer than five) trees.

**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)

**Ramified rectilinear polygons: coordinatization by dendrons**.

H.-J. Bandelt, V. Chepoi, and D. Eppstein.

arXiv:1005.1721.

*Disc. Comp. Geom.*54 (4): 771–797, 2015.

We characterize the graphs that can be isometrically embedded into the Cartesian product of two trees (partial double dendrons), and the metric spaces obtained as the median complexes of these graphs. These spaces include the space of geodesic distance in axis-parallel polygons in the L

_{1}plane, hence the title. An algorithm based on lexicographic breadth-first search can be used to recognize partial double dendrons in linear time.**Densities of minor-closed graph families**.

D. Eppstein.

arXiv:1009.5633.

*Electronic J. Combinatorics*17(1), Paper R136, 2010.For every minor-closed graph family (such as the family of planar graphs), there is a constant c such that the maximum number of edges in an n-vertex graph in the family is

*c*(*n*+*o*(*n*); for instance, for planar graphs,*c*= 3. We call*c*the limiting density of the family, and we study the set of all limiting densities of all minor-closed graph families. We show that this set of limiting densities is closed and well-ordered, with order type at least ω^{ω}, and we find an exact description of the members of this set up to its first two cluster points 1 and 3/2.**Bounds on the complexity of halfspace intersections when the bounded faces have small dimension**.

D. Eppstein and M. Löffler.

*Proc. 27th ACM Symp. on Computational Geometry*, Paris, 2011, pp. 361–368.

arXiv:1103.2575.

*Discrete Comput. Geom.*50 (1): 1–21, 2013.Suppose that

*P*is the intersection of*n*halfspaces in*D*dimensions, but that the bounded faces of*P*are at most*d*-dimensional, for some*d*that is much smaller than*D*. Then in this case we show that the number of vertices of*P*is*O*(*n*^{d}), independent of*D*. We also investigate related bounds on the number of bounded faces of all dimensions of*P*, and algorithms for efficiently listing the vertices and bounded faces of*P*.**On the density of maximal 1-planar graphs**.

F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, and J. Reislhuber.

*20th Int. Symp. Graph Drawing*, Redmond, Washington, 2012.

Springer,*Lecture Notes in Comp. Sci.*7704, 2013, pp. 327–338.

A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge, and maximal 1-planar if it is 1-planar but adding any edge would force more than one crossing on some edge or edges. Although maximal 1-planar graphs on

*n*vertices may have as many as 4*n*− 8 edges, we show that there exist maximal 1-planar graphs with as few as 45*n*/17 + O(1) edges.**The graphs of planar soap bubbles**.

D. Eppstein.

arXiv:1207.3761.

*Proc. 29th ACM Symp. on Computational Geometry*, Rio de Janeiro, 2013, pp. 27–36.We characterize the graphs of two-dimensional soap bubble clusters as being exactly the bridgeless 3-regular planar graphs. The proof uses the Möbius invariance of the properties characterizing these clusters together with our previous circle packing method for constructing Lombardi drawings of graphs.

For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".

(Slides)

**Antimatroids and balanced pairs**.

D. Eppstein.

arXiv:1302.5967.

*Order*31 (1): 81–99, 2014. Erratum (with V. Wiechert).We generalize the 1/3-2/3 conjecture, according to which every partial order should have a pair of items that are nearly equally likely to appear in either order in a random linear extension, to antimatroids, and we prove it for several specific types of antimatroid.

**Grid minors in damaged grids**.

D. Eppstein.

arXiv:1303.1136.

*Electronic J. Combinatorics*21(3), Paper P3.20, 2014.We give tight bounds on the size of the largest remaining grid minor in a grid graph from which a given number of vertices have been deleted, and study several related problems.

**Universal point sets for planar graph drawings with circular arcs**.

P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.

HAL-Inria open archive oai:hal.inria.fr:hal-00846953.

*25th Canadian Conference on Computational Geometry*, Waterloo, Canada, 2013.

*J. Graph Algorithms and Applications*18 (3): 313–324, 2014.For every positive integer

*n*, there exists a set of*n*points on a parabola, with the property that every*n*-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.(Slides)

**Superpatterns and universal point sets**.

M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein.

arXiv:1308.0403.

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

Springer,*Lecture Notes in Comp. Sci.*8242, 2013, pp. 208–219.

Bannister's talk on this paper won the GD2013 best presentation award.

*J. Graph Algorithms & Applications*18 (2): 177–209, 2014 (special issue for GD'13).A superpattern of a set of permutations is a permutation that contains as a pattern every permutation in the set. Previously superpatterns had been considered for all permutations of a given length; we generalize this to sets of permutations defined by forbidden patterns; we show that the 213-avoiding permutations have superpatterns half the length of the known bound for all permutations, and that any proper permutation subclass of the 213-avoiding permutations has near-linear superpatterns. We apply these results to the construction of universal point sets, sets of points that can be used as the vertices of drawings of all n-vertex planar graphs. We use our 213-avoiding superpatterns to construct universal sets of size approximately

*n*^{2}/4, and we also construct near-linear universal sets for graphs of bounded pathwidth.**Small superpatterns for dominance drawing**.

M. J. Bannister, W. E. Devanny, and D. Eppstein.

arXiv:1310.3770.

*Analytic Algorithmics and Combinatorics (ANALCO14)*, Portland, Oregon, 2014, pp. 92–103.We construct small universal point sets for dominance drawings of classes of acyclic graphs, by finding forbidden patterns in the permutations determined by these drawings and proving the existence of small superpatterns for the permutations with these patterns forbidden. In particular, dominance drawings of the Hasse diagrams of width-2 partial orders have universal point sets of size O(

*n*^{3/2}), derived from superpatterns of the same size for the 321-avoiding permutations, and dominance drawings of st-planar graphs have universal point sets of size O(*n*log*n*), derived from superpatterns for riffle shuffles.**Planar induced subgraphs of sparse graphs**.

G. Borradaile, D. Eppstein, and P. Zhu.

arXiv:1408.5939.

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

Springer,*Lecture Notes in Comp. Sci.*8871, 2014, pp. 1–12.

*J. Graph Algorithms & Applications*19 (1): 281–297, 2015.We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that

*m*/5.22 vertices are sufficient and*m*/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.**Structure of graphs with locally restricted crossings**.

V. Dujmović, D. Eppstein, and D. R. Wood.

arXiv:1506.04380.

*23rd Int. Symp. Graph Drawing*, Los Angeles, California, 2015.

Springer,*Lecture Notes in Comp. Sci.*9411 (2015), pp. 87–98.

*SIAM J. Discrete Math.*31 (2): 805–824, 2017.The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.

(Slides — local copy of final version)

**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.

**Triangle-free penny graphs: degeneracy, choosability, and edge count**.

D. Eppstein.

arXiv:1708.05152.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*10692 (2018), pp. 506–513.

*J. Graph Algorithms & Applications*22 (3): 483–499 (special issue for GD 2017), 2018.A penny graph is the contact graph of unit disks: each disk represents a vertex of the graph, no two disks can overlap, and each tangency between two disks represents an edge in the graph. We prove that, when this graph is triangle free, its degeneracy is at most two. As a consequence, triangle-free penny graphs have list chromatic number at most three. We also show that the number of edges in any such graph is at most 2

*n*− Ω(√*n*). The journal version uses the alternative title "Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs".(Slides)

**The effect of planarization on width**.

D. Eppstein.

arXiv:1708.05155.

*Proc. 25th Int. Symp. Graph Drawing*, Boston, Massachusetts, 2017.

Springer,*Lecture Notes in Comp. Sci.*10692 (2018), pp. 560–572.

*J. Graph Algorithms & Applications*22 (3): 461–481 (special issue for GD 2017), 2018.We study what happens to nonplanar graphs of low width (for various width measures) when they are made planar by replacing crossings by vertices. For treewidth, pathwidth, branchwidth, clique-width, and tree-depth, this replacement can blow up the width from constant to linear. However, for bandwidth, cutwidth, and carving width, graphs of bounded width stay bounded when we planarize them.

(Slides)

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

Semi-automatically filtered from a common source file.