**Trees in TeX**.

D. Eppstein.

*TUGboat*6 (1): 31, 1985.This note in the TeX user's group newsletter described a set of macros for drawing trees, using TeX's boxes-and-glue mechanisms to line up the nodes at each level of the tree.

(BibTeX – TeX source code – Citations – Nelson Beebe's TeX tree drawing bibliography)

**On the NP-completeness of cryptarithms**.

D. Eppstein.

*SIGACT News*18 (3): 38–40, 1987.A cryptarithm (also known as an alphametic) is a puzzle in which the digits of a mathematical formula (typically addition of two large numbers) are replaced by letters; the goal is to determine which letter stands for which digits. If arithmetic is done in a polynomially large radix, the problem becomes NP-complete.

(BibTeX – Full paper – Citations)

**Parallel algorithmic techniques for combinatorial computation**.

D. Eppstein and Z. Galil.

*Ann. Rev. Comput. Sci.*3: 233–283, 1988.

Invited talk by Z. Galil,*16th Int. Coll. Automata, Languages and Programming,*Stresa, Italy, 1989.

Springer,*Lecture Notes in Comp. Sci.*372, 1989, pp. 304–318.This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

(BibTeX – Citations – CiteSeer – ACM DL (ARCS) – ACM DL (ICALP))

**Ten algorithms for Egyptian fractions**.

D. Eppstein.

*Mathematica in Education and Research*4 (2): 5–15, 1995.Number theory. I survey and implement in

*Mathematica*several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a*k*shortest paths heuristic.(BibTeX – Citations – Also available in HTML and Mathematica notebook formats)

**A deterministic linear time algorithm for geometric separators and its applications**.

D. Eppstein, G.L. Miller, and S.-H. Teng.

*9th ACM Symp. Comp. Geom.,*San Diego, 1993, pp. 99–108.

*Fundamenta Informaticae*22: 309–330, 1995 (special issue on computational geometry).Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.

(BibTeX – Citations – CiteSeer)

**Computing the discrepancy with applications to supersampling patterns**.

D. P. Dobkin, D. Eppstein, and D. P. Mitchell.

*ACM Trans. on Graphics*15 (4): 354–376, 1996.Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.

(BibTeX – Citations – CiteSeer – ACM DL)

**Clustering for faster network simplex pivots**.

D. Eppstein.

Tech. Rep. 93-19, ICS, UCI, 1993.

*5th ACM-SIAM Symp. Discrete Algorithms,*Arlington, 1994, pp. 160–166.

*Networks*35 (3): 173–180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

**Zonohedra and Zonotopes**.

D. Eppstein.

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

*Mathematica in Education and Research*5 (4): 15–21, 1996.I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and

*Mathematica*notebook formats.(BibTeX – Citations – CiteSeer)

**The crust and the beta-skeleton: combinatorial curve reconstruction**.

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

*Graphical Models & Image Processing*60/2 (2): 125–135, 1998.We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.

(BibTeX – Citations – CiteSeer – ACM DL)

**Fast hierarchical clustering and other applications of dynamic closest pairs**.

D. Eppstein.

*9th ACM-SIAM Symp. Discrete Algorithms,*San Francisco, 1998, pp. 619–628.

arXiv:cs.DS/9912014.

*J. Experimental Algorithmics*5 (1): 1–23, 2000.This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.

(Source code and experimental data – BibTeX – SODA paper – Citations – CiteSeer – ACM DL – JEA home page)

**The distribution of cycle lengths in graphical models for iterative decoding**.

X. Ge, D. Eppstein, and P. Smyth.

arXiv:cs.DM/9907002.

Tech. Rep. 99-10, ICS, UCI, 1999.

IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000.

*IEEE Trans. Information Theory*47 (6): 2549–2553, 2001.We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.

(BibTeX – Citations: TR/ISIT – 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)

**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 – BibTeX – Citations – CiteSeer)

**The minimum expectation selection problem**.

D. Eppstein and G. Lueker.

10th Int. Conf. Random Structures and Algorithms, Poznan, Poland, August 2001.

arXiv:cs.DS/0110011.

*Random Structures and Algorithms*21: 278–292, 2002.We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.

**Algorithms for media**.

D. Eppstein and J.-C. Falmagne.

arXiv:cs.DS/0206033.

Int. Conf. Ordinal and Symbolic Data Analysis, Irvine, 2003.

*Discrete Applied Mathematics*156 (8): 1308–1320, 2008.Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.

(BibTeX – Citations – OSDA talk slides)

**Reference caching using unit distance redundant codes for activity reduction on address buses**.

D. Eppstein and T. Givargis.

