David Eppstein - Publications

Publications with Sergio Cabello

• The Fibonacci dimension of a graph.
  S. Cabello, D. Eppstein, and S. Klavžar.
  IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.
  arXiv:0903.2507.
  Electronic J. Combinatorics 18(1), Paper P55, 2011.

  We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.

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

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

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