David Eppstein – Publications

Publications with Giordano Da Lozzo

• Square-contact representations of partial 2-trees and triconnected simply-nested graphs.
  G. Da Lozzo, W. E. Devanny, D. Eppstein, and T. Johnson.
  arXiv:1710.00426.
  Proc. 28th Int. Symp. Algorithms and Computation (ISAAC 2017), Phuket, Thailand, 2017.
  Leibniz International Proceedings in Informatics (LIPIcs) 92, pp. 24:1–24:16.

  We show that the K_1,1,3-free partial 2-trees and the Halin graphs other than K₄ can all be represented as proper contact graphs of squares in the plane. Among partial 2-trees and Halin graphs, these are exactly the ones that can be embedded without nonempty triangles, which form an obstacle to the existence of square contact representations. However the graph of a square antiprism has no such representation despite being embeddable without any nonempty triangles.

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