David Eppstein - Publications

2015

• Ramified rectilinear polygons: coordinatization by dendrons.
  H.-J. Bandelt, V. Chepoi, and D. Eppstein.
  arXiv:1005.1721.
  Disc. Comp. Geom. 54 (4): 771–797, 2015.
  

  We characterize the graphs that can be isometrically embedded into the Cartesian product of two trees (partial double dendrons), and the metric spaces obtained as the median complexes of these graphs. These spaces include the space of geodesic distance in axis-parallel polygons in the L₁ plane, hence the title. An algorithm based on lexicographic breadth-first search can be used to recognize partial double dendrons in linear time.

• Improved grid map layout by point set matching.
  D. Eppstein, M. van Kreveld, B. Speckmann, and F. Staals.
  28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, 2012.
  6th IEEE Pacific Visualization Conf. (PacificVis), Sydney, Australia, 2013.
  Int. J. Comput. Geom. Appl. 25 (2): 101–122, 2015.

  We study the problem of matching geographic regions to points in a regular grid, minimizing the distance between each region's centroid and the corresponding grid point, and preserving as much as possible the relative orientations between pairs of regions.

• Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets.
  G. Borradaile and D. Eppstein.
  arXiv:1206.2254.
  24th Canadian Conference on Computational Geometry (CCCG 2012), Prince Edward Island, Canada, 2012, pp. 311–316.
  Comp. Geom. Theory & Applications 49: 8–16, 2015 (special issue for CCCG 2012).

  When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

• Automated generation of linkage loop equations for planar 1-dof linkages, demonstrated up to 8-bar.
  B. E. Parrish, J. M. McCarthy, and D. Eppstein.
  Proc. ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Vol. 5A: 38th Mechanisms and Robotics Conference, Buffalo, New York, USA, August 17-20, 2014, paper no. DETC2014-35263.
  J. Mechanisms and Robotics 7 (1): 011006, 2015.

  This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.

  (eScholarship conference version – eScholarship journal version)

• Planar induced subgraphs of sparse graphs.
  G. Borradaile, D. Eppstein, and P. Zhu.
  arXiv:1408.5939.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 1–12.
  J. Graph Algorithms & Applications 19 (1): 281–297, 2015.

  We investigate the number of vertices that must be deleted from an arbitrary graph, in the worst case as a function of the number of edges, in order to planarize the remaining graph. We show that m/5.22 vertices are sufficient and m/(6 − o(1)) are necessary, and we also give bounds for the number of deletions needed to achieve certain subclasses of planar graphs.

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

• k-best enumeration.
  D. Eppstein.
  Encyclopedia of Algorithms (Ming-Yang Kao, ed.), Springer, added 2014.
  arXiv:1412.5075.
  Bull. EATCS 115, 2015.

  A brief survey of algorithms for finding the k shortest paths and related k-best enumeration problems. The arXiv/EATCS version is significantly longer and with more references than the Springer version.

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

  (Slides)

• Folding a paper strip to minimize thickness.
  E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.
  arXiv:1411.6371.
  9th International Workshop on Algorithms and Computation (WALCOM 2015), Dhaka, Bangladesh.
  Springer, Lecture Notes in Comp. Sci. 8973 (2015), pp. 113–124.
  Journal of Discrete Algorithms 36: 18–26, 2016 (special issue for WALCOM).
  

  If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.

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

• Simple recognition of Halin graphs and their generalizations.
  D. Eppstein.
  arXiv:1502.05334.
  J. Graph Algorithms & Applications 20 (2): 323–346, 2016.

  We describe and implement a simple linear time algorithm for recognizing Halin graphs based on two simplifications of triples of degree-three vertices in such graphs. Removing some auxiliary data from the algorithm causes it to recognize a broader class of graphs that we call the D3-reducible graphs. We study the properties of these graphs, showing that they share many properties with the Halin graphs.

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

  (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)

• Metric dimension parameterized by max leaf number.
  D. Eppstein.
  arXiv:1506.01749.
  J. Graph Algorithms & Applications 19 (1): 313–323, 2015.

  We prove that when a graph of bounded size has its edges subdivided to form a larger graph, it is still possible to find its metric dimension by a fixed-parameter tractable algorithm, parameterized by the pre-subdivision size of the graph.

• Folding polyominoes into (poly)cubes.
  O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.
  27th Canadian Conference on Computational Geometry, Kingston, Ontario, Canada, 2015, pp. 101–106.
  arXiv:1712.09317.
  Int. J. Comp. Geom. & Appl. 28 (3): 197–226, 2018.

  We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

• Structure of graphs with locally restricted crossings.
  V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.04380.
  23rd Int. Symp. Graph Drawing, Los Angeles, California, 2015.
  Springer, Lecture Notes in Comp. Sci. 9411 (2015), pp. 87–98.
  SIAM J. Discrete Math. 31 (2): 805–824, 2017.

  The Graph Drawing version used the alternative title "Genus, treewidth, and local crossing number". We prove tight bounds on the treewidth of graphs embedded on low-genus surfaces with few crossings per edge, and nearly tight bounds on the number of crossings per edge for graphs with a given number of edges embedded on low-genus surfaces.

  (Slides — local copy of final version)

• Track layouts, layered path decompositions, and leveled planarity.
  M. J. Bannister, W. E. Devanny, and V. Dujmović, D. Eppstein, and D. R. Wood.
  arXiv:1506.09145.
  24th Int. Symp. Graph Drawing, Athens, Greece, 2016.
  Springer, Lecture Notes in Comp. Sci. 9801 (2016), pp. 499–510.
  Algorithmica 81 (4): 1561–1583, 2019.

  We introduce the concept of a layered path decomposition, and show that the layered pathwidth can be used to characterize the leveled planar graphs. As a consequence we show that finding the minimum number of tracks in a track layout of a given graph is NP-complete. The GD version includes only the parts concerning track layout, and uses the title "Track Layout is Hard".

• Approximate greedy clustering and distance selection for graph metrics.
  D. Eppstein, S. Har-Peled, and A. Sidiropoulos.
  arXiv:1507.01555.
  J. Computational Geometry 11 (1): 629–652, 2020.

  We provide fast approximation algorithms for the farthest-first traversal of graph metrics.

• Rigid origami vertices: Conditions and forcing sets.
  Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.
  arXiv:1507.01644.
  J. Computational Geometry 7 (1): 171–184, 2016.

  We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.

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

• Treetopes and their graphs.
  D. Eppstein.
  arXiv:1510.03152.
  27th ACM-SIAM Symp. on Discrete Algorithms, Arlington, 2016, pp. 969–984.
  Discrete Comput. Geom. 64 (2), 259–289, 2020 (special issue for Branko Grünbaum).
  

  We describe a class of polytopes of varying dimensions, whose restriction to three dimensions is the class of roofless polyhedra (Halin graphs). We call these polytopes treetopes. We show that the four-dimensional treetopes are closely related to clustered planar graph drawings, and we use this connection to recognize the graphs of four-dimensional treetopes in polynomial time.

  (Slides)

• On the planar split thickness of graphs.
  D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.
  arXiv:1512.04839.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 403–415.
  Algorithmica 80 (3): 977–994 (special issue for LATIN), 2018.

  We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.

  (Slides)

• From discrepancy to majority.
  D. Eppstein and D. S. Hirschberg.
  arXiv:1512.06488.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
  Algorithmica 80 (4): 1278–1297, 2018.

  We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

  (Slides)