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, to appear.

  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.

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.