David Eppstein - Publications

Publications with Michael Kaufmann

• Universal point sets for planar graph drawings with circular arcs.
  P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.
  HAL-Inria open archive oai:hal.inria.fr:hal-00846953.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.
  J. Graph Algorithms and Applications 18 (3): 313–324, 2014.

  For every positive integer n, there exists a set of n points on a parabola, with the property that every n-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.

  (Slides)

• Contact graphs of circular arcs.
  M. J. Alam, D. Eppstein, M. Kaufmann, S. Kobourov, S. Pupyrev A. Schulz, and T. Ueckerdt.
  arXiv:1501.00318.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 1–13.

  We study the graphs formed by non-crossing circular arcs in the plane, having a vertex for each arc and an edge for each point where an arc endpoint touches the interior of another arc.

  (Slides)