David Eppstein – Publications

Publications with Maria Chudnovsky

• String graph obstacles of high girth and of bounded degree.
  M. Chudnovsky, D. Eppstein, and D. Fischer.
  arXiv:2509.00278.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 24:1–24:18.

  String graphs, the intersection graphs of curves in the plane, are closed under induced minors (induced subgraphs of contractions), and were known to have infinitely many obstacles under the induced minor order, but these obstacles were very dense. We find an infinite class of obstacles that are nearly-planar (one edge away from being planar) but we prove that there are no subcubic obstacles of high girth. Recognizing string graphs is known to be NP-complete (unusually, the hard part of this result is proving that recognition belongs to NP); we use Courcelle's theorem to give a fixed-parameter tractable algorithm for recognizing subcubic string graphs, parameterized by treewidth.