The topic of graph embedding (especially in graphs with a lot of structure, such as grids) has been studied for decades, motivated by applications in VLSI design and graph drawing. Recently, the interest has been revived due to the graph product structure theorem, which states that any planar graph G can be embedded in the strong product of a path with a graph H of small treewidth. This raises the natural question: what is the smallest treewidth that H could have? In this talk, we investigate this question, and show that computing this so-called row treewidth of a graph G is NP-hard. We also prove NP-hardness of computing some other parameters that relate to embedding in graph products. Finally we consider special cases of graph G, such as being planar, having small pathwidth, having small maximum degree, etc. Under most of these restrictions computing the row treewidth remains NP-hard, but we give some positive results as well. (Joint work with David Eppstein and Torsten Ueckerdt.)