David Eppstein - Publications

Publications with Giuseppe Liotta

• Selected open problems in graph drawing.
  F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.

  We survey a number of open problems in theoretical and applied graph drawing.

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