David Eppstein - Publications

2019

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

• Covering many points with a small-area box.
  M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.
  arXiv:1612.02149.
  J. Computational Geometry 10 (1): 207–222, 2019.
  

  We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.

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

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

• Realization and connectivity of the graphs of origami flat foldings.
  D. Eppstein.
  arXiv:1808.06013.
  Proc. 26th Int. Symp. Graph Drawing, Barcelona, 2018.
  Springer, Lecture Notes in Comp. Sci. 11282 (2018), pp. 541–554.
  J. Computational Geometry 10 (1): 257–280, 2019.

  If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.

  (Slides)

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

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

• Counting polygon triangulations is hard.
  D. Eppstein.
  arXiv:1903.04737.
  Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 33:1–33:17.
  Discrete Comput. Geom. 64 (4): 1210–1234, 2020 (special issue for SoCG 2019).

  Given a polygon with holes, it is #P-complete to determine how many triangulations it has.

  (UCLA seminar talk slides — SoCG slides)

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

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

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

  (WADS slides – ICGT 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.

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

• Ununfoldable Polyhedra with 6 Vertices or 6 Faces.
  H. A. Akitaya, E. Demaine, D. Eppstein, T. Tachi, and R. Uehara.
  22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Tokyo, Japan, 2019, pp. 27–28.
  Comp. Geom. Theory & Applications 103: 101857, 2022.
  

  We find a (nonconvex, but topologically equivalent to convex) polyhedron with seven vertices and six faces that cannot be unfolded to a flat polygon by cutting along its edges. Both the number of vertices and the number of faces are the minimum possible. The JCDCG³ version used the title "Minimal ununfoldable polyhedron".

• Some polycubes have no edge-unzipping.
  E. Demaine, M. Demaine, D. Eppstein, and J. O'Rourke.
  arXiv:1907.08433.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 101–105.
  Geombinatorics 31 (3): 101–109, 2022.
  

  We find polycubes that cannot be cut along a simple path through their vertices and edges and unfolded to form a flat polygon in the plane.

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

• Existence and hardness of conveyor belts.
  M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
  arXiv:1908.07668.
  Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.

  A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.

• Face flips in origami tessellations.
  H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
  arXiv:1910.05667.
  J. Computational Geometry 11 (1): 397–417, 2020.

  We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.