Other conferences and workshops
A heuristic approach to program inversion.
D. Eppstein.
9th Int. Joint Conf. Artificial Intelligence, Los Angeles, 1985, pp. 219–221.Program transformation. Given a (lisp) program for an invertible function, how do we automatically find a program for the inverse function? Considers more general simultaneous inverses of multiple functions. The heuristic part involves type inference for finding conditionals to use in certain if statements.
Speeding up dynamic programming.
D. Eppstein, Z. Galil, and R. Giancarlo.
29th IEEE Symp. Foundations of Comp. Sci., White Plains, New York, 1988, pp. 488–496.
Worksh. Algorithms for Molecular Genetics, Bethesda, Maryland, 1988.
Tech. Rep. CUCS-379-88, Computer Science Dept., Columbia University, 1988.
Appeared as "Efficient algorithms with applications to molecular biology" in Int. Advanced Workshop on Sequences, Positano, Italy, 1988.
Sequences: Combinatorics, Compression, Security, Transmission, R. M. Capocelli, ed., Springer, 1990, pp. 59–74.The FOCS and Positano versions of this paper merged my results on a dynamic program used for RNA secondary structure prediction, with Raffaele's on sequence comparison. The Bethesda talk and the TR version both used the longer title "Speeding up dynamic programming with application to the computation of RNA structure", and included only the RNA result, which used a mild convexity assumption on certain costs to save two orders of magnitude in total time. This work incited a boom in computational biology within the theory community that is still going strong. But the RNA results were quickly improved by a log factor [Aggarwal et al. at the same FOCS] and never made it into a journal paper.
Simultaneous strong separations of probabilistic and unambiguous complexity classes.
D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65–70.
Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
Mathematical Systems Theory 25 (1): 23–36, 1992.Structural complexity theory. Constructs oracles in which \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{UP}\) (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".
Efficient algorithms for sequence analysis.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
International Advanced Workshop on Sequences, Positano, Italy, 1991.
Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer, 1993, pp. 225–244.Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
Edge insertion for optimal triangulations.
M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T.S. Tan.
1st Latin Amer. Symp. Theoretical Informatics, Sao Paulo, 1992.
Springer, Lecture Notes in Comp. Sci. 583, 1992, pp. 46–60.
Tech. Rep. EDC UILU-ENG-92-1702, Univ. Illinois, Urbana-Champaign, 1992.
Disc. & Comp. Geom. 10: 47–65, 1993.One standard way of constructing Delaunay triangulations is by iterated local improvement, in which each step flips the diagonal of some quadrilateral. For many other optimal triangulation problems, flipping is insufficient, but the problems can instead be solved by a more general local improvement step in which a new edge is added to the triangulation, cutting through several triangles, and the region it cuts through is retriangulated on both sides.
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(nceil(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.
Computational geometry and parametric matroid optimization.
D. Eppstein.
Invited talk, 5th Int. Symp. Parametric Optimization, Chiba, Japan, 1997.This talk surveys some connections from computational geometry to parametric matroids: the results of my paper "Geometric lower bounds", new upper bounds from a paper by Tamal Dey, and a problem from constructive solid geometry with the potential to lead to stronger lower bounds.
A disk-packing algorithm for an origami magic trick.
M. Bern, E. Demaine, D. Eppstein, and B. Hayes.
Int. Conf. Fun with Algorithms, Elba, June 1998.
Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.
Origami3: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001), A K Peters, 2002, pp. 17–28.We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
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.
Emerging challenges in computational topology.
M. Bern, D. Eppstein, et al.
arXiv:cs.CG/9909001.This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.
Searching for spaceships.
D. Eppstein.
arXiv:cs.AI/0004003.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 433–453.We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.
Graphs for dynamic geometry.
D. Eppstein.
Invited talk, Worksh. Dynamic Graph Algorithms, Victoria, Canada, 2000.This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.
One-dimensional peg solitaire, and duotaire.
C. Moore and D. Eppstein.
arXiv:math.CO/0006067 and math.CO/0008172.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
Santa Fe Inst. working paper 00-09-050, September 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 341–350.We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.
(Cris' MSRI talk on streaming video – Cris' publications page)
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.
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.
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.
A steady state model for graph power laws.
D. Eppstein and J. Wang.
2nd Int. Worksh. Web Dynamics, Honolulu, 2002.
arXiv:cs.DM/0204001.We propose a random graph model that (empirically) appears to have a power law degree distribution. Unlike previous models, our model is based on a Markov process rather than incremental growth. We compare our model with others in its ability to predict web graph clustering behavior.
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.
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.
Möbius transformations in scientific computing.
D. Eppstein.
Talk at SIAM Conf. on Computational Science and Engineering, San Diego, 2003.This talk, for the CSE session on combinatorial scientific computing, surveys my work with Marshall Bern on optimal Möbius transformation and Möbius-invariant natural neighbor transformation.
Depth and arrangements.
D. Eppstein.
Invited talk at DIMACS Worksh. on Data Depth, New Brunswick, NJ, 2003.
Invited talk at MSRI Introductory Worksh. Discrete & Computational Geometry, Berkeley, CA, 2003.Surveys projective duality and its uses in algorithms for robust regression. The MSRI talk used the alternative title "Computational geometry and robust statistics" but contained essentially the same content.
Quasiconvex programming.
D. Eppstein.
Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
Plenary talk at ALGO 2004, Bergen, Norway, 2004.
arXiv:cs.CG/0412046.
Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287–331.Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.
Hyperbolic geometry, Möbius transformations, and geometric optimization.
D. Eppstein.
Invited talk at MSRI Introductory Worksh. Discrete & Computational Geometry, Berkeley, CA, 2003.Describes extensions of computational geometry algorithms to hyperbolic geometry, including an output-sensitive 3d Delaunay triangulation algorithm of Boissonat et al. and my own research on optimal Möbius transformation.
Single-strip triangulation of manifolds with arbitrary topology.
D. Eppstein and M. Gopi.
13th Video Review of Computational Geometry, 2004.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 455–456 (abstract for video).
25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04), Grenoble, 2004 (2nd best paper award).
Eurographics Forum 23 (3): 371–379, 2004.
arXiv:cs.CG/0405036.We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.
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.
Skip-webs: efficient distributed data structures for multi-dimensional data sets.
L. Arge, D. Eppstein, and M. T. Goodrich.
Proc. 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing (PODC 2005), Las Vegas, July 2005, pp. 69–76.
arXiv:cs.DC/0507050.Describes efficient distributed versions of skip quadtrees and related spatial searching structures.
Single triangle strip and loop on manifolds with boundaries.
A. Bushan, P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
Tech. Rep. 05-11, UC Irvine, School of Information and Computer Science, 2005.
Proc. 19th Brazilian Symp. Computer Graphics and Image Processing (SIBGRAPI 2006), pp. 221–228.This follows on to our previous paper on using graph matching to cover a triangulated polyhedral model with a single triangle strip by extending the algorithms to models with boundaries. We provide two methods: one is based on using an algorithm for the Chinese Postman problem to find a small set of triangles to split in order to find a perfect matching in the dual mesh, while the other augments the model with virtual triangles to remove the boundaries and merges the strips formed by our previous algorithm on this augmented model. We implement the algorithms and report some preliminary experimental results.
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.
Edges and switches, tunnels and bridges.
D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 77–88.
Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
arXiv:0705.0413.
Comp. Geom. Theory & Applications 42 (8): 790–802, 2009 (special issue for EWCG'07).We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.
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.
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.
Studying (non-planar) road networks through an algorithmic lens.
D. Eppstein, and M. T. Goodrich.
arXiv:0808.3694.
Proc. 16th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2008), Article 16 (best paper award).
Invited talk at INFORMS 2009, San Diego.We examine US road network data and show that, contrary to the assumptions of much past GIS work, these networks are highly nonplanar. We introduce a class of "multiscale dispersed" networks that better fit the data; these networks are defined by a family of disks of varying sizes such that, if a small number of outliers is removed, the remaining disks cover each point of the plane a constant number of times. As we show, these networks have good graph separators, allowing for efficient algorithms for minimum spanning trees, graph Voronoi diagrams, and related problems.
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.
Area-universal rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
arXiv:0901.3924.
25th Eur. Worksh. Comp. Geom., Brussels, Belgium, 2009.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, pp. 267–276.A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
Graph-theoretic solutions to computational geometry problems.
D. Eppstein.
Invited talk, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.
Springer, Lecture Notes in Comp. Sci. 5911, 2009, pp. 1–16.
arXiv:0908.3916.We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.
Curvature-aware fundamental cycles.
P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
17th Pacific Conf. Computer Graphics and Applications, Jeju, Korea, 2009.
Computer Graphics Forum 28 (7): 2015–2024, 2009.Considers heuristic modifications to the tree-cotree decomposition of my earlier paper Dynamic generators of topologically embedded graphs, to make the set of fundamental cycles found as part of the decomposition follow the contours of a given geometric model.
Going off-road: transversal complexity in road networks.
D. Eppstein, M. T. Goodrich, and L. Trott.
arXiv:0909.2891.
Proc. 17th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Seattle, 2009, pp. 23–32.Shows both theoretically and experimentally that the number of times a random line crosses a road network is asymptotically upper bounded by the square root of the number of road segments.
Hyperconvexity and metric embedding.
D. Eppstein.
Invited talk, Fifth William Rowan Hamilton Geometry and Topology Workshop, Dublin, Ireland, 2009.
Invited talk at IPAM Workshop on Combinatorial Geometry, UCLA, 2009.Surveys hyperconvex metric spaces, tight spans, and my work on Manhattan orbifolds, tight span construction, and optimal embedding into star metrics.
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".
Flows in one-crossing-minor-free graphs.
E. Chambers and D. Eppstein.
arXiv:1007.1484.
Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 241–252.
J. Graph Algorithms and Applications 17 (3): 201–220, 2013.We show that the maximum flow problem can be solved in near-linear time for K5-minor-free and K3,3-minor-free graphs. The same result also holds for H-minor-free graphs when H can be embedded in the plane with one crossing and a structural decomposition of the input flow graph is given.
Listing all maximal cliques in sparse graphs in near-optimal time.
D. Eppstein, M. Löffler, and D. Strash.
arXiv:1006.5440.
Workshop on Exact Algorithms for NP-Hard Problems, Dagstuhl, Germany, 2010.
Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
Springer, Lecture Notes in Comp. Sci. 6506, 2010, pp. 403–414.We describe an algorithm for finding all maximal cliques in a graph, in time O(dn3d/3) where n is the number of vertices and d is the degeneracy of the graph, a standard measure of its sparsity. This time bound matches the worst-case output size for these parameters. The algorithm modifies the Bron-Kerbosch algorithm for maximal cliques by ordering the vertices by degree in the outer recursive call of the algorithm.
For the journal version, see "Listing all maximal cliques in large sparse real-world graphs," which combines results from this and a different conference paper.
Extended dynamic subgraph statistics using h-index parameterized data structures.
D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
arXiv:1009.0783.
Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.
Privacy-preserving data-oblivious geometric algorithms for geographic data.
D. Eppstein, M. T. Goodrich, and R. Tamassia.
Proc. 18th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2010), San Jose, California, pp. 13–22.
arXiv:1009.1904.An algorithm is data-oblivious if the memory access patterns it makes depend only on the input size and not on the actual input values; data-oblivious algorithms are an important building block of cryptographic protocols that allow algorithmic tasks to be solved by parties who each have some subset of the input data that they do not wish to reveal. We show how to solve several basic geometric problems data-obliviously, including construction of convex hulls, quadtrees, and well-separated pair decompositions, and computation of closest pairs and all nearest neighbors.
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.
Listing all maximal cliques in large sparse real-world graphs.
D. Eppstein and D. Strash.
10th Int. Symp. Experimental Algorithms, Crete, 2011.
Springer, Lecture Notes in Comp. Sci. 6630, 2011, pp. 364–375.
arXiv:1103.0318.We experiment with our degeneracy-based algorithm for listing maximal cliques in sparse graphs and show that it works well on large graphs drawn from several repositories of real-world social networks and bioinformatics networks.
For the journal version, see "Listing all maximal cliques in large sparse real-world graphs", which combines results from this and a different conference paper.
What's the difference? Efficient set reconciliation without prior context.
D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
Proc. ACM SIGCOMM, Toronto, Canada, 2011.We determine the symmetric difference between two similar sets of items, held by different machines on the internet, using an amount of communication bandwidth that is proportional only to the difference between the sets and with low computational overhead. Our solution technique combines the invertible Bloom filter data structure from our previous work on streaming straggler detection with a randomized sampling scheme that allows us to accurately and efficiently estimate the size of the difference.
Category-based routing in social networks: membership dimension and the small-world phenomenon.
D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott.
Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
arXiv:1108.4675.
Theor. Comput. Sci. 514: 96–104, 2013. (Special issue on Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello)We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.
Randomized speedup of the Bellman–Ford algorithm.
M. J. Bannister and D. Eppstein.
arXiv:1111.5414.
Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan, 2012, pp. 41–47.The Bellman–Ford algorithm for single-source shortest paths in graphs that may have negatively weighted edges but no negative cycles can be sped up by a technique of Yen in which the graph is partitioned into two directed acyclic subgraphs and edge relaxations alternate between these two subgraphs. We show that choosing this partition randomly gains an additional factor of 2/3 in running time.
Improved grid map layout by point set matching.
D. Eppstein, M. van Kreveld, B. Speckmann, and F. Staals.
28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, 2012.
6th IEEE Pacific Visualization Conf. (PacificVis), Sydney, Australia, 2013.
Int. J. Comput. Geom. Appl. 25 (2): 101–122, 2015.We study the problem of matching geographic regions to points in a regular grid, minimizing the distance between each region's centroid and the corresponding grid point, and preserving as much as possible the relative orientations between pairs of regions.
Solving single-digit Sudoku subproblems.
D. Eppstein.
arXiv:1202.5074.
6th International Conference on Fun with Algorithms (FUN 2012), Venice, Italy, 2012.
Springer, Lecture Notes in Comp. Sci. 7288, 2012, pp. 142–153.We find an algorithm for making all possible deductions based on the set of candidate locations for a single digit in a Sudoku puzzle; the problem is NP-hard, and our algorithm takes exponential time, but the mild form of the exponential allows it to be fast for practical problem sizes.
UOBPRM: a uniform distributed obstacle-based PRM.
H.-Y. Yeh, S. Thomas, D. Eppstein, and N. Amato.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012), Vilamoura, Algarve, Portugal, 2012, pp. 2655–2662.We use a method based on intersecting obstacles with line segments in order to uniformly sample from obstacle surfaces in the probabilistic roadmap method for robot motion planning.
A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing.
D. Eppstein.
Invited talk at EuroGIGA Midterm Conference, Prague, Czech Republic, 2012.
Discrete Comput. Geom. 52 (3): 515–550, 2014 (Special issue for SoCG 2013).This talk and journal paper combines the results from "Planar Lombardi drawings for subcubic graphs" and "The graphs of planar soap bubbles". It uses three-dimensional hyperbolic geometry to define a partition of the plane into cells with circular-arc boundaries, given an input consisting of (possibly overlapping) circular disks and disk complements, which remains invariant under Möbius transformations of the input. We use this construction as a tool to construct planar Lombardi drawings of all 3-regular planar graphs; these are graph drawings in which the edges are represented by circular arcs meeting at equal angles at each vertex. We also use it to characterize the graphs of two-dimensional soap bubble clusters as being exactly the 2-vertex-connected 3-regular planar graphs.
A brief history of curves in graph drawing.
D. Eppstein.
Invited survey talk at Workshop on Drawing Graphs and Maps with Curves, Dagstuhl, Germany, April 2013.
Drawing Graphs and Maps with Curves (Dagstuhl Seminar 13151), S. G. Kobourov, M. Nöllenburg, and M. Teillaud, eds., Dagstuhl Reports 3(4): 40–46, 2013.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(n3/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.
Structures in solution spaces: Three lessons from Jean-Claude.
D. Eppstein.
Invited talk, Conference on Meaningfulness and Learning Spaces: A Tribute to the Work of Jean-Claude Falmagne
Irvine, California, 2014.This talk surveys my work on rectangular cartograms, the 1/3-2/3 conjecture for antimatroids, and flip distance for triangulations of point sets with no empty pentagon, and how this line of research stemmed from the work of Jean-Claude Falmagne on learning spaces.
Distance-sensitive point location made easy.
B. Aronov, M. De Berg, D. Eppstein, M. Roeloffzen, and B. Speckmann.
30th European Workshop on Computational Geometry (EuroCG 2014), Dead Sea, Israel, March 2014.
arXiv:1602.00767
Comp. Geom. Theory & Applications 54: 17–31, 2016.We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.
Wear minimization for cuckoo hashing: how not to throw a lot of eggs into one basket.
D. Eppstein, M. T. Goodrich, M .Mitzenmacher, and P. Pszona.
arXiv:1404.0286.
Proc. 13th International Symposium on Experimental Algorithms (SEA 2014), Copenhagen, Denmark, 2014.
Springer, Lecture Notes in Comp. Sci. 8504, pp. 162–173, 2014.We study cuckoo hashing data structures in a model of flash memory in which each memory cell has a limited number of times it can be changed, so the goal is to prevent hot spots that change many times.
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)
Linear-time algorithms for proportional apportionment.
Z. Cheng and D. Eppstein.
arXiv:1409.2603.
Proc. 25th Int. Symp. Algorithms and Computation (ISAAC 2014), Jeonju, Korea, 2014.
Springer, Lecture Notes in Comp. Sci. 8889, 2014, pp. 581–592.We consider a broad class of highest averages methods for proportional allocation (the problems of allocating seats to parties after a parliamentary election, or of allocating congressmen to states based on total population). We show that these methods can be simulated by an algorithm whose running time is proportional only to the number of parties or states, independent of the number of seats allocated or the number of voters.
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 (special issue for WALCOM).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.
On the planar split thickness of graphs.
D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.
arXiv:1512.04839.
Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 403–415.
Algorithmica 80 (3): 977–994 (special issue for LATIN), 2018.We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.
From discrepancy to majority.
D. Eppstein and D. S. Hirschberg.
arXiv:1512.06488.
Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
Algorithmica 80 (4): 1278–1297, 2018.We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.
The computational hardness of dK-series.
W. E. Devanny, D. Eppstein, and B. Tillman.
NetSci2016 poster session, Seoul, Korea.The dK-series is an extension of the degree sequence of a graph to a d-dimensional tensor, describing the number of d-tuples of vertices with each possible combination of degrees and adjacencies. As we show, it is NP-hard to determine whether such a tensor represents a valid graph, for any d ≥ 3, or for d = 2 if the number of triangles in the graph is also specified (or constrained to be zero).
Models and algorithms for graph watermarking.
D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.
arXiv:1605.09425.
Proc. 19th Information Security Conference (ISC 2016), Honolulu, Hawaii.
Springer, Lecture Notes in Comp. Sci. 9866 (2016), pp. 283–301.We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.
Scheduling autonomous vehicle platoons through an unregulated intersection.
J. Besa, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
Proc. 16th Worksh. Algorithmic Approaches for Transportation Modelling, Optimization and Systems (ATMOS 2016), Aarhus, Denmark, 2016.
OpenAccess Series in Informatics (OASIcs) 54, Schloss Dagstuhl (2016), pp. 5:1–5.16.
arXiv:1609.04512.We consider a model of vehicle scheduling in which vehicles arrive at an intersection in indivisible platoons (or individual vehicles of variable length) and the goal is to find a schedule for them to all cross the intersection without collisions, minimizing the maximum delay incurred by any platoon. We show that for many types of intersections, an optimal schedule can be found in polynomial time by a combination of dynamic programming and parametric search.
K-best solutions of MSO problems on tree-decomposable graphs.
D. Eppstein and D. Kurz.
arXiv:1703.02784.
Proc. 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria, 2017.
Leibniz International Proceedings in Informatics (LIPIcs) 89, pp. 16.1–16.13We show that, on graphs of bounded treewidth, for any optimization problem definable in monadic second-order logic, we can find the k best solutions in logarithmic time per solution.
Algorithms for stable matching and clustering in a grid.
D. Eppstein, M. T. Goodrich, and N. Mamano.
arXiv:1704.02303
Proc. 18th International Workshop on Combinatorial Image Analysis (IWCIA 2017), Plovdiv, Bulgaria, 2017.
Springer, Lecture Notes in Comp. Sci. 10256 (2017), pp. 117–131.Motivated by redistricting, we consider geometric variants of the stable matching problem in which points (such as the pixels of a discretization of the unit square) are to be matched to a smaller number of centers such that each center has the same number of matches and no match is unstable with respect to Euclidean distances. We show how to solve such problems in polylogarithmic time per matched point, experiment with practical heuristics for solving these problems, and test methods for moving the centers to improve the shape of the matched regions.
2-3 cuckoo filters for faster triangle listing and set intersection.
D. Eppstein, M. T. Goodrich, M. Mitzenmacher, and M. Torres.
Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017), Chicago, 2017, pp. 247–260.We show that bit-parallel algorithm design techniques, on a machine of word size w, can speed up the time for sparse set intersection by a factor of log w/w. The main data structure underlying our algorithms is the cuckoo filter, a variant of cuckoo hash tables that has operations similar to a Bloom filter but outperforms Bloom filters in several respects.
Using multi-level parallelism and 2-3 cuckoo filters for faster set intersection queries and sparse boolean matrix multiplication.
D. Eppstein and M. T. Goodrich.
Brief announcement, Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Washington, DC, 2017, pp. 137–139.We provide parallel versions of our bit-parallel algorithms from PODS 2017 for sparse set intersection.
Defining equitable geographic districts in road networks via stable matching.
D. Eppstein, M. T. Goodrich, D. Korkmaz, and N. Mamano.
arXiv:1706.09593
Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 52:1–52:4.We cluster road networks (modeled as planar graphs, or more generally as graphs obeying a separator theorem) with a given set of cluster centers, by matching graph vertices to centers stably according to distance: no unmatched vertex and center should have smaller distances than the matched pairs for the same points. We provide a separator-based data structure for dynamic nearest neighbor queries in planar or separated graphs, which allows the optimal stable clustering to be constructed in time O(n3/2log n). We also experiment with heuristics for fast practical construction of this clustering.
Crossing patterns in nonplanar road networks.
D. Eppstein and S. Gupta.
arXiv:1709.06113.
Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 40:1–40:9.We show that, although an individual edge in a road network can have many crossings, real-world road networks have the property that the crossing graph of their edges is sparse. We prove that networks with this property are themselves sparse and have small separators, allowing many fast algorithms to be generalized from planar graphs to these networks.
Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
arXiv:1710.00426.
Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.We show that the K1,1,3-free partial 2-trees and the Halin graphs other than K4 can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.
NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs.
D. Eppstein and V. V. Vazirani.
arXiv:1802.00084.
Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Phoenix, Arizona, 2019, pp. 23–30.
SIAM J. Computing 50 (3): 1014–1033, 2021.We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.
Reactive proximity data structures for graphs.
D. Eppstein, M. T. Goodrich, and N. Mamano.
arXiv:1803.04555.
Proc. 13th Latin American Theoretical Informatics Symposium (LATIN 2018), Buenos Aires, Argentina.
Springer, Lecture Notes in Comp. Sci. 10807 (2018), pp. 777–789.We develop data structures for solving nearest neighbor queries for dynamic subsets of vertices in a planar graph, or more generally for a graph in any graph class with small separators (polynomial expansion).
Subexponential-time and FPT algorithms for embedded flat clustered planarity.
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
arXiv:1803.05465
Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), Lübbenau, Germany.
Springer, Lecture Notes in Comp. Sci. 11159 (2018), pp. 111–124.Clustered planarity is the problem of simultaneously drawing a planar graph and a clustering of its vertices (as Jordan curves surrounding the cluster) with no unnecessary crossings between edges or cluster boundaries; it remains unknown whether it can be solved in polynomial time. We provide parameterized and subexponential exact algorithms for the case where the planar embedding is fixed and the clusters form a partition of the vertices.
Faster evaluation of subtraction games.
D. Eppstein.
arXiv:1804.06515.
Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 20:1–20:12.We show how to evaluate the set of winning heap sizes in subtraction games like subtract-a-square in near-linear time, and how to compute the nim-values more quickly than naive dynamic programming. Additionally we perform computational experiments showing that the set of winning positions forms an unexpectedly dense square-difference-free set.
Making change in 2048.
D. Eppstein.
arXiv:1804.07396.
Proc. 9th Int. Conf. Fun with Algorithms (FUN 2018), La Maddalena, Italy.
Leibniz International Proceedings in Informatics (LIPIcs) 100, pp. 21:1–21:13.The 2048 puzzle, modified to use any sequence of integer tile values that has arbitrarily large gaps, always terminates. The proof relates the puzzle to the greedy algorithm for making change (suboptimally) using a given system of coins.
Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
arXiv:1805.04055
Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Qingdao, China.
Springer, Lecture Notes in Comp. Sci. 10976 (2018), pp. 365–377.
Theor. Comput. Sci. 806: 332–343, 2020.For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.
Parameterized leaf power recognition via embedding into graph products.
D. Eppstein and E. Havvaei.
arXiv:1810.02452.
Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 16:1–16:14.
Algorithmica 82 (8): 2337–2359, 2020 (special issue for IPEC 2018).A leaf power graph is the graph formed from the leaves of a tree by making two leaves adjacent when their tree distance is at most k. We show that recognizing these graphs is fixed-parameter tractable in a combination of two parameters: k and the degeneracy of the graph.
(James Nastos has pointed out a minor error in our statement of known prior results: the figure depicting chordal graphs that are not 4-leaf powers is labeled as a complete set of forbidden subgraphs, but it is only the complete set among graphs without true twin vertices.)
The parameterized complexity of finding point sets with hereditary properties.
D. Eppstein and D. Lokshtanov.
arXiv:1808.02162
Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 11:1–11:14.We exhibit a hereditary property of planar point sets (depending only on the order type of a point set) such that under standard assumptions there is no fixed-parameter-tractable algorithm to find a k-point subset with the property. On the other hand, several natural classes of properties have FPT algorithms for this problem, including the properties that are true for all collinear point sets or false for at least one convex polygon.
Applications of nearest-neighbor chains: Euclidean TSP and motorcycle graphs.
N. Mamano, A. Efrat, D. Eppstein, D. Frishberg, M. T. Goodrich, and S. G. Kobourov, P. Matias, and V. Polishchuk.
arXiv:1902.06875.
Computational Geometry: Young Researchers Forum, 2019.
Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 51:1–51:21.We apply the nearest-neighbor chain algorithm to repeatedly find pairs of mutual nearest neighbors for different distances, speeding up the times for the multi-fragment TSP heuristic, motorcycle graphs, straight skeletons, and other problems.
Graphs in nature.
D. Eppstein.
Invited talk at Symposium on Geometry Processing, Milan, Italy, July 2019.
Invited talk at Algorithms and Data Structures Symposium, Edmonton, Canada, August 2019.
Invited talk at International Colloquium on Graph Theory and Combinatorics, Montpellier, France, July 2022.I survey results on characterizing the graphs formed on planar surfaces according to several natural processes: motorcycle graphs, Gilbert tessellations, and the contact graphs of line segments from needle-like crystal growth and crack formation; the graphs of planar soap bubble foams; and graphs representing the fold patterns of crumpled paper.
C-planarity testing of embedded clustered graphs with bounded dual carving-width.
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
arXiv:1910.02057.
Proc. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Munich, Germany, 2019 (best paper award).
Leibniz International Proceedings in Informatics (LIPIcs) 148, 2019, pp. 9:1–9:17.
Algorithmica 83 (8): 2471–2502, 2021 (special issue for IPEC 2019).We show that finding clustered planar drawings can be done in fixed-parameter-tractable time, depending only on a single width parameter of the input clustered graph.
Tracking paths in planar graphs.
D. Eppstein, M. T. Goodrich, P. Matias, and J. A. Liu.
arXiv:1908.05445.
Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 54:1–54:17.A tracking set for a given graph, with designated start and destination vertices, is a set of vertices such that any path from start to destination is determined by the subsequence of its vertices that belong to the tracking set. We show that finding the smallest tracking set is NP-hard but has a constant factor approximation, and can be solved exactly in fixed-parameter-tractable time for graphs of bounded width.
On the treewidth of Hanoi graphs.
D. Eppstein, D. Frishberg, and W. Maxwell.
arXiv:2005.00179.
Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
Theor. Comput. Sci. 906: 1–17, 2022.The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of np − 1.
The graphs of stably matchable pairs.
D. Eppstein.
arXiv:2010.09230.
47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021).
Springer, Lecture Notes in Comp. Sci. 12911 (2021), pp. 349–360.If you form a bipartite graph from a stable matching instance, with an edge for each pair that can participate in a stable matching, what graphs can you get? They are matching-covered, but NP-hard to recognize, and their structure is related to the structure of the lattice of stable matchings of the same instance.
Geometric dominating sets – A minimum version of the no-three-in-line problem.
O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
37th European Workshop on Computational Geometry (EuroCG 2021), pp. 17:1–17:7.
arXiv:2203.13170.
Comp. Geom. Theory & Applications 108: 101913, 2023 (special issue for EuroCG).We study how few points can be placed in a grid so that all remaining grid points are collinear with two of the placed points.
Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes.
D. Eppstein, E. Havvaei, and S. Gupta.
arXiv:2101.09918.
Proc. 23rd International Symposium on Fundamentals of Computation Theory, 2021.
Springer, Lecture Notes in Comp. Sci. 12867 (2021), pp. 217–229.We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).
Distributed construction of lightweight spanners for unit ball graphs.
D. Eppstein and H. Khodabandeh.
arXiv:2106.15234.
Brief announcement, 34th ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 57–59.
Proc. 36th International Symposium on Distributed Computing (DISC 2022).
Leibniz International Proceedings in Informatics (LIPIcs) 246, 2022, pp. 21:1–21:23.Metric spaces of bounded doubling dimension have spanners with bounded degree, weight a bounded multiple of the minimum spanning tree weight, and dilation arbitrarily close to one, that can be found efficiently by a distributed algorithm.
Multifold tiles of polyominoes and convex lattice polygons.
K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
Thai Journal of Mathematics 21 (4): 957–978, 2023.We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).
Finding relevant points for nearest-neighbor classification.
D. Eppstein.
arXiv:2110.06163.
Proc. SIAM Symp. Simplicity in Algorithms, 2022, pp. 68–78; best paper award winner.The nearest-neighbor classification problem considered here takes as input a training set of points in a Euclidean space, each with a classification from some finite set of classes or colors, and then uses that input to predict the classification of new points as being equal to that of the nearest neighbor in the input training set. A training point is irrelevant when removing it from the training set would produce the same predicted classification for all possible new points that might be queried. We describe how to find all of the relevant points, in polynomial time, using a simple algorithm whose only components are construction of a minimum spanning tree of the training set and the computation of extreme points (convex hull vertices) of geometrically transformed subsets of points. For any constant dimension, with \(k\) relevant points resulting from a training set of \(n\) points, this method can be made to take time \(O(n^2+k^2n)\), using only simple algorithms for the minimum spanning tree and extreme point subroutines. For small dimensions, somewhat better but more complicated bounds are possible.
Rapid mixing of the hardcore Glauber dynamics and other Markov chains in bounded-treewidth graphs.
D. Eppstein and D. Frishberg.
arXiv:2111.03898.
Proc 34th International Symposium on Algorithms and Computation (ISAAC 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 283, 2022, pp. 30:1–30:13.A random walk on the independent sets or dominating sets of a graph mixes rapidly for graphs of bounded treewidth, and a random walk on maximal independent sets mixes rapidly for graphs of bounded carving width.
Geodesic paths passing through all faces on a polyhedron.
E. Demaine, M. Demaine, D. Eppstein, H. Ito, Y. Katayama, W. Maruyama, and Y. Uno.
24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, September 9–11, 2022.
Springer, Lecture Notes in Comp. Sci. 14364 (2026), pp. 184–209.Which convex polyhedra have the property that there exist two points on the surface of the polyhedron whose shortest path passes through all of the faces of the polyhedron? The answer is yes for the tetrahedron, and for certain prisms, but no for all other regular polyhedra.
Widths of geometric graphs.
D. Eppstein.
Invited talk, Workshop on Parameterized Algorithms for Geometric Problems, CG Week 2023.Many computational geometry problems can be solved by transforming them into a graph problem on a geometric graph. When the graph has low width, for some form of graph width, this can often lead to efficient classical or parameterized algorithms. We survey the geometric graphs that always have low width, the geometric graphs that can have high width, and the opportunities for parameterization obtained by studying low-width instances of graphs that sometimes have high width.
Uniqueness in puzzles and puzzle solving.
D. Eppstein.
Minisymposium on Mathematical Puzzles and Games in Theoretical Computer Science, ICIAM, Waseda Univ., Tokyo, Japan, 2023.In puzzles such as Sudoku, one can often make use of an assumption that the solution is unique, in deduction rules that eliminate alternatives that would lead to a non-unique solution. However, these rules can lack the monotonicity properties of other deduction rules, under which a conclusion that can be deduced from some partially-solved state of the puzzle remains available to be deduced until it actually is deduced. I discuss a method of obtaining monotonic deductions in a planar precoloring extension puzzle, and ask whether there is some more general method for obtaining monotonicity in this way.
Games on game graphs.
D. Eppstein. AMS Special Session on Serious Recreational Mathematics, Joint Mathematics Meetings, San Francisco, 2024.This talk surveys graph parameters defined from pursuit-evasion games on graphs, including cop-number, treewidth, and flip-width, and the values of these parameters on graphs derived from games and puzzles.
Computational complexities of folding.
D. Eppstein.
Invited talk, 8th International Meeting on Origami in Science, Mathematics and Education, Melbourne, Australia, 2024.
Invited talk, 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
arXiv:2410.07666.
Journal of Information Processing 33: 954–973, 2025.We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.
Zip-tries: simple dynamic data structures for strings.
D. Eppstein, O. Gila, M. T. Goodrich, and R. Kitagawa.
SIAM Conference on Applied and Computational Discrete Algorithms (ACDA25), Montreal, Canada, 2025, pp. 130–143.
arXiv:2505.04953.We provide fast parallel and bit-parallel data structures for string search in a dynamic set of strings, with few bits of metadata per node.
Better late than never: the complexity of arrangements of polyhedra.
B. Aronov, S. W. Bae, O. Cheong, D. Eppstein, C. Knauer, and R. Seidel.
41st European Workshop on Computational Geometry (EuroCG 2025), Liblice, Czech Republic, pp. 62:1–62:4.
arXiv:2506.03960.My 1994 paper "On the number of minimal 1-Steiner trees" with Aronov and Bern, in some preliminary manuscript versions, included a bound of \(O(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor})\) on the complexity of an arrangement of \(m\) convex polytopes given as intersections of a total of \(n\) halfspaces, interpolating between the upper bound theorem for polytopes and the complexity of hyperplane arrangements. However, the manuscript and the proof were lost. This paper re-proves the result, with better care for the degenerate cases.