David Eppstein – Publications

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.
Computing in Geometry and Topology 4 (2): 5:1–5:18, 2025, doi:10.57717/cgt.v4i2.56.

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 \(\mathsf{NP}\)-hard.

(Blog post: Logic engines and product graphs)