The topic of graph em­bed­ding (es­pe­cially in graphs with a lot of struc­ture, such as grids) has been stud­ied for decades, mo­ti­vated by ap­pli­ca­tions in VLSI de­sign and graph draw­ing. Re­cently, the in­ter­est has been re­vived due to the graph prod­uct struc­ture the­o­rem, which states that any pla­nar graph G can be em­bed­ded in the strong prod­uct of a path with a graph H of small treewidth. This raises the nat­ural ques­tion: what is the small­est treewidth that H could have? In this talk, we in­ves­ti­gate this ques­tion, and show that com­put­ing this so-called row treewidth of a graph G is NP-hard. We also prove NP-hard­ness of com­put­ing some other pa­ra­me­ters that re­late to em­bed­ding in graph prod­ucts. Fi­nally we con­sider spe­cial cases of graph G, such as being pla­nar, hav­ing small path­width, hav­ing small max­i­mum de­gree, etc. Under most of these re­stric­tions com­put­ing the row treewidth re­mains NP-hard, but we give some pos­i­tive re­sults as well. (Joint work with David Epp­stein and Torsten Ueck­erdt.)