Worksh. Embedded System Codesign (ESCODES'02), San Jose, 2002, pp. 43–48.

*J. Microprocessors & Microsystems*29 (4): 145–153, 2005.We study the problem of minimizing transitions in address signals on a bus. The UDRC part of the title refers to an algorithm for coding signals with at most one transition per signal (using an increased number of wires); we combine this with a scheme for caching previously coded addresses and use trace data to compare our technique with previous approaches.

(BibTeX – Citations – CiteSeer)

**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 effect of faults on network expansion.**

A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.

arXiv:cs.DC/0404029.

*16th ACM Symp. Parallelism in Algorithms and Architectures*, Barcelona, 2004, pp. 286–293.

*Theory of Computing Systems*39 (6): 903–928, 2006.Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.

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

**Comment on "Location-Scale Depth".**

D. Eppstein.

*J. Amer. Stat. Assoc.*99 (468): 976–979, 2004.Discusses a paper by Mizera and Müller on depth-based methods for simultaneously fitting both a center and a radius to a set of sample points, by viewing the points as lying on the boundary of a model of a higher dimensional hyperbolic space. Reformulates their method in combinatorial terms more likely to be familiar to computational geometers, and discusses the algorithmic implications of their work.

**Cubic partial cubes from simplicial arrangements.**

D. Eppstein.

arXiv:math.CO/0510263.

*Electronic J. Combinatorics*13(1) #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.

**Approximate weighted farthest neighbors and minimum dilation stars.**

J. Augustine, D. Eppstein, and K. Wortman.

arXiv:cs.CG/0602029.

*Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010)*, Nha Trang, Vietnam.

Springer,*Lecture Notes in Comp. Sci.*6196, 2010, pp. 90–99.

*Discrete Mathematics, Algorithms and Applications*2 (4): 553–565, 2010.The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.

**Interconnect criticality driven delay relaxation.**

L. Singhal, E. Bozorgzadeh, and D. Eppstein.

*IEEE Trans. CAD*26 (10): 1803–1817, 2007.We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.

**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.**Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.**

D. Eppstein, and M. T. Goodrich.

*10th Worksh. Algorithms and Data Structures,*Halifax, Nova Scotia, 2007.

Springer,*Lecture Notes in Comp. Sci.*4619, 2007, pp. 637–648.

arXiv:0704.3313.

*IEEE Trans. Knowledge and Data Engineering*23 (2): 297–306, 2011.We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.

**On verifying and engineering the well-gradedness of a union-closed family**.

D. Eppstein, J.-C. Falmagne, and H. Uzun.

arXiv:0704.2919.

38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.

*J. Mathematical Psychology*53 (1): 34–39, 2009.We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.

**Approximate Topological Matching of Quadrilateral Meshes**.

D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.

*Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008)*, Stony Brook, New York, pp. 83–92.

*The Visual Computer*25 (8): 771–783, 2009.We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.

(Preprint)

**Motorcycle graphs: canonical quad mesh partitioning**.

D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.

*Proc. 6th Symp. Geometry Processing*, Copenhagen, Denmark, 2008.

*Computer Graphics Forum*27 (5): 1477–1486, 2008.We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.

**Succinct greedy geometric routing using hyperbolic geometry**.

D. Eppstein and M. T. Goodrich.

arXiv:0806.0341.

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

(under the different title "Succinct greedy graph drawing in the hyperbolic plane"),

Springer,*Lecture Notes in Comp. Sci.*5417, 2009, pp. 14–25.

*IEEE Transactions on Computing*60 (11): 1571–1580, 2011.Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.

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

**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.**On 2-site Voronoi diagrams under geometric distance functions**.

G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.

*27th Eur. Worksh. Comp. Geom.*, Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.

*Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering*, Qing Dao, China, 2011, pp. 31–38.

arXiv:1105.4130.

*J. Computer Science and Technology*28 (2): 267–277, 2013.We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.

**Diamond-kite meshes: adaptive quadrilateral meshing and orthogonal circle packing**.

D. Eppstein.

arXiv:1207.5082.

*21st International Meshing Round Table*, San Jose, California, 2012, pp. 261–277.

*Engineering with Computers*30 (2): 223–235 (special issue for the 21st Int. Meshing Roundtable), 2014.We describe a recursive subdivision of the plane into quadrilaterals in the form of rhombi and kites with 60, 90, and 120 degree angles. The vertices of the resulting quadrilateral mesh form the centers of a set of circles that cross orthogonally for every two adjacent vertices, and it has many other properties that are important in finite element meshing.

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

**Listing all maximal cliques in large sparse real-world graphs in near-optimal time**.

D. Eppstein, M. Löffler, and D. Strash.

*J. Experimental Algorithmics*18 (3): 3.1, 2013.This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011.

**Automated generation of linkage loop equations for planar 1-dof linkages, demonstrated up to 8-bar**.

B. E. Parrish, J. M. McCarthy, and D. Eppstein.

*Proc. ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference*, Vol. 5A:*38th Mechanisms and Robotics Conference*, Buffalo, New York, USA, August 17-20, 2014, paper no. DETC2014-35263.

*J. Mechanisms and Robotics*7 (1): 011006, 2015.This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.

(eScholarship conference version – eScholarship journal version)

**Folding a paper strip to minimize thickness**.

E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.

arXiv:1411.6371.

*9th International Workshop on Algorithms and Computation (WALCOM 2015)*, Dhaka, Bangladesh.

Springer,*Lecture Notes in Comp. Sci.*8973 (2015), pp. 113–124.

*Journal of Discrete Algorithms*36: 18–26, 2016.

If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.

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

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

Semi-automatically filtered from a common source file.