David Eppstein - Publications

2021

• NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs.
  D. Eppstein and V. V. Vazirani.
  arXiv:1802.00084.
  Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Phoenix, Arizona, 2019, pp. 23–30.
  SIAM J. Computing 50 (3): 1014–1033, 2021.

  We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.

  (Slides)

• Cubic planar graphs that cannot be drawn on few lines.
  D. Eppstein.
  arXiv:1903.05256.
  Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 32:1–32:15.
  J. Computational Geometry 12 (1): 178–197, 2021.
  

  We construct planar graphs whose straight drawings require a large number of lines (at least the cube root of the number of vertices) to cover all vertices. We also find series-parallel graphs and apex-trees that require a non-constant number of lines.

  (Slides)

• Bipartite and series-parallel graphs without planar Lombardi drawings.
  D. Eppstein.
  arXiv:1906.04401.
  Proc. 31st Canadian Conference on Computational Geometry, Edmonton, Canada, 2019, pp. 17–22.
  J. Graph Algorithms & Applications 25 (1): 549–562, 2021.

  Not every bipartite planar graph has a planar Lombardi drawing. Not every plane series parallel graph has a planar Lombardi drawing with the same embedding. The proof involves the properties of cycles of circular-arc-quadrilaterals all sharing the same two vertices, with equal and sharp vertex angles.

  (Slides)

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

• On the treewidth of Hanoi graphs.
  D. Eppstein, D. Frishberg, and W. Maxwell.
  arXiv:2005.00179.
  Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
  Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
  Theor. Comput. Sci. 906: 1–17, 2022.

  The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of n^p − 1.

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

• On polyhedral realization with isosceles triangles.
  D. Eppstein.
  arXiv:2009.00116.
  Graphs and Combinatorics 37 (4): 1247–1269, 2021.
  

  We find convex polyhedra with all faces triangular that cannot be realized with all faces isosceles, and new families of convex polyhedra with congruent isosceles-triangle faces.

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

  (Slides)

• Geometric dominating sets – A minimum version of the no-three-in-line problem.
  O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
  37th European Workshop on Computational Geometry (EuroCG 2021), pp. 17:1–17:7.
  arXiv:2203.13170.
  Comp. Geom. Theory & Applications 108: 101913, 2023 (special issue for EuroCG).
  

  We study how few points can be placed in a grid so that all remaining grid points are collinear with two of the placed points.

• 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 85: 1738–1753, 2023 (special issue for WADS 2021).
  

  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)

• Angles of arc-polygons and Lombardi drawings of cacti.
  D. Eppstein, D. Frishberg, and M. Osegueda.
  arXiv:2107.03615.
  Proc. 33rd Canadian Conference on Computational Geometry, 2021, pp. 56–64.
  Comp. Geom. Theory & Applications 112: 101982, 2023 (special issue for CCCG 2021).
  

  We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.

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

  (Slides)

• Multifold tiles of polyominoes and convex lattice polygons.
  K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
  23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
  Thai Journal of Mathematics 21 (4): 957–978, 2023.

  We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).

• Egyptian fractions with denominators from sequences closed under doubling.
  D. Eppstein.
  J. Integer Sequences 24: 21.8.8, 2021.
  arXiv:2109.12217.

  We prove that if a set of positive integers includes multiples of all integers, and is closed under multiplication by two, then its reciprocals can form Egyptian fractions for every rational number up to the sum of reciprocals of the set.

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

• The complexity of iterated reversible computation.
  D. Eppstein.
  arXiv:2112.11607.
  Invited talk at 15th Latin American Theoretical Informatics Symposium, Guanajuato, Mexico, November 2022.
  TheoretiCS 2: A10:1–A10:41, 2023.
  

  We study a class of problems involving computing a value \(f^{(n)}(x)\), the \(n\)th iterate of a function \(f\), for polynomial time bijections. We prove that these problems are complete for \(\mathsf{P}^{\mathsf{PSPACE}}\), and include hard problems in circuit complexity, graph algorithms, the simulation of one- and two-dimensional automata, and dynamical systems. We also provide a polynomial time algorithm for the special case where the bijection is an interval exchange transformation.