# David Eppstein - Publications

## Worksh. Algorithms and Data Structures (WADS)

I was on the program committee for the 5th Workshop, 1997 and the 10th Workshop, 2007.

• Offline algorithms for dynamic minimum spanning tree problems.
D. Eppstein.
2nd Worksh. Algorithms and Data Structures, Ottawa, Canada, 1991.
Springer, Lecture Notes in Comp. Sci. 519, 1991, pp. 392–399.
Tech. Rep. 92-04, ICS, UCI, 1992.
J. Algorithms 17: 237–250, 1994.

Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time O(log2 n) for the Euclidean metric and O(log n log log n) for the rectilinear metric.

• Parallel construction of quadtrees and quality triangulations.
M. Bern, D. Eppstein, and S.-H. Teng.
3rd Worksh. Algorithms and Data Structures, Montreal, 1993.
Springer, Lecture Notes in Comp. Sci. 709, 1993, pp. 188–199.
Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.
Int. J. Comp. Geom. & Appl. 9 (6): 517–532, 1999.

A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.

• 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).

• Small maximal independent sets and faster exact graph coloring.
D. Eppstein.
arXiv:cs.DS/0011009.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 462–470.
J. Graph Algorithms and Applications (special issue for WADS'01) 7 (2): 131–140, 2003.

We show that any graph can be colored in time O(2.415n), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.

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

• The traveling salesman problem for cubic graphs.
D. Eppstein.
arXiv:cs.DS/0302030.
8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
Springer, Lecture Notes in Comp. Sci. 2748, 2003, pp. 307–318. J. Graph Algorithms and Applications 11 (1): 61–81, 2007.

We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.

• Improved combinatorial group testing for real-world problem sizes.
D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
Springer, Lecture Notes in Comp. Sci. 3608, 2005, pp. 86–98.
arXiv:cs.DS/0505048.
SIAM J. Computing 36 (5): 1360–1375, 2007.

We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.

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

• Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 637–648.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.

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

• The h-index of a graph and its application to dynamic subgraph statistics.
D. Eppstein and E. S. Spiro.
arXiv:0904.3741.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 278–289.
J. Graph Algorithms and Applications 16 (2): 543–567, 2012.

We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.

(Slides)

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

(Slides)

• Orientation-constrained rectangular layouts.
D. Eppstein and E. Mumford.
arXiv:0904.4312.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 266–277.

We show how to find a stylized map in which regions have been replaced by rectangles, preserving adjacencies between regions, with constraints on the orientations of adjacencies between regions. For an arbitrary dual graph representing a set of adjacencies, and an arbitrary set of orientation constraints, we can determine whether there exists a rectangular map satisfying those constraints in polynomial time. The algorithm is based on a representation of the set of all layouts for a given dual graph as a distributive lattice, and on Birkhoff's representation theorem for distributive lattices.

Merged with "Area-universal rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".

(Slides)

• Optimal embedding into star metrics.
D. Eppstein and K. Wortman.
arXiv:0905.0283.
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.

(Slides)

K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira.
arXiv:1105.0398.
12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 159–170.
J. Computational Geometry 7 (1): 100–122, 2016.

We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.

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

• Combinatorial pair testing: distinguishing workers from slackers.
D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
arXiv:1305.0110.
13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario.
Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 316–327.

We study the problem of distinguishing workers (people who complete their assigned tasks) from slackers (people who do not contribute towards the completion of their tasks) by grouping people in pairs and assigning a task to each group.

• Parameterized complexity of 1-planarity.
M. J. Bannister, S. Cabello, and D. Eppstein.
arXiv:1304.5591.
13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario
Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 97–108.
J. Graph Algorithms and Applications 22 (1): 23–49, 2018. (Special issue on Graph Drawing Beyond Planarity.)

We show that testing whether a graph is 1-planar (drawable with at most one crossing per edge) may be performed in polynomial and fixed-parameter tractable time for graphs of bounded circuit rank, vertex cover number, or tree-depth. However, it is NP-complete for graphs of bounded treewidth, pathwidth, or bandwidth.

(Slides)

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

(Slides)

• Rooted cycle bases.
D. Eppstein, J. M. McCarthy, and B. E. Parrish.
arXiv:1504.04931.
14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 339–350.
J. Graph Algorithms & Applications 21 (4): 663–686, 2017.

We consider the problem of finding a cycle basis for a graph in which all basis cycles contain a specified edge. We characterize the graphs having such a basis in terms of their vertex connectivity, we show that the minimum weight cycle basis with this constraint can be found in polynomial time and is weakly fundamental, and we show that finding a fundamental cycle basis with this constraint is NP-hard but fixed-parameter tractable.

(Slides)

• The parametric closure problem.
D. Eppstein.
arXiv:1504.04073.
14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 327–338.
ACM Trans. Algorithms 14 (1): Article 2, 2018.

We consider the minimum weight closure problem for a partially ordered set whose elements have weights that vary linearly as a function of a parameter. For several important classes of partial orders the number of changes to the optimal solution as the parameter varies is near-linear, and the sequence of optimal solutions can be found in near-linear time.

(Slides)

• Maximum plane trees in multipartite geometric graphs.
A. Biniaz, P. Bose, J.-L. De Carufel, K. Crosbie, D. Eppstein, A. Maheshwari, M. Smid.
15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.
Springer, Lecture Notes in Comp. Sci. (2017), pp. 193–204.
Algorithmica 81 (4): 1512–1534, 2019.

We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.

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

(Slides)

• A stronger lower bound on parametric minimum spanning trees.
D. Eppstein.
arXiv:2105.05371.
17th Algorithms and Data Structures Symp. (WADS 2021).
Springer, Lecture Notes in Comp. Sci. 12808 (2021), pp. 343–356.
Algorithmica, Special issue for WADS 2021, to appear.

There exist graphs with edges labeled by linear real functions, such that the number of different minimum spanning trees obtained for different choices of the function argument is $$\Omega(m\log n)$$.

(Slides)

Semi-automatically filtered from a common source file.