Publications with no journal or book chapter version
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.
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.
Efficient sequential and parallel algorithms for computing recovery points in trees and paths.
M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158–167.
ALCOM Report 91-74, University of Rome, 1991.Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.
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).
Worst-case bounds for subadditive geometric graphs.
M. Bern and D. Eppstein.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 183–188.For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).
Dihedral bounds for mesh generation in high dimensions.
M. Bern, L.P. Chew, D. Eppstein, and J. Ruppert.
892nd Meeting Amer. Math. Soc., Brooklyn, 1994.
Abstract in Abs. Amer. Math. Soc. 15, 1994, p. 366.
6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 189–196.Any d-dimensional point set can be triangulated with O(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.
The centroid of points with approximate weights.
M. Bern, D. Eppstein, L. J. Guibas, J. Hershberger, S. Suri, and J. Wolter.
3rd Eur. Symp. Algorithms, Corfu, 1995.
Springer, Lecture Notes in Comp. Sci. 979, 1995, pp. 460–472.Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.
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.
Faster construction of planar two-centers.
D. Eppstein.
Tech. Rep. 96-12, ICS, UCI, 1996.
8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 131–138.Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log2 n).
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.
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.
An efficient algorithm for shortest paths in vertical and horizontal segments.
D. Eppstein and D. Hart.
5th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 1997.
Springer, Lecture Notes in Comp. Sci. 1272, 1997, pp. 234–247.We show how to find shortest paths along the segments of an arrangement of n vertical and horizontal line segments in the plane, in time O(n3/2).
Shortest paths in an arrangement with k line orientations.
D. Eppstein and D. Hart.
10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. 310–316.We show how to find shortest paths between two points on the lines of an arrangement of n lines with k distinct orientations, in time O(n + k2).
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.
Parametric and kinetic minimum spanning trees.
P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596–605..We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n1/4 polylog n) per combinatorial change to the tree for planar graphs.
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.
Internet packet filter management and rectangle geometry.
D. Eppstein and S. Muthukrishnan.
arXiv:cs.CG/0010018.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827–835.Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n3/2) time algorithm for testing whether a rule set contains any ambiguities.
Optimal Möbius transformations for information visualization and meshing.
M. Bern and D. Eppstein.
arXiv:cs.CG/0101006.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 14–25.We give linear-time quasiconvex programming algorithms for finding a Möbius transformation of a set of spheres in a unit ball or on the surface of a unit sphere that maximizes the minimum size of a transformed sphere. We can also use similar methods to maximize the minimum distance among a set of pairs of input points. We apply these results to vertex separation and symmetry display in spherical graph drawing, viewpoint selection in hyperbolic browsing, and element size control in conformal structured mesh generation.
Optimization over zonotopes and training support vector machines.
M. Bern and D. Eppstein.
arXiv:cs.CG/0105017.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 111–121.We use the ellipsoid method to develop (theoretically) efficient algorithms for optimizing linear functions on intersections of zonotopes, and show how to apply this to train soft-margin support vector classifiers.
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.
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.
Möbius-invariant natural neighbor interpolation.
M. Bern and D. Eppstein.
arXiv:cs.CG/0207081.
14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 128–129.Natural neighbor interpolation is a well-known technique for fitting a surface to scattered data, with some nice properties including smoothness everywhere except the data and exact fitting of linear functions. The interpolated surface is formed from a weighted combination of data values at the "natural neighbors" (neighbors in the Delaunay triangulation), with weights related to Voronoi cell areas. We describe a variation of natural neighbor interpolation, using different weights based on Delaunay circle angles, that remains invariant when the data is transformed by Möbius transformations, and reconstructs harmonic functions in the limit of dense data on a circle.
Dynamic generators of topologically embedded graphs.
D. Eppstein.
arXiv:cs.DS/0207082.
14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 599–608.We describe a decomposition of graphs embedded on 2-dimensional manifolds into three subgraphs: a spanning tree, a dual spanning tree, and a set of leftover edges with cardinality determined by the genus of the manifold. This tree-cotree decomposition allows us to find efficient data structures for dynamic graphs (allowing updates that change the surface), better constants in bounded-genus graph separators, and efficient algorithms for tree-decomposition of bounded-genus bounded-diameter graphs.
Optimized color gamuts for tiled displays.
M. Bern and D. Eppstein.
arXiv:cs.CG/0212007.
19th ACM Symp. Comp. Geom., San Diego, 2003, pp. 274–281.We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.
Lazy algorithms for dynamic closest pair with arbitrary distance measures.
J. Cardinal and D. Eppstein.
Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004, pp. 112–119.We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.
Selected open problems in graph drawing.
F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.We survey a number of open problems in theoretical and applied graph drawing.
The geometric thickness of low degree graphs.
C. Duncan, D. Eppstein, and S. Kobourov.
arXiv:cs.CG/0312056.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 340–346.We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.
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.
Algorithms for drawing media.
D. Eppstein.
arXiv:cs.DS/0406020.
12th Int. Symp. Graph Drawing, New York, 2004.
Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 173–183.We describe two algorithms for finding planar layouts of partial cubes: one based on finding the minimum-dimension lattice embedding of the graph and then projecting the lattice onto the plane, and the other based on representing the graph as the planar dual to a weak pseudoline arrangement.
Due to editorial mishandling there will be no journal version of this paper: I submitted it to a journal in 2004, the reviews were supposedly sent back to me in 2005, but I didn't receive them and didn't respond to them, leading the editors to assume that I intended to withdraw the submission. Large portions of the paper have since been incorporated into my book Media Theory, making journal publication moot.
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.
The weighted maximum-mean subtree and other bicriterion subtree problems.
J. Carlson and D. Eppstein.
arXiv:cs.CG/0503023.
Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
Springer, Lecture Notes in Comp. Sci. 4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".
Delta-confluent drawings.
D. Eppstein, M. T. Goodrich, and J. Meng.
13th Int. Symp. Graph Drawing, Limerick, Ireland, 2005.
Springer, Lecture Notes in Comp. Sci. 3843, 2006, pp. 165–176.
arXiv:cs.CG/0510024.We characterize the graphs that can be drawn confluently with a single confluent track that is tree-like except for three-way Delta junctions, as being exactly the distance hereditary graphs. Based on this characterization, we develop efficient algorithms for drawing these graphs.
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.
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.
Guard placement for efficient point-in-polygon proofs.
D. Eppstein, M. T. Goodrich, and N. Sitchinava.
arXiv:cs.CG/0603057.
23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 27–36.The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.
Trees with convex faces and optimal angles.
J. Carlson and D. Eppstein.
arXiv:cs.CG/0607113.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 77–88.We consider drawings of trees which, if the leaf edges were extended to infinite rays, would form partitions of the plane into unbounded convex polygons. For such a drawing the edges may be chosen independently without any possibility of edge crossing. We show how to choose the angles of such drawings to optimize the angular resolution of the drawing.
Choosing colors for geometric graphs via color space embeddings.
M. Dillencourt, D. Eppstein, and M. T. Goodrich.
arXiv:cs.CG/0609033.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 294–305.We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.
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.
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.
Straight skeletons of three-dimensional polyhedra.
G. Barequet, D. Eppstein, M. T. Goodrich, and A. Vaxman.
arXiv:0805.0022.
Proc. 16th European Symp. Algorithms, Karlsruhe, Germany, 2008.
Springer, Lecture Notes in Comp. Sci. 5193, 2008, pp. 148–160.A straight skeleton is defined by the locus of points crossed by the edges and vertices of a polyhedron as it undergoes a continuous shrinking process in which the faces move inwards at constant speed. We resolve some ambiguities in the definition of these shapes, define efficient algorithms for polyhedra with axis-parallel faces, show that arbitrary polyhedra have strictly more complicated straight skeletons, and report on results from an implementation of our algorithm for arbitrary polyhedra.
Isometric diamond subgraphs.
D. Eppstein.
arXiv:0807.2218.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 384–389.We describe polynomial time algorithms for determining whether an undirected graph may be embedded in a distance-preserving way into the hexagonal tiling of the plane, the diamond structure in three dimensions, or analogous structures in higher dimensions. The graphs that may be embedded in this way form an interesting subclass of the partial cubes.
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.
Self-overlapping curves revisited.
D. Eppstein and E. Mumford.
arXiv:0806.1724.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 160–169.We consider problems of determining when a curve in the plane is the projection of a 3d surface with no vertical tangents. Several problems of this type are NP-complete, but can be solved in polynomial time if a casing of the curve is also given.
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.
Animating a continuous family of two-site distance function Voronoi diagrams (and a proof of a complexity bound on the number of non-empty regions).
M. Dickerson and D. Eppstein.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, video and multimedia track, pp. 92–93.We investigate distance from a pair of sites defined as the sum of the distances to each site minus a parameter times the distance between the two sites. A given set of n sites defines n(n-1)/2 pairs and n(n-1)/2 distances in this way, from which we can determine a Voronoi diagram. As we show, for a wide range of parameters, the diagram has relatively few regions because the pairs that have nonempty Voronoi regions must be Delaunay edges.
On the approximability of geometric and geographic generalization and the min-max bin covering problem.
W. Du, D. Eppstein, M. T. Goodrich, G. Lueker.
arXiv:0904.3756.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 242–253.We investigate several simplified models for k-anonymization in databases, show them to be hard to solve exactly, and provide approximation algorithms for them.
The min-max bin covering problem is closely related to one of our models. An input to this problem consists of a collection of items with sizes and a threshold size. The items must be grouped into bins such that the total size within each bin is at least the threshold, while keeping the maximum bin size as small as possible.
Optimal embedding into star metrics.
D. Eppstein and K. Wortman.
arXiv:0905.0283.
Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 290–301.We provide an O(n3 log2n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform 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. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.
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.
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.
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.
Cloning Voronoi diagrams via retroactive data structures.
M. Dickerson, D. Eppstein, and M. T. Goodrich.
arXiv:1006.1921.
18th Eur. Symp. Algorithms, Liverpool, 2010.
Springer, Lecture Notes in Comp. Sci. 6346, 2010, pp. 362–373.We analyze the security of an online geometric database that allows planar nearest-neighbor queries but that does not wish the entire database to be copied by a competitor. We show that, under several models of how the query answers are returned, the database can be copied in a linear or near-linear number of queries. Our method for the competitor to copy the database is based on simulating Fortune's sweep-line algorithm for Voronoi diagrams, backtracking when the simulation discovers the existence of another point that invalidates earlier parts of the Voronoi diagram construction, and using retroactive data structures to perform the backtracking steps efficiently.
Regular labelings and geometric structures.
D. Eppstein.
arXiv:1007.0221.
Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
Invited to Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
Springer, Lecture Notes in Comp. Sci. 6506, 2010, p. 1.We survey regular labelings for straight-line embedding of planar graphs on grids, rectangular partitions, and orthogonal polyhedra, and the many similarities between these different types of labeling.
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.
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.
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.
Tracking moving objects with few handovers.
D. Eppstein, M. T. Goodrich, and M. Löffler.
arXiv:1105.0392.
12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 362–373.We apply competitive analysis to the problem of deciding online which cell phone tower to change to when a phone moves out of the coverage region of the tower it is connected to. We show that, when the coverage regions have constant ply (at most a constant number of them overlap any point of the plane) it is possible to get within a constant factor of the minimum possible number of handovers that an offline algorithm could achieve.
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.
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.
Privacy-enhanced methods for comparing compressed DNA sequences.
D. Eppstein, M. T. Goodrich, and P. Baldi.
arXiv:1107.3593.
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.
Force-directed graph drawing using social gravity and scaling.
M. J. Bannister, D. Eppstein, M. T. Goodrich, and L. Trott.
arXiv:1209.0748.
20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 414–425.We extend force-directed methods of graph drawing by adding a force that pulls vertices towards the center of the drawing, with a strength proportional to the centrality of the vertex. Gradually scaling up this force helps avoid the tangling that would otherwise result from its use.
On the density of maximal 1-planar graphs.
F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, and J. Reislhuber.
20th Int. Symp. Graph Drawing, Redmond, Washington, 2012.
Springer, Lecture Notes in Comp. Sci. 7704, 2013, pp. 327–338.A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge, and maximal 1-planar if it is 1-planar but adding any edge would force more than one crossing on some edge or edges. Although maximal 1-planar graphs on n vertices may have as many as 4n − 8 edges, we show that there exist maximal 1-planar graphs with as few as 45n/17 + O(1) edges.
Windows into relational events: data structures for contiguous subsequences of edges.
M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth.
NIPS 2012 Workshop on Algorithmic and Statistical Approaches for Large Social Networks, South Lake Tahoe, California, 2012 (poster and invited talk).
24th ACM-SIAM Symp. Discrete Algorithms, New Orleans, Louisiana, 2013, pp. 856–864.
arXiv:1209.5791.We study relational event data in which a collection of actors in a social network have a sequence of pairwise interactions. Contiguous subsequences of these interactions form graphs, and we develop efficient data structures for querying the parameters of these 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.Set-difference range queries.
D. Eppstein, M. T. Goodrich, and J. Simons.
arXiv:1306.3482.
25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.We show how to use invertible Bloom filters as part of range searching data structures that determine the differences between the members of two sets that lie in a given query range.
Fixed parameter tractability of crossing minimization of almost-trees.
M. J. Bannister, D. Eppstein, and J. Simons.
arXiv:1308.5741.
21st Int. Symp. Graph Drawing, Bordeaux, France, 2013.
Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 340–351.Many real-world graphs are k-almost-trees for small values of k: graphs in which, in every biconnected component, removing a spanning tree leaves at most k edges. We use kernelization methods to show that in such graphs, the 1-page and 2-page crossing numbers can be computed quickly.
Convex-arc drawings of pseudolines.
D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.
21st Int. Symp. Graph Drawing (poster), Bordeaux, France, 2013.
Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 522–523.
arXiv:1601.06865.We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.
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.
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.
Balanced circle packings for planar graphs.
M. J. Alam, D. Eppstein, M. T. Goodrich, S. Kobourov, and S. Pupyrev.
arXiv:1408.4902.
22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 125–136.The balanced circle packings of the title are systems of interior-disjoint circles, whose tangencies represent the given graph, and whose radii are all within a polynomial factor of each other. We show that these packings always exist for trees, cactus graphs, outerpaths, k-outerplanar graphs of bounded degree when k is at most logarithmic, and planar graphs of bounded treedepth. The treedepth result uses a new construction of inversive-distance circle packings.
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.
Minimum forcing sets for Miura folding patterns.
B. Ballinger, M. Damian, D. Eppstein, R. Flatland, J. Ginepro, and T. Hull.
arXiv:1410.2231.
26th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2015, pp. 136–147.A forcing set for an origami crease pattern is a subset of the folds with the property that, if these folds are folded the correct way (mountain vs valley) the rest of the pattern also has to be folded the correct way. We use a combinatorial equivalence with three-colored grids to construct minimum-cardinality forcing sets for the Miura-ori folding pattern and for other patterns with differing folds along the same line segments.
All-pairs minimum cuts in near-linear time for surface-embedded graphs.
G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen.
arXiv:1411.7055.
Proc. 32nd Int. Symp. Computational Geometry, Boston, 2016.
Leibniz International Proceedings in Informatics (LIPIcs) 51, pp. 22:1–22:16.We give the first known near-linear algorithms for constructing Gomory–Hu trees of bounded-genus graphs, and we shave a log off the time for the same problem on planar graphs.
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.
Contact graphs of circular arcs.
M. J. Alam, D. Eppstein, M. Kaufmann, S. Kobourov, S. Pupyrev A. Schulz, and T. Ueckerdt.
arXiv:1501.00318.
14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 1–13.We study the graphs formed by non-crossing circular arcs in the plane, having a vertex for each arc and an edge for each point where an arc endpoint touches the interior of another arc.
Finding all maximal subsequences with hereditary properties.
D. Bokal, S. Cabello, and D. Eppstein.
Proc. 31st Int. Symp. on Computational Geometry, Eindhoven, the Netherlands, June 2015.
Leibniz International Proceedings in Informatics (LIPIcs) 34, pp. 240–254.We study problems in which the input is a sequence of points in the plane and we wish to find, for each position in the sequence, the longest contiguous subsequence that begins at that position and has some geometric property. For many natural properties we can find all such maximal subsequences in linear or near-linear time.
Confluent orthogonal drawings of syntax diagrams.
M. J. Bannister, D. A. Brown, and D. Eppstein.
arXiv:1509.00818.
23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 260–271.We describe a system for transforming context-free grammars into human-readable syntax diagrams, including optimizations that change the structure of the grammar to make it more readable without affecting the language described by the grammar.
Cuckoo filter: simplification and analysis.
D. Eppstein.
arXiv:1604.06067.
Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland.
Leibniz International Proceedings in Informatics (LIPIcs) 53, pp. 8.1–8.12.A cuckoo filter is an approximate set data structure that can be used in place of a Bloom filter, but with several practical advantages: it uses less space, has better locality of reference, and can handle element deletions. We provide the first theoretical analysis of a simplified variation of cuckoo filters, showing that these advantages can be guaranteed to hold theoretically and not just experimentally.
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.
Forbidden configurations in discrete geometry.
D. Eppstein.
Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.
Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.
Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.
Invited talk, Southern California Theory Day, Irvine, California, 2018.
Cambridge University Press, 2018.We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.
(CCCG talk slides – CCCG talk video – SCTD talk slides – Updates, errata, and reviews)
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.
Quadratic time algorithms appear to be optimal for sorting evolving data.
J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
arXiv:1805.05443.We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.
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.
Optimally sorting evolving data.
J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
arXiv:1805.03350
Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.
Geometric fingerprint matching via oriented point-set pattern matching.
D. Eppstein, M. T. Goodrich, J. Jorgensen, and M. Torres.
arXiv:1808.00561
Proc. 30th Canadian Conference on Computational Geometry, Winnepeg, Canada, 2018, pp. 98–113.When matching fingerprints, the data involves planar points each of which has an associated direction. Motivated by this application, we consider point matching problems in which the distance between points combines both their translational distance and the rotation needed to make their directions align. We provide fast and simple approximation schemes for matching oriented point sets under the directed Hausdorff distance with different allowed groups of transformations.
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.
Stable-matching Voronoi diagrams.
D. Eppstein.
Invited talk at 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3), Manila, Philippines, 2018.We survey the results from several of my earlier papers: Algorithms for stable matching and clustering in a grid, Defining equitable geographic districts in road networks via stable matching, Reactive proximity data structures for graphs, and Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
Finding maximal sets of laminar 3-separators in planar graphs in linear time.
D. Eppstein and B. Reed.
arXiv:1810.07825.
30th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2019, pp. 589–605.Given a 3-vertex-connected planar graph, we find a hierarchical decomposition of the graph by 3-vertex separators, such that each piece of the decomposition is 4-vertex-connected, in linear time. The result has applications to an algorithm of Kawarabayashi, Li, and Reed for finding disjoint paths in nonplanar graphs.
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.
Reconfiguring undirected paths.
E. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara, and Y. Uno.
arXiv:1905.00518.
16th Algorithms and Data Structures Symp. (WADS 2019), Edmonton, Alberta.
Springer, Lecture Notes in Comp. Sci. 11646 (2019), pp. 353–365.A motion that slides an undirected path along its length from one configuration to another in a graph (allowing moves in both directions) can be found in time that is fixed-parameter tractable in the path length. However the problem is PSPACE-complete for paths of unbounded length, even when the host graph has bounded bandwidth.
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.
Homotopy height, grid-minor height and graph-drawing height.
T. Biedl, E. Chambers, D. Eppstein, A. de Mesmay, and T. Ophelders.
arXiv:1908.05706.
Proc. 27th Int. Symp. Graph Drawing, Prague, Czech Republic, 2019.
Springer, Lecture Notes in Comp. Sci. 11904 (2019), pp. 468–481.We lower bound the height of a drawing of a planar graph in an integer grid by a topological invariant, the homotopy height, and show that this invariant is equal to the smallest height of a grid graph in which the given graph is a minor.
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.
Simplifying activity-on-edge graphs.
D. Eppstein, D. Frishberg, and E. Havvaei.
arXiv:2002.01610.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 24:1–24:14.Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.
Low-stretch spanning trees of graphs with bounded width.
G. Borradaile, E. Chambers, D. Eppstein, W. Maxwell, and A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.
On the edge crossings of the greedy spanner.
D. Eppstein and H. Khodabandeh.
arXiv:2002.05854.
Proc. 37th International Symposium on Computational Geometry (SoCG 2021).
Leibniz International Proceedings in Informatics (LIPIcs) 189, 2021, pp. 33:1–33:17.Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.
Dynamic products of ranks.
D. Eppstein.
arXiv:2007.08123.
Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 199–205.We provide data structures for the following problem: maintain a collection of points in the Euclidean plane, subject to insertions or deletions, and after each update find the point whose product of ranks according to the two sorted orders of the points by x- and y-coordinates is as small or as large as possible.
Acutely triangulated, stacked, and very ununfoldable polyhedra.
E. Demaine, M. Demaine, and D. Eppstein.
arXiv:2007.14525.
Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 106–113.We construct non-convex but topologically spherical polyhedra in which all faces are acute triangles, with no unfolded net.
New results in sona drawing: hardness and TSP separation.
M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
arXiv:2007.15784.
Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.
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.
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.
Limitations on realistic hyperbolic graph drawing.
D. Eppstein.
arXiv:2108.07441.
Proc. 29th Int. Symp. Graph Drawing, Tübingen, Germany, 2021.
Springer, Lecture Notes in Comp. Sci. 12868 (2021), pp. 343–357.Graphs drawn in the hyperbolic plane can be forced to have features much closer together than unit distance, in the absolute distance scale of the plane. In particular this is true for planar drawings of maximal planar graphs or grid graphs, and for nonplanar drawings of arbitrary graphs.
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.
Reflections in an octagonal mirror maze.
D. Eppstein.
arXiv:2206.11413.
34th Canadian Conference on Computational Geometry, 2022, pp. 129–134.For two-dimensional scenes consisting of mirrors and opaque walls that are either axis-parallel or with slope ±1, with integer endpoints, it is possible to determine the eventual destination of rational light rays in time polynomial in the description complexity of the scene, even though the number of reflections before a ray reaches this destination may be exponential. The solution involves transforming the problem into one involving interval exchange transformations and from there into another problem involving normal curves on topological surfaces.
Improved mixing for the convex polygon triangulation flip walk.
D. Eppstein and D. Frishberg.
arXiv:2207.09972.
Proc. 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 261, 2023, pp. 56:1–56:17.The associahedron is a polytope whose vertices represent the triangulations of a convex polygon, and whose edges represent flips connecting one triangulation to another. We show that a random walk on the edges of this polytope rapidly converges to the uniform distribution on triangulations. However, we also show that the associahedron does not have constant expansion.
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.
Lower bounds for non-adaptive shortest path relaxation.
D. Eppstein.
arXiv:2305.09230.
Proc. 18th Algorithms and Data Structures Symposium (WADS 2023).
Springer, Lecture Notes in Computer Science 13079 (2023), pp. 416–429.The Bellman–Ford algorithm for single-source shortest paths operates by relaxation steps, in which it checks for a given edge whether the best path it knows to the start of the edge, plus the edge itself, is better than the path it already knows to the end of the edge. We prove that, up to constant factors, Bellman–Ford is optimal among algorithms that use relaxation in an edge ordering that does not depend on the results of earlier relaxation steps.
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.
Geometric graphs with unbounded flip-width.
D. Eppstein and R. McCarty.
arXiv:2306.12611.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 197–208.We show that many constructions for dense geometric graphs produce graphs of unbounded flip-width, frustrating the search for natural classes of graphs that have bounded flip-width but unbounded twin-width.
Manipulating weights to improve stress-graph drawings of 3-connected planar graphs.
A. Chiu, D. Eppstein, and M. T. Goodrich.
arXiv:2307.10527.
Proc. 31st Int. Symp. Graph Drawing and Network Visualization, Palermo, Italy, 2023.
Springer, Lecture Notes in Computer Science 14466 (part II), pp. 141–149.In Tutte spring embeddings for planar graphs, it is possible to adjust the strengths of the springs and the fixed positions of the vertices on the outer face to obtain an infinite continuous family of straight-line planar embeddings. We experiment with making those adjustments to spread out the features of the drawing to better positions than they would have in the unweighted case.
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.
Maintaining light spanners via minimal updates.
D. Eppstein and H. Khodabandeh.
arXiv:2403.03290.
Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 1–15.We find a way to maintain a spanner of a dynamic point set, a graph approximating its distances to within a \(1+\varepsilon\) factor while maintaining weight proportionate to the minimum spanning tree. Each change to the point set leads to a logarithmic number of changes to the spanner, although update times remain slow.
Well-separated multiagent path traversal.
G. Dilman, D. Eppstein, V. Polishchuk, and C. Schmidt.
Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 137–144.We find algorithms and lower bounds for scheduling a sequence of release times for robots to follow the same path as each other, traversing the path at uniform speeds, and not colliding.
Drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature.
D. Eppstein, M. T. Goodrich, and A. M. Illickan.
32nd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 39:1–39:17.
arXiv:2410.12083.1-planar graphs are the graphs that can be drawn in the plane with at most one crossing per edge. We show that we can make all crossings into right angles using Bézier spline curve edges.
Computational geometry with probabilistically noisy primitive operations.
D. Eppstein, M. T. Goodrich, and V. Sridhar.
arXiv:2501.07707.
Proc. 19th Algorithms and Data Structures Symposium (WADS 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 349, 2025, pp. 24:1–24:20.An algorithm that uses Boolean primitive operations, like comparisons, that may be erroneous with some small independent probability per call, may be made to run correctly with high probability by repeating each primitive enough times to be sure its majority result is correct, but this incurs a logarithmic time penalty. Prior work avoids this penalty for sorting; we extend this speedup to algorithms in computational geometry that can be formulated using path search in DAGs. Applications of our "path-guided pushdown random walk" technique include point location, plane sweep, convex hulls, and Delaunay triangulation.
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.
Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing.
D. Eppstein, M. T. Goodrich, and S. Liu.
arXiv:2505.10789.
Proc. 33rd Annual European Symposium on Algorithms (ESA 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 351, 2025, pp. 69:1–69:17.In graphs of bounded bandwidth, the number of vertices per level of a breadth-first search tree is at most polylogarithmic, with the exponent of the polylogarithm both upper and lower bounded by functions of the bandwidth. This has applications to the Cuthull-McKee heuristic and reverse Cuthull-McKee heuristic in sparse numerical algebra, to reconstructing an unknown graph by shortest distance queries, and to drawing graphs as arc diagrams of small height.
Decremental greedy polygons and polyhedra without sharp angles.
D. Eppstein.
arXiv:2507.04538.
Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 85–91.For given elements and a quality function of an element in a subset, monotonically non-increasing with respect to removals of other elements, we can find the max-min-quality subset by a decremental greedy algorithm that repeatedly removes low-quality subsets. We apply this method to find the max-min-angle polygon for points in the plane, the max-min-weight cycle in a directed graph, and several generalizations of both problems.
Stabbing faces by a convex curve.
D. Eppstein.
arXiv:2508.17549.
33rd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 29:1–29:8.For each smooth convex curve \(C\), and each planar graph \(G\), there exists a straight-line drawing of \(G\) all of whose faces are crossed by \(C\). This result serves as a counterexample to an argument that universal point sets for planar graph drawing cannot be covered by few convex polygons.
String graph obstacles of high girth and of bounded degree.
M. Chudnovsky, D. Eppstein, and D. Fischer.
arXiv:2509.00278.
33rd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 24:1–24:18.String graphs, the intersection graphs of curves in the plane, are closed under induced minors (induced subgraphs of contractions), and were known to have infinitely many obstacles under the induced minor order, but these obstacles were very dense. We find an infinite class of obstacles that are nearly-planar (one edge away from being planar) but we prove that there are no subcubic obstacles of high girth. Recognizing string graphs is known to be NP-complete (unusually, the hard part of this result is proving that recognition belongs to NP); we use Courcelle's theorem to give a fixed-parameter tractable algorithm for recognizing subcubic string graphs, parameterized by treewidth.
Visualizing treewidth.
A. Chiu, T. Depian, D. Eppstein, M. T. Goodrich, and M. Nöllenburg.
arXiv:2508.19935.
33rd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 17:1–17:20.We experiment with metro-map style visualizations of tree decompositions of graphs. Here, the bags of a tree decomposition are visualized as stations on a metro system, and the vertices of a graph are visualized as metro lines passing through certain stations. Within each bag we display a drawing of the induced subgraph of the bag.
Bicriteria polygon aggregation with arbitrary shapes.
L. Blank, D. Eppstein, J.-H. Haunert, H. Haverkort, B. Kolbe, P. Mayer, P. Mutzel, A. Naumann, and J. Sauer.
arXiv:2507.11212.We consider a problem of shape aggregation in which we cluster a collection of disjoint regions in the plane by finding a collection of surrounding shapes, covering all the given regions and minimizing a linear combination of area and perimeter. The tradeoff between area and perimeter gives us a nested family of clusterings ranging from each given region forming its own cluster to a single cluster for all the regions. The cluster boundaries are straight line segments and circular arcs, leading to a discretization of the clustering problem that allows its optimal solution to be found in polynomial time by a transformation to network flow.