Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

Question

For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological minor, and for this reason restrict the input planar graph to have maximal degree 3 (see this question). The graph family in which I embed are the so-called wall graphs, which are a high-treewidth degree-3 variant of grid graphs occurring for instance in this paper.

I have worked out a proof of the result I needed in this note. The result is the following: given as input a degree-3 planar graph $G$, one can compute in polynomial time a wall graph $H$ and a topological embedding of $G$ in $H$. The proof is by constructing in linear time an embedding of the planar graph with points having integer coordinates, using existing results by Schnyder, and Chrobak and Payne. Then it is not surprising that the drawing can be adjusted to a topological embedding, but working out the details proved out a bit tedious (probably I didn't take the most efficient route...).

My question is: is this result, or a similar result, known in the literature? I am wondering if it is just folklore that one can do this, or whether a result of this kind had already been stated or sketched somewhere.

Answer 1

I don't know whether this has been explicitly stated anywhere, but it follows from known results. Every planar graph is a minor of a $O(n)\times O(n)$ grid and such an embedding can be found in linear time R. Tamassia and I. G. Tollis. Planar grid embedding in linear time, 1989). In turn every grid is a minor of a wall (contracting pairs of neighboring points of the wall results in a grid). But for graphs of degree at most 3 being a minor is equivalent to being a topological minor, so every planar graph of degree at most 3 is a topological minor of a wall. This is quite constructive, and the constants are small.