David Eppstein - Publications

Publications with Torsten Ueckerdt

• Convex-arc drawings of pseudolines.
  D. Eppstein, M. van Garderen, B. Speckmann, and T. Ueckerdt.
  21st Int. Symp. Graph Drawing (poster), Bordeaux, France, 2013.
  Springer, Lecture Notes in Comp. Sci. 8242, 2013, pp. 522–523.
  arXiv:1601.06865.
  

  We show that every outerplanar weak pseudoline arrangement (a collection of curves topologically equivalent to lines, each crossing at most once but possibly zero times, with all crossings belonging to an infinite face) can be straightened to a hyperbolic line arrangement. As a consequence such an arrangement can also be drawn in the Euclidean plane with each pseudoline represented as a convex piecewise-linear curve with at most two bends. In contrast, for arbitrary pseudoline arrangements, a linear number of bends is sufficient and sometimes necessary.

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

• On the complexity of embedding in graph products.
  T. Biedl, D. Eppstein, and T. Ueckerdt.
  arXiv:2303.17028.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.

  Row treewidth (embedding a graph as a subgraph of a strong product of a path with a low treewidth graph), row pathwidth, and row tree-depth are all NP-hard.

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

Semi-automatically filtered from a common source file.