Papers not presented at a conference
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.
(TeX source code – 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.
Sequence comparison with mixed convex and concave costs.
D. Eppstein.
Tech. Rep. CUCS-382-88, Computer Science Dept., Columbia University, 1988.
J. Algorithms 11 (1): 85–101, 1990.Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.
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 \(15n/2\). The complexity of cells cut by a convex \(k\)-gon is \(O(n\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
Planar orientations with low out-degree and compaction of adjacency matrices.
M. Chrobak and D. Eppstein.
Theor. Comp. Sci. 86 (2): 243–266, 1991.Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. One consequence is a parallel algorithm to list all subgraphs isomorphic to \(K_3\) or \(K_4\). More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods.
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.
Fast optimal parallel algorithms for maximal matching in sparse graphs.
H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.
Tech. Rep. 92-01, ICS, UCI, 1992.We later discovered that the same results were published in a SPAA paper by Greg Shannon.
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.
Finding minimum area \(k\)-gons.
D. Eppstein, M. Overmars, G. Rote, and G. Woeginger.
Disc. Comp. Geom. 7 (1): 45–58, 1992.Uses dynamic programming to choose sets of \(k\) points optimizing various criteria on the quality of their convex hull (in particular area). The time complexity (cubic in \(n\)) was later improved to quadratic in my paper "New algorithms for minimum area \(k\)-gons", which however continues to use the same dynamic program as a subroutine.
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. Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel 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 \(\mathcal{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 \(\mathcal{F}\). Then the \(x\)-connected graphs have linear subgraph multiplicity for \(\mathcal{F}\), and there exists an \((x-1)\)-connected graph (namely \(K_{x-1,x-1}\) that does not have linear subgraph multiplicity. When \(x\le 3\) or when \(x=4\) and the minimal forbidden minors for \(\mathcal{F}\) are triangle-free, then the graphs with linear subgraph multiplicity for \(\mathcal{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.
Persistence, offline algorithms, and space compaction.
D. Eppstein.
Tech. Rep. 91-54, ICS, UCI, 1991.Considers persistence for a naive form of dynamic algorithm in which each update rebuilds a static solution. The space bounds for this can often be reduced by maintaining an offline solution over a sequence of updates constructed from an Euler tour of the persistent update history tree.
New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams.
D. Eppstein and J. Erickson.
Tech. Rep. 92-55, ICS, UCI, 1992.Looks at space complexity of finding minimum simplices – solves the problem in O(n2) space and O(nd) time (matching the best known time bounds) or in linear space at the expense of an additional log in time. Also finds one-dimensional multiplicatively weighted Voronoi diagrams in linear time for sorted inputs (O(n log n) was known).
Tree-weighted neighbors and geometric k smallest spanning trees.
D. Eppstein.
Tech. Rep. 92-77, ICS, UCI, 1992.
Int. J. Comp. Geom. & Appl. 4: 229–238, 1994."Finding the k smallest spanning trees" used higher order Voronoi diagrams to reduce the geometric k smallest spanning tree problem to the graph problem. Here I instead use nearest neighbors for a modified distance function where the bottleneck shortest path length is subtracted from the true distance between points. The result improves the planar time bounds and extends more easily to higher dimensions.
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 nd.
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.
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.
Asymptotic speed-ups in constructive solid geometry.
D. Eppstein.
Tech. Rep. 92-87, ICS, UCI, 1992.
Algorithmica 13: 462–471, 1995.Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.
Mesh generation and optimal triangulation.
M. Bern and D. Eppstein.
Tech. Rep. CSL-92-1, Xerox PARC, 1992.
Computing in Euclidean Geometry, D.-Z. Du and F.K. Hwang, eds., World Scientific, 1992, pp. 23–90.
Revised version in Computing in Euclidean Geometry, 2nd ed., D.-Z. Du and F.K. Hwang, eds., World Scientific, 1995, pp. 47–123.Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures.
Improved sparsification.
D. Eppstein, Z. Galil, and G.F. Italiano.
Tech. Rep. 93-20, ICS, UCI, 1993.Saves a log factor over dynamic graph algorithms in "Sparsification" and their applications, by dividing vertices instead of edges. Merged into the journal version of "Sparsification".
Algorithms for proximity problems in higher dimensions.
M. T. Dickerson and D. Eppstein.
Comp. Geom. Theory & Applications 5: 277–291, 1996.Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.
Faster circle packing with application to nonobtuse triangulation.
D. Eppstein.
Tech. Rep. 94-33, ICS, UCI 1994.
Int. J. Comp. Geom. & Appl. 7 (5): 485–491, 1997.Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.
Approximation algorithms for geometric problems.
M. Bern and D. Eppstein.
Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed., PWS Publishing, 1996, pp. 296–345.Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.
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(D6) vertices. This was later further improved to O(D5) and merged with results of Paterson and Yao into "On nearest neighbor graphs".
Minimum range balanced cuts via dynamic subset sums.
D. Eppstein.
Tech. Rep. 95-10, ICS, UCI, 1995.
J. Algorithms 23: 375–385, 1997.Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.
Faster geometric k-point MST approximation.
D. Eppstein.
Tech. Rep. 95-13, ICS, UCI, 1995.
Comp. Geom. Theory & Applications 8: 231–240, 1997.Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.
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. The equivalent graph can be constructed in time O(m+n log n) given a single minimum spanning tree of G. As a consequence one can find fast algorithms for counting, listing, and randomly generating MSTs. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.
Finding common ancestors and disjoint paths in DAGs.
D. Eppstein.
Tech. Rep. 95-52, ICS, UCI, 1995.This paper describes algorithms for finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. The main results were merged into the journal version of "Finding the k shortest paths".
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.
Dynamic connectivity in digital images.
D. Eppstein.
Tech. Rep. 96-13, ICS, UCI, 1996.
Inf. Proc. Lett. 62: 121–126, 1997.Any algorithm that maintains the connected components of a bitmap image must take Omega(log n / log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.
On the parity of graph spanning tree numbers.
D. Eppstein.
Tech. Rep. 96-14, ICS, UCI, 1996.Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.
Beta-skeletons have unbounded dilation.
D. Eppstein.
Tech. Rep. 96-15, ICS, UCI, 1996.
arXiv:cs.CG/9907031.
Comp. Geom. Theory & Applications 23: 43–52, 2002.Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(nc), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.
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.
Application Challenges to Computational Geometry.
The Computational Geometry Impact Task Force Report.
Tech. Rep. TR-521-96, Princeton University, April 1996.
Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407–423.
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.
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.
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.
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.
Phutball endgames are hard.
E. Demaine, M. Demaine, and D. Eppstein.
arXiv:cs.CC/0008025.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.
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.
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, (f1+f2)/(f0+f3). 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 R3. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.
Tiling space and slabs with acute tetrahedra.
D. Eppstein, J. M. Sullivan, and A. Üngör.
arXiv:cs.CG/0302027.
Comp. Geom. Theory & Applications 27 (3): 237–255, 2004.We show it is possible to triangulate three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08 degrees, and another which tiles a slab in space.
Guest editor's forward.
D. Eppstein.
Disc. Comp. Geom. 30: 1–2, 2003 (special issue for 17th Symp. Comp. Geom.)
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 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.
Nonrepetitive paths and cycles in graphs with application to Sudoku.
D. Eppstein.
arXiv:cs.DS/0507053.We describe algorithms and hardness results for finding paths in edge-labeled graphs such that no two consecutive edges have the same label, and use our algorithms to implement heuristics for a program that automatically solves and generates Sudoku puzzles.
Drawings of planar graphs with few slopes and segments.
V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.
arXiv:math.CO/0606450.
Comp. Geom. Theory & Applications 38: 194–212, 2007.We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).
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.
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 L1 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.
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.
Learning sequences.
D. Eppstein.
arXiv:0803.4030.How to implement an antimatroid, with applications in computerized education.
Principles of Graph Drawing.
D. Eppstein.
Talk at Inst. for Mathematical Behavioral Sciences, May 2008.
Talk at Technical University of Eindhoven, September 2008.
Finding large clique minors is hard.
D. Eppstein.
arXiv:0807.0007.
J. Graph Algorithms and Applications 13 (2): 197–204, 2009.Proves that it's NP-complete to compute the Hadwiger number of a graph.
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.
Optimal angular resolution for face-symmetric drawings.
D. Eppstein and K. Wortman.
arXiv:0907.5474.
J. Graph Algorithms and Applications 15 (4): 551–564, 2011.We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.
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 L1 plane.
Growth and decay in life-like cellular automata.
D. Eppstein.
arXiv:0911.2890.
Game of Life Cellular Automata (Andrew Adamatzky, ed.), Springer, 2010, pp. 71–98.We classify semi-totalistic cellular automaton rules according to whether patterns can escape any finite bounding box and whether patterns can die out completely, with the aim of finding rules with interesting behavior similar to Conway's Game of Life. We survey a number of such rules.
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 L1 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.
Guest editor's foreword.
D. Eppstein and E. Gansner.
Journal of Graph Algorithms and Applications 15 (2): 3–5, 2011.
(Special Issue on Selected Papers from the Seventeenth International Symposium on Graph Drawing, GD 2009)
Inapproximability of orthogonal compaction.
M. J. Bannister, D. Eppstein, and J. Simons.
arXiv:1108.4705.
J. Graph Algorithms and Applications 16 (3): 651–673, 2012. (Special issue for GD 2011.)This is the journal version of "Hardness of approximate compaction for nonplanar orthogonal graph drawings". It has stronger inapproximability bounds, and more variations of the compaction problem that are hard to approximate. In addition it includes a retraction of a buggy approximation algorithm from the conference version.
Privacy-enhanced methods for comparing compressed DNA sequences.
D. Eppstein, M. T. Goodrich, and P. Baldi.
arXiv:1107.3593.
Area-universal and constrained rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
SIAM J. Computing 41 (3): 537–564, 2012.A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".
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.
Learning sequences: an efficient data structure for learning spaces.
D. Eppstein.
In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013, pp. 287–304.We show how to represent a learning space by a small family of learning sequences, orderings of the items in a learning sequence that are consistent with their prerequisite relations. This representation allows for the rapid generation of the family of all consistent knowledge states and the efficient assessment of the state of knowledge of a human learner.
Projection, decomposition, and adaption of learning spaces.
D. Eppstein.
In Knowledge Spaces: Applications in Education, J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013, pp. 305–322.In another chapter of the same book we used learning sequences to represent learning spaces and perform efficient knowledge assessment of a human learning. In this chapter we show how to use the same data structure to build learning spaces on a sample of the items of a larger learning space (an important subroutine in knowledge assessment) and to modify a learning space to more accurately model students.
Listing all maximal cliques in large sparse real-world graphs.
D. Eppstein, M. Löffler, and D. Strash.
J. Experimental Algorithmics 18 (3): 3.1, 2013 (special issue for SEA).This paper combines our theoretical results on clique-finding algorithms from ISAAC 2010 with our experimental results on the same algorithms from SEA 2011. We show how to list all maximal cliques in graphs of bounded degeneracy in time that is linear in the size of the graph and near-optimal in the degeneracy, and we show that low degeneracy explains the good behavior of the algorithm in our experiments on large real-world social networks.
ERGMs are hard.
M. J. Bannister, W. E. Devanny, and D. Eppstein.
arXiv:1412.1787.ERGMs (exponential random graph models) are used in social science to describe probability distributions on graphs that are supposed to mimic real-world social networks. However, we show that (with features that are standard in the social science application) the distributions given by these models can be computationally infeasible to sample from or to approximate the probability of seeing a given graph.
Simple recognition of Halin graphs and their generalizations.
D. Eppstein.
arXiv:1502.05334.
J. Graph Algorithms & Applications 20 (2): 323–346, 2016.We describe and implement a simple linear time algorithm for recognizing Halin graphs based on two simplifications of triples of degree-three vertices in such graphs. Removing some auxiliary data from the algorithm causes it to recognize a broader class of graphs that we call the D3-reducible graphs. We study the properties of these graphs, showing that they share many properties with the Halin graphs.
Metric dimension parameterized by max leaf number.
D. Eppstein.
arXiv:1506.01749.
J. Graph Algorithms & Applications 19 (1): 313–323, 2015.We prove that when a graph of bounded size has its edges subdivided to form a larger graph, it is still possible to find its metric dimension by a fixed-parameter tractable algorithm, parameterized by the pre-subdivision size of the graph.
Approximate greedy clustering and distance selection for graph metrics.
D. Eppstein, S. Har-Peled, and A. Sidiropoulos.
arXiv:1507.01555.
J. Computational Geometry 11 (1): 629–652, 2020.We provide fast approximation algorithms for the farthest-first traversal of graph metrics.
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.
Spanning trees in multipartite geometric graphs.
A. Biniaz, P. Bose, D. Eppstein, A. Maheshwari, P. Morin, and M. Smid.
arXiv:1611.01661.
Algorithmica 80 (11): 3177–3191, 2018.We provide near-linear-time algorithms for minimum and maximum spanning trees on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance.
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 10 (1): 207–222, 2019.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.
Which women mathematicians get written about on Wikipedia, and why.
D. Eppstein.
AWM Newsletter 48 (4): 12–14, July–August 2018.This short opinion piece explains Wikipedia's guidelines for inclusion of articles on academics, and outlines steps to help improve Wikipedia's coverage of women in mathematics.
Minor-closed graph classes with bounded layered pathwidth.
V. Dujmović, D. Eppstein, G. Joret, P. Morin, and D. R. Wood.
arXiv:1810.08314.
SIAM J. Discrete Math 34 (3): 1693–1709, 2020.A minor-closed graph family has a functional relation between diameter and path width (bounded local pathwidth) if and only if it excludes an apex-tree. The same graph families are also the ones with bounded layered pathwidth: a simultaneous path decomposition and layering (sequence of subsets of vertices with all edges connecting the same subset or consecutive subsets) so that the intersection of a bag and a layer has constant size.
Existence and hardness of conveyor belts.
M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
arXiv:1908.07668.
Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.
Face flips in origami tessellations.
H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
arXiv:1910.05667.
J. Computational Geometry 11 (1): 397–417, 2020.We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.
On polyhedral realization with isosceles triangles.
D. Eppstein.
arXiv:2009.00116.
Graphs and Combinatorics 37 (4): 1247–1269, 2021.We find convex polyhedra with all faces triangular that cannot be realized with all faces isosceles, and new families of convex polyhedra with congruent isosceles-triangle faces.
Stack-number is not bounded by queue-number.
V. Dujmović, D. Eppstein, R. Robert Hickingbotham, P. Morin, and D. R. Wood.
arXiv:2011.04195.
Combinatorica 42: 151–164, 2022.Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.
Egyptian fractions with denominators from sequences closed under doubling.
D. Eppstein.
J. Integer Sequences 24: 21.8.8, 2021.
arXiv:2109.12217.We prove that if a set of positive integers includes multiples of all integers, and is closed under multiplication by two, then its reciprocals can form Egyptian fractions for every rational number up to the sum of reciprocals of the set.
The complexity of iterated reversible computation.
D. Eppstein.
arXiv:2112.11607.
Invited talk at 15th Latin American Theoretical Informatics Symposium, Guanajuato, Mexico, November 2022.
TheoretiCS 2: A10:1–A10:41, 2023.We study a class of problems involving computing a value \(f^{(n)}(x)\), the \(n\)th iterate of a function \(f\), for polynomial time bijections. We prove that these problems are complete for \(\mathsf{P}^{\mathsf{PSPACE}}\), and include hard problems in circuit complexity, graph algorithms, the simulation of one- and two-dimensional automata, and dynamical systems. We also provide a polynomial time algorithm for the special case where the bijection is an interval exchange transformation.
Three-dimensional graph products with unbounded stack-number.
D. Eppstein, R. Robert Hickingbotham, L. Merker, S. Norin, M. T. Seweryn, and D. R. Wood.
arXiv:2202.05327.
Discrete Comput. Geom. 71: 1210–1237, 2024.The strong product of any three graphs of non-constant size has unbounded book thickness. In the case of strong products of three paths, and more generally of triangulations of \(n\times n\times n\) grid graphs obtained by adding a diagonal to each square of the grid, the book thickness is \(\Theta(n^{1/3})\). This is the first explicit example of a graph family with bounded maximum degree and unbounded book thickness.
Product structure extension of the Alon–Seymour–Thomas theorem.
M. Distel, V. Dujmović, D. Eppstein, R. Robert Hickingbotham, G. Joret, P. Micek, P. Morin, M. T. Seweryn, and D. R. Wood.
arXiv:2212.08739.
SIAM J. Discrete Math. 38 (3): 2095–2107, 2024.The graphs in any nontrivial minor-closed graph family can be represented as strong products of a graph of treewidth 4 with a clique of size \(O(\sqrt{n})\). For planar graphs and \(K_{3,t}\)-minor-free graphs, the treewidth can be reduced to 2.
Quasipolynomiality of the smallest missing induced subgraph.
D. Eppstein, A. Lincoln, and V. V. Williams.
arXiv:2306.11185.
J. Graph Algorithms & Applications 27 (5): 329–339, 2023.The smallest graph that is not an induced subgraph of a given graph can be found in time \(n^{O(\log n)}\). The exponent is optimal, up to constant factors, under the exponential time hypothesis.
What is ... treewidth?.
D. Eppstein.
Notices of the American Mathematical Society 72 (2): 172–175, 2025.We survey graph treewidth at a high level. The focus is on applications of treewidth to various areas of mathematics.
Fast Schulze voting using quickselect.
A. Arora, D. Eppstein, and R. L. Huynh.
arXiv:2411.18790.We show how to determine the outcome of a Schulze method election, from an input consisting of an \(m\times m\) array of pairwise margins of victory, in time \(O(m^2\log m)\). The algorithm uses random pivoting like that of quickselect.
Princ-wiki-a mathematica: Wikipedia editing and mathematics.
D. Eppstein, J. B. Lewis, R. Woodroofe, and X. Easter.
arXiv:2412.20419.
Notices of the AMS 72 (1): 65–73, 2025.We describe the experience of editing mathematics articles on Wikipedia, with the aim of providing helpful advice for new editors and encouraging mathematicians to become Wikipedia editors.
Hamiltonian cycles in subdivided doubles.
D. Eppstein.
arXiv:2510.18359.
Ars Mathematica Contemporanea, to appear.The subdivided double construction turns a 4-regular graph into a bigger 4-regular graph, by subdividing each edge and doubling each vertex. We prove that the resulting graphs, which include the Folkman graph, have the following curious property: every Hamiltonian cycle (of which there are exponentially many) is complementary to another Hamiltonian cycle.