On the Complexity of Embedding in Graph Products

Authors

DOI:

https://doi.org/10.57717/cgt.v4i2.56

Abstract

Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph G in a host graph that is the strong product of a path P with a graph H that satisfies some properties, such as having small treewidth, pathwidth or treedepth. We show that this is NP-complete, even under numerous restrictions on both G and H. In particular, computing the row pathwidth and the row treedepth is NP-hard even for a tree of small pathwidth, while computing the row treewidth is NP-hard even for series-parallel graphs.

Downloads

Published

2025-05-21

How to Cite

Biedl, T., Eppstein, D., & Ueckerdt, T. (2025). On the Complexity of Embedding in Graph Products. Computing in Geometry and Topology, 4(2), 5:1–5:18. https://doi.org/10.57717/cgt.v4i2.56

Issue

Section

Original Research Articles

Categories