David Eppstein – Publications

Publications with Siddhartha Gupta

• Crossing patterns in nonplanar road networks.
  D. Eppstein and S. Gupta.
  arXiv:1709.06113.
  Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 40:1–40:9.

  We show that, although an individual edge in a road network can have many crossings, real-world road networks have the property that the crossing graph of their edges is sparse. We prove that networks with this property are themselves sparse and have small separators, allowing many fast algorithms to be generalized from planar graphs to these networks.

• Subexponential-time and FPT algorithms for embedded flat clustered planarity.
  G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
  arXiv:1803.05465
  Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), Lübbenau, Germany.
  Springer, Lecture Notes in Comp. Sci. 11159 (2018), pp. 111–124.

  Clustered planarity is the problem of simultaneously drawing a planar graph and a clustering of its vertices (as Jordan curves surrounding the cluster) with no unnecessary crossings between edges or cluster boundaries; it remains unknown whether it can be solved in polynomial time. We provide parameterized and subexponential exact algorithms for the case where the planar embedding is fixed and the clusters form a partition of the vertices.

• C-planarity testing of embedded clustered graphs with bounded dual carving-width.
  G. Da Lozzo, D. Eppstein, M. T. Goodrich, and S. Gupta.
  arXiv:1910.02057.
  Proc. 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Munich, Germany, 2019 (best paper award).
  Leibniz International Proceedings in Informatics (LIPIcs) 148, 2019, pp. 9:1–9:17.
  Algorithmica 83 (8): 2471–2502, 2021 (special issue for IPEC 2019).

  We show that finding clustered planar drawings can be done in fixed-parameter-tractable time, depending only on a single width parameter of the input clustered graph.

• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes.
  D. Eppstein, E. Havvaei, and S. Gupta.
  arXiv:2101.09918.
  Proc. 23rd International Symposium on Fundamentals of Computation Theory, 2021.
  Springer, Lecture Notes in Comp. Sci. 12867 (2021), pp. 217–229.

  We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).