<p>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 <span class="math-container">$O(n)\times O(n)$</span> grid and such an embedding can be found in linear time <a href="https://ieeexplore.ieee.org/document/34669" rel="nofollow noreferrer">R. Tamassia and I. G. Tollis. Planar grid embedding in linear time, 1989</a>). 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.</p>

CC BY-SA 4.0
2023-02-19T21:54:17.457Z
Thanks for this very insightful answer! I wasn't aware of this paper by Tamassia and Tollis and this line of work giving algorithms for orthogonal embeddings. Indeed it is clear that these embeddings in grids (which are apparently a special kind of topological embeddings) can afterwards be converted to embeddings in a wall graph, giving the result I need with a better bound (but arguably a less self-contained proof). I had instead found the paper by Schnyder which talks of "straight line embeddings" where the same is not clear.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-19T21:54:44.200Z
I'll revise my note to point out this connection. Would you like me to acknowledge you for this? if so, how? Thanks again!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-20T00:21:43.040Z
I wouldn't be surprised if for the special case of degree-3 graphs there is an easier and more direct way to find an embedding algorithmically. Starting with an st-ordering of the graph may be useful. No need for acknowledgment, but thanks for the offer.
user67422
CC BY-SA 4.0
2023-02-19T17:19:00.443Z
2023-02-19T17:19:00.443Z
user67422
<p>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 <a href="https://en.wikipedia.org/wiki/Graph_minor#Topological_minors" rel="nofollow noreferrer">topological minor</a>, and for this reason restrict the input planar graph to have maximal degree 3 (see <a href="https://cstheory.stackexchange.com/questions/7290/citation-showing-minors-are-topological-minors-for-subcubic-graphs">this question</a>). The graph family in which I embed are the so-called wall graphs, which are a high-treewidth degree-3 variant of <a href="https://en.wikipedia.org/wiki/Lattice_graph" rel="nofollow noreferrer">grid graphs</a> occurring for instance in <a href="https://www.sciencedirect.com/science/article/pii/S0022000010001303" rel="nofollow noreferrer">this paper</a>.</p>
<p>I have worked out a proof of the result I needed in <a href="https://arxiv.org/abs/2302.03461" rel="nofollow noreferrer">this note</a>. The result is the following: <strong>given as input a degree-3 planar graph <span class="math-container">$G$</span>, one can compute in polynomial time a wall graph <span class="math-container">$H$</span> and a topological embedding of <span class="math-container">$G$</span> in <span class="math-container">$H$</span></strong>. 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...).</p>
<p>My question is: <strong>is this result, or a similar result, known in the literature?</strong> 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.</p>

<reference-request><graph-theory><planar-graphs><graph-minor>
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
Antoine Amarilli 'a3nm'
# Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

(Asked by: username_0 on 2023-02-16)

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](https://en.wikipedia.org/wiki/Graph_minor#Topological_minors), and for this reason restrict the input planar graph to have maximal degree 3 (see [this question](https://cstheory.stackexchange.com/questions/7290/citation-showing-minors-are-topological-minors-for-subcubic-graphs)). The graph family in which I embed are the so-called wall graphs, which are a high-treewidth degree-3 variant of [grid graphs](https://en.wikipedia.org/wiki/Lattice_graph) occurring for instance in [this paper](https://www.sciencedirect.com/science/article/pii/S0022000010001303).

I have worked out a proof of the result I needed in [this note](https://arxiv.org/abs/2302.03461). 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.

**Tags:** reference-request, graph-theory, planar-graphs, graph-minor


---

## 1 answers

### Answer by username_1 on 2023-02-19. Score: 3 | Accepted answer

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](https://ieeexplore.ieee.org/document/34669)). 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.

> **Comments:**
> **username_0**: Thanks for this very insightful answer! I wasn't aware of this paper by Tamassia and Tollis and this line of work giving algorithms for orthogonal embeddings. Indeed it is clear that these embeddings in grids (which are apparently a special kind of topological embeddings) can afterwards be converted to embeddings in a wall graph, giving the result I need with a better bound (but arguably a less self-contained proof). I had instead found the paper by Schnyder which talks of "straight line embeddings" where the same is not clear.  
> **username_0**: I'll revise my note to point out this connection. Would you like me to acknowledge you for this? if so, how? Thanks again!  
> **username_1**: I wouldn't be surprised if for the special case of degree-3 graphs there is an easier and more direct way to find an embedding algorithmically. Starting with an st-ordering of the graph may be useful. No need for acknowledgment, but thanks for the offer.  

---

