2023/03/29 by Biedl, Therese, Eppstein, David, Ueckerdt, Torsten
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2303.17028
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 tree depth. We show that this is NP-hard, 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.