2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – a3nm
    Commented Feb 19, 2023 at 21:54
  • $\begingroup$ I'll revise my note to point out this connection. Would you like me to acknowledge you for this? if so, how? Thanks again! $\endgroup$
    – a3nm
    Commented Feb 19, 2023 at 21:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – user67422
    Commented Feb 20, 2023 at 0:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.