Publications with Michael T. Goodrich
Confluent drawings: visualizing non-planar diagrams in a planar way.
M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
arXiv:cs.CG/0212046.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
J. Graph Algorithms and Applications (special issue for GD'03) 9 (1): 31–52, 2005.We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.
Deterministic sampling and range counting in geometric data streams.
A. Bagchi, A. Chaudhary, D. Eppstein, and M. T. Goodrich.
arXiv:cs.CG/0307027.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 144–151.
ACM Trans. Algorithms 3(2):A16, 2007.We describe an efficient streaming-model construction of epsilon-nets and epsilon-approximations, and use it to find deterministic streaming-model approximation algorithms for iceberg range queries and for various robust statistics problems.
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.
Confluent layered drawings.
D. Eppstein, M. T. Goodrich, and J. Meng.
12th Int. Symp. Graph Drawing, New York, 2004.
Springer, Lecture Notes in Comp. Sci. 3383, 2004, pp. 184–194.
arXiv:cs.CG/0507051.
Algorithmica 47 (4): 439–452 (special issue for Graph Drawing), 2007.Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.
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.
The skip quadtree: a simple dynamic data structure for multidimensional data.
D. Eppstein, M. T. Goodrich, and J. Z. Sun.
21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296–305.
arXiv:cs.CG/0507049.
Int. J. Comp. Geom. & Appl. 18(1-2): 131–160, 2008.We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.
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.
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.
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.
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.
Space-efficient straggler identification in round-trip data streams via Newton's identities 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.
Approximate Topological Matching of Quadrilateral Meshes.
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008), Stony Brook, New York, pp. 83–92.
The Visual Computer 25 (8): 771–783, 2009.We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.
(Preprint)
Motorcycle graphs: canonical quad mesh partitioning.
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. 6th Symp. Geometry Processing, Copenhagen, Denmark, 2008.
Computer Graphics Forum 27 (5): 1477–1486, 2008.We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.
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.
Succinct greedy geometric routing using hyperbolic geometry.
D. Eppstein and M. T. Goodrich.
arXiv:0806.0341.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008
(under the different title "Succinct greedy graph drawing in the hyperbolic plane"),
Springer, Lecture Notes in Comp. Sci. 5417, 2009, pp. 14–25.
IEEE Transactions on Computing 60 (11): 1571–1580, 2011.Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.
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.
Linear-time algorithms for geometric graphs with sublinearly many crossings.
D. Eppstein, M. T. Goodrich, and D. Strash.
arXiv:0812.0893.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150–159.
SIAM J. Computing 39 (8): 3814–3829, 2010.If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.
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.
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.
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.
Drawing graphs in the plane with a prescribed outer face and polynomial area.
E. Chambers, D. Eppstein, M. T. Goodrich, and M. Löffler.
Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 129–140.
arXiv:1009.0088.
J. Graph Algorithms and Applications 16 (2): 243–259, 2012.Tutte's method of spring embeddings allows any triangulated planar graph to be drawn so that the outer face has any pre-specified convex shape, but it may place vertices exponentially close to each other. Alternative graph drawing methods provide polynomial-area straight line drawings but do not allow the outer face shape to be specified. We describe a drawing method that combines both properties: it has polynomial area, and can match any pre-specified shape of the outer face, even a shape in which some of the vertices have 180 degree angles. We apply our results to drawing polygonal schemas for graphs embedded on surfaces of positive genus.
Lombardi drawings of graphs.
C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 195–207.
arXiv:1009.0579.
Invited talk at 7th Dutch Computational Geometry Day, Eindhoven, the Netherlands, 2010.
J. Graph Algorithms and Applications 16 (1): 85–108, 2012 (special issue for GD 2010).In honor of artist Mark Lombardi, we define a Lombardi drawing to be a drawing of a graph in which the edges are drawn as circular arcs and at each vertex they are equally spaced around the vertex so as to achieve the best possible angular resolution. We describe algorithms for constructing Lombardi drawings of regular graphs, 2-degenerate graphs, graphs with rotational symmetry, and several types of planar graphs. A program for the rotationally symmetric case, the Lombardi Spirograph, is available online.
Drawing trees with perfect angular resolution and polynomial area.
C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Nöllenburg.
Proc. 18th Int. Symp. Graph Drawing, Konstanz, Germany, 2010.
Springer, Lecture Notes in Comp. Sci. 6502, 2011, pp. 183–194.
arXiv:1009.0581.
Discrete Comput. Geom. 49 (2): 157–182, 2013.We consider balloon drawings of trees, in which each subtree of the root is drawn recursively within a disk, and these disks are arranged radially around the root, with the edges at each node spaced equally around the node so as to achieve the best possible angular resolution. If we are allowed to permute the children of each node, then we show that a drawing of this type can be made in which all edges are straight line segments and the area of the drawing is a polynomial multiple of the shortest edge length. However, if the child ordering is prescribed, exponential area might be necessary. We show that, if we relax the requirement of straight line edges and draw the edges as circular arcs (a style we call Lombardi drawing) then even with a prescribed child ordering we can achieve polynomial area.
Extended dynamic subgraph statistics using h-index parameterized data structures.
D. Eppstein, M. T. Goodrich, D. Strash, and L. Trott.
Proc. 4th Int. Conf. on Combinatorial Optimization and Applications (COCOA 2010), Hawaii, 2010.
Springer, Lecture Notes in Comp. Sci. 6508, 2010, pp. 128–141.
arXiv:1009.0783.
Theor. Comput. Sci. 447: 44–52, 2012 (special issue for COCOA 2010).An earlier paper with Spiro at WADS 2009 provided dynamic graph algorithms for counting how many copies of each possible type of subgraph there are in a larger undirected graph, when the subgraphs have at most three vertices. This paper extends the method to directed graphs and to larger numbers of vertices per subgraph.
Privacy-preserving data-oblivious geometric algorithms for geographic data.
D. Eppstein, M. T. Goodrich, and R. Tamassia.
Proc. 18th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2010), San Jose, California, pp. 13–22.
arXiv:1009.1904.An algorithm is data-oblivious if the memory access patterns it makes depend only on the input size and not on the actual input values; data-oblivious algorithms are an important building block of cryptographic protocols that allow algorithmic tasks to be solved by parties who each have some subset of the input data that they do not wish to reveal. We show how to solve several basic geometric problems data-obliviously, including construction of convex hulls, quadtrees, and well-separated pair decompositions, and computation of closest pairs and all nearest neighbors.
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.
Category-based routing in social networks: membership dimension and the small-world phenomenon.
D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott.
Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
International Conference on Computational Aspects of Social Networks (CASoN 2011), Salamanca, Spain, October 2011.
arXiv:1108.4675.
Theor. Comput. Sci. 514: 96–104, 2013. (Special issue on Graph Algorithms and Applications: in Honor of Professor Giorgio Ausiello)We investigate greedy routing schemes for social networks, in which participants know categorical information about some other participants and use it to guide message delivery by forwarding messages to neighbors that have more categories in common with the eventual destination. We define the membership dimension of such a scheme to be the maximum number of categories that any individual belongs to, a natural measure of the cognitive load of greedy routing on its participants. And we show that membership dimension is closely related to the small world phenomenon: a social network can be given a category system with polylogarithmic membership dimension that supports greedy routing if, and only if, the network has polylogarithmic diameter.
Planar and poly-arc Lombardi drawings.
C. Duncan, D. Eppstein, M. T. Goodrich, S. Kobourov, and M. Löffler, and M. Nöllenburg.
Proc. 19th Int. Symp. Graph Drawing, Eindhoven, The Netherlands, 2011.
Springer, Lecture Notes in Comp. Sci. 7034, 2012, pp. 308–319.
arXiv:1109.0345.
J. Computational Geometry 9 (1): 328–355, 2018.We extend Lombardi drawing (in which each edge is a circular arc and the edges incident to a vertex must be equally spaced around it) to drawings in which edges are composed of multiple arcs, and we investigate the graphs that can be drawn in this more relaxed framework.
Privacy-enhanced methods for comparing compressed DNA sequences.
D. Eppstein, M. T. Goodrich, and P. Baldi.
arXiv:1107.3593.
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.
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.
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.
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.
The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings.
M. J. Bannister, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
arXiv:1408.1422.
22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014
Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 149–161.
J. Graph Algorithms & Applications 19 (2): 619–656, 2015 (special issue for GD'14).We show that many standard graph drawing methods have algebraic solutions described by polynomials that can have unsolvable Galois groups, and that can have Galois groups whose order is divisible by large prime numbers. As a consequence certain models of exact algebraic computation are unable to construct these drawings.
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.
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.
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.
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.
Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
arXiv:1804.09411
Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
J. Computational Geometry 11 (1): 26–59, 2020.The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.
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.
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.
C-planarity testing of embedded clustered graphs with bounded dual carving-width.
G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
arXiv:1910.02057.
Proc. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Munich, Germany, 2019 (best paper award).
Leibniz International Proceedings in Informatics (LIPIcs) 148, 2019, pp. 9:1–9:17.
Algorithmica 83 (8): 2471–2502, 2021 (special issue for IPEC 2019).We show that finding clustered planar drawings can be done in fixed-parameter-tractable time, depending only on a single width parameter of the input clustered graph.
Tracking paths in planar graphs.
D. Eppstein, M. T. Goodrich, P. Matias, and J. A. Liu.
arXiv:1908.05445.
Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 54:1–54:17.A tracking set for a given graph, with designated start and destination vertices, is a set of vertices such that any path from start to destination is determined by the subsequence of its vertices that belong to the tracking set. We show that finding the smallest tracking set is NP-hard but has a constant factor approximation, and can be solved exactly in fixed-parameter-tractable time for graphs of bounded width.
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.
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.
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.
Entropy-bounded computational geometry made easier and sensitive to sortedness.
D. Eppstein, M. T. Goodrich, A. M. Illickan, and C. A. To.
arXiv:2508.20489.
Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 53–61.We define a notion of structural entropy of point sets under which a set has low entropy when it can be covered by few disjoint triangles that are either entirely under the hull of the input or presorted, and show that we can find the hull in time sensitive to this entropy. Generalizations of the same technique apply to geometric maxima, lower envelopes, and visibility polygons.
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.