David Eppstein - Publications

Publications with Philipp Kindermann

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