LTCI, Télécom Paris, Institut Polytechnique de Paris, France and
https://a3nm.net/a3nm@a3nm.nethttps://orcid.org/0000-0002-7977-4441 Antoine
Amarilli [500]Mathematics of computing Discrete mathematics Graph theory

# Degree-3 planar graphs as topological minors of wall graphs in polynomial
time

Antoine Amarilli

###### Abstract

In this note, we give a proof of the fact that we can efficiently find
degree-3 planar graphs as topological minors of sufficiently large wall
graphs. The result is needed as an intermediate step to fix a proof in my PhD
thesis [1].

###### keywords:

Planar graph, topological minor, wall graph

##  1 Introduction and related work

In this note, we explain how, given a degree-3 planar graph, we can find it as
a topological minor of a wall graph, and do so efficiently, i.e., in
polynomial time. This result is needed as an intermediate step to fix a proof
in my PhD thesis [1]. Here is the formal statement of the result:

######  Theorem 1.1.

Given as input any degree-3 planar graph $G$ with $n$ vertices, we can compute
in time $O(n^{10})$ a wall graph $H$ of size $O(n^{4})$ by $O(n^{4})$ and an
embedding of $G$ as a topological minor of $H$.

Note that, in this result, we make no effort to optimize the degree of the
polynomial.

The proof presented here uses the well-known fact [6, 3] that planar graphs
can be drawn in linear time on a grid with integer coordinates. Specifically,
it works by starting from the drawing and adjusting it to obtain the
embedding.

### Related work.

An alternative route to show Theorem 1.1 was pointed out to us in [8] after we
posted a first version of this note. Specifically, it is shown in [7] that we
can embed an input planar graph of maximal degree 4 into a grid in linear
time, and the _grid embedding_ computed in [7] is a topological embedding
(satisfying additional properties). The embedding can then be converted to a
topological embedding into a wall graph, thanks to the fact that the input
graph is degree-3. This proof method is different from the one which we
present in this note; further, it would achieve a better bound, and is
arguably simpler.

Similar results to Theorem 1.1 are already known to embed planar graphs as
minors of grid graphs [5, Result 1.5], but we are not aware of a discussion of
the complexity of this process. In particular, the proof in [5] does not seem
easy to adapt to a polynomial-time process, as it involves, e.g., the
computation of Hamiltonian circuits.

Theorem 1.1 is not related to the celebrated theorem by Chekuri and Chuzhoy
[2], which shows that we can embed a grid in any graph with sufficiently large
but polynomial treewidth. In our result, the graph that we embed is an
arbitrary planar degree-3 graph, but importantly the target of the embedding
is always a wall graph. This is why we are also able to show a deterministic
PTIME bound, whereas the algorithm of [2] runs in randomized PTIME.

### Acknowledgements.

I am grateful to Pierre Bourhis, Mikaël Monet, and Pierre Senellart for
discussions about the problem, in particular I warmly thank Mikaël Monet for
proofreading the note in detail, identifying some problems, and discussing
possible solutions.

##  2 Preliminaries and result statement

Figure 1: The $(6,8)$-wall

An (undirected) _graph_ $G=(V,E)$ consists of a set of _vertices_ $V$ and a
set of _edges_ $E$ which are pairs of distinct vertices that are said to be
_adjacent_. The graph is _degree-3_ if the _degree_ of each vertex, i.e., the
number of edges in which it appears, is at most $3$. The graph is _planar_ if
it can be drawn on the plane without edge crossings. A _path_ connecting $u\in
V$ and $v\in V$ in $G$ is a sequence of vertices $u=w_{1},\ldots,w_{n}=v$ such
that $w_{i}$ and $w_{i+1}$ are adjacent for all $1\leq i\leq n$. The _inner
vertices_ of the path are $w_{2},\ldots,w_{n-1}$: there may be none if the
_length_ $n$ of the path is $0$ (i.e., $u=v$) or $1$ (i.e., $u$ and $v$ are
adjacent and the path directly takes that edge).

We define _wall graphs_ following [4]. For integers $r$ and $s$, the _$(r,s)$
-wall_ is the graph $W_{r,s}$ with vertices $\\{(i,j)\mid 1\leq i\leq r,1\leq
j\leq s\\}$ and edges $\\{\\{(i,j),(i,j+1)\\}\mid 1\leq i\leq r,1\leq j<s\\}$
and $\\{\\{(i,j),(i+(-1)^{i+j},j)\mid 1\leq i<r,1\leq j\leq s\\}$. An example
wall graph is given on Figure 1. Note that wall graphs are always degree-3 and
planar.

A _(topological) embedding_ of a graph $G=(V,E)$ into a graph
$H=(V^{\prime},E^{\prime})$ consists of an injective function $f\colon V\to
V^{\prime}$ and a function $g$ mapping each edge $\\{u,v\\}$ of $E$ to a path
$g(\\{u,v\\})$ in $H$ connecting $f(u)$ and $f(v)$ such that all these paths
are vertex-disjoint, i.e., for any two edges $\\{u,v\\}$ and
$\\{u^{\prime},v^{\prime}\\}$ of $E$, the set of inner vertices of the paths
$g(\\{u,v\\})$ and $g(\\{u^{\prime},v^{\prime}\\})$ are disjoint.

Our goal is to show Theorem 1.1. The proof proceeds in three steps. Some of
the details are a bit tedious, and the goal of this note is to make them
precise, but the overall strategy is rather simple.

First, we use the result of [6] to obtain in linear time a drawing of the
input graph with integer coordinates. The idea will be to convert this to an
embedding in a sufficiently large wall graph, by scaling up the drawing. We
also show some geometric lemmas on the drawing to bound how close the elements
of the drawing can be: how close can a vertex be to a segment to which it does
not belong, and how close two segments sharing a common endpoint can be when
they are sufficiently far away from the common endpoint.

Second, we explain how edges can be translated to paths in the wall graph, by
showing that any straight line between points with integer coordinates can be
“approximated” by a path in a wall graph which “stays close” to the line.

Third, we use the approximate paths to transform the drawing of the graph into
something that resembles a topological embedding except that the paths may
overlap close to their endpoints.

Fourth, we explain how to modify the embedding close to the vertices to fix
this problem.

##  3 Drawing the input graph $G$ and showing lemmas about the drawing

Given the input graph $G=(V,E)$, let $n$ be its number of vertices. The
problem is trivial if $n\leq 2$, so we assume $n\geq 3$. We know by the work
of Schnyder [6] that we can compute in linear time a _straight line embedding_
of $G$ in the $n-2$ by $n-2$ grid. This implies that we have an injective
_drawing function_ $\delta\colon V\to\\{0,\ldots,n-1\\}^{2}$ mapping each
vertex $u\in V$ to a point with integer coordinates in this range, so that the
edges do not cross, i.e., for any two edges $e=\\{u,v\\}$ and
$e^{\prime}=\\{u^{\prime},v^{\prime}\\}\in E$ with $e\neq e^{\prime}$, the
segments $[\delta(u),\delta(v)]$ and $[\delta(u^{\prime}),\delta(v^{\prime})]$
do not cross (except that they may share the same endpoints if some vertices
among $u$, $v$, $u^{\prime}$, and $v^{\prime}$ are equal).

We will want to replace the segments of the drawing by paths in a suitable
wall graph. To do this and ensure that the paths do not intersect, it will be
important to understand some properties of the drawing. First, we must
understand how close a segment between points with integer coordinates can
pass by another point with integer coordinates which is not on the segment.
For this, we show a lemma:

$p$$r$$q$ (a) Situation of Lemma 3.1. The point of the lemma is to give a
lower bound on the distance between $q$ and the segment $[p,r]$ (in orange)

(b) Argument used in the proof of Lemma 3.1. The orange area corresponds to
the point by which a segment cannot pass, extending to length $1/n$ on each
side of the point. The dashed blue line is the closest that the segment may
pass, and the distance bound in thick blue is the one shown in the lemma,
namely, $1/(\sqrt{2}n)$

Figure 2: Illustrations for Lemma 3.1

######  Lemma 3.1.

Let $p,q,r$ be pairwise distinct points with integer coordinates between $0$
and $n-1$. Assume that the point $q$ is not on the segment $[p,r]$. Then the
distance between $q$ and the segment $[p,r]$ is at least
$\frac{1}{\sqrt{2}n}$.

The lemma is illustrated as Figure 2(a).

######  Proof 3.2.

If the segment is parallel to one of the axes, then the result is trivial
because its distance to points with integer coordinates not in the segment is
clearly at least $1$, hence at least $\frac{1}{\sqrt{2}n}$. Hence, we assume
that the segment is not parallel to any axis, hence the first coordinates of
$p$ and $r$ are different, and the second coordinates of $p$ and $r$ are also
different.

We first show the following claim (*): for all points of the segment $[p,r]$
having exactly one integer coordinate in the range $\\{0,\ldots,n\\}$, the
difference between the other coordinate and the nearest integer is at least
$1/n$.

Indeed, let $(a,b)$ and $(c,d)$ be the respective coordinates of $p$ and $r$.
The points in the segment are those with coordinates $(a+x(c-a),b+x(d-b))$ for
$0\leq x\leq 1$. Assume that some coordinate is integer, say the first, then
$a+x(c-a)$ is an integer, say $e$. Hence, $x=\frac{e-a}{c-a}$, recalling that
$c\neq a$, where $a$ and $e$ and $c$ are integers in $\\{0,\ldots,n-1\\}$.
Then the second coordinate is $b+x(d-b)$. This can be expressed as a fraction
with integer numerator and with denominator $c-a$, which is an integer of
absolute value at most $n$. Hence, if the value of the second coordinate is
not an integer, its distance to the nearest integer is at least $1/n$. The
same argument applies if we exchange the role of the first and second
coordinates. This establishes claim (*) above.

Now, we use convexity. Considering the point $q$, the segment does not go via
that point, so considering all points with one integer coordinate matching
that of $q$ and the other integer coordinate differing from the coordinate of
$q$ by strictly less than $1/n$, we know that the segment cannot go via these
points. So the closest the segment can go is
$\frac{1}{\sqrt{2}}\times\frac{1}{n}$ (see Figure 2(b) for an illustration),
concluding the proof.

Second, we need to understand how close two segments with integer coordinates
that share a common endpoint can be from one another. Of course, close to the
endpoint, they can be arbitrarily close; but we need to show that they are
sufficiently far away once we are sufficiently far from the common endpoint.
For this, let us define the notion of _box_ :

######  Definition 3.3.

Given a point $p$ and length $\epsilon>0$, the _box_ of radius $\epsilon$
centered on $p$ is the square region with center $p$ and sides $2\epsilon$.

We can then claim:

######  Lemma 3.4.

Let $p,q,r$ be pairwise distinct points with integer coordinates, and consider
the segments $[p,q]$ and $[p,r]$. We assume that $[p,q]$ and $[p,r]$ are not
collinear, so $p$ is their only intersection.

Let $\epsilon>0$, and consider the box of radius $\epsilon$ centered on $p$.
Let $q^{\prime}$ and $r^{\prime}$ be arbitrary points of $[p,q]$ and $[p,r]$
respectively such that both are outside the box. Then the distance between
$q^{\prime}$ and $r^{\prime}$ is at least $\frac{\epsilon}{2n^{2}}$.

We illustrate the lemma in Figure 3. We need a simple auxiliary claim to show
the result.

$p$$q$$r$$2\epsilon$$q^{\prime\prime}$$r^{\prime\prime}$$r^{\prime\prime\prime}$
Figure 3: Illustration of Lemma 3.4. The lemma is shown by establishing a
lower bound on the orange distance, depending on the size of the box (in
blue).

######  Claim 1.

Consider a triangle $p$, $q^{\prime\prime}$, $r^{\prime\prime}$, where the
angles on $q^{\prime\prime}$ and on $r^{\prime\prime}$ are acute. Let $q$ be a
point of the ray with direction $(p,q^{\prime\prime})$ starting at
$q^{\prime\prime}$ and let $r$ be a point on the ray with direction
$(p,r^{\prime\prime})$ starting at $r^{\prime\prime}$. Then the distance
between $q$ and $r$ is greater than or equal to the distance between
$q^{\prime\prime}$ and $r^{\prime\prime}$.

The claim is illustrated on Figure 4. Let us prove it:

$p$$q^{\prime\prime}$$r^{\prime\prime}$$q$$r$$r^{\prime}$ Figure 4:
Illustration of Claim 1: the distance in blue is greater than or equal to the
distance in orange, provided the angles on $r^{\prime\prime}$ and
$q^{\prime\prime}$ are acute. We also illustrate the first step of the proof.

######  Proof 3.5.

We first reduce to the case where $q=q^{\prime\prime}$. This step is
illustrated on Figure 4. Consider the line
$(q^{\prime\prime},r^{\prime\prime})$. Up to swapping the points $q$ and
$q^{\prime\prime}$ with $r$ and $r^{\prime\prime}$, without loss of generality
we can assume that the distance of point $q$ to that line is no greater than
the distance of point $r$ to that line.

Let $r^{\prime}$ the intersection with $(p,r)$ of the parallel line to
$(q^{\prime\prime},r^{\prime\prime})$. It is immediate (e.g., by Thales’s
theorem) that the distance between $q$ and $r^{\prime}$ is no smaller than the
distance between $q^{\prime\prime}$ and $r^{\prime\prime}$. Further,
considering the triangle $p$, $q$, $r^{\prime}$, the angles on $q$ and
$r^{\prime}$ in that triangle are respectively equal to the angles on
$q^{\prime\prime}$ and $r^{\prime\prime}$ on the original triangle, so they
are also acute; further the point $r$ is still on the ray starting at
$r^{\prime}$ with direction $(p,r^{\prime})$. Hence, it suffices to study the
case where $q=q^{\prime\prime}$. (This case is not illustrated.)

Now, in this case, since the angle on $r^{\prime\prime}$ is acute, we know
that the projection of $q^{\prime\prime}$ on $(p,r^{\prime\prime})$ is in the
segment $[p,r^{\prime\prime}]$. This means that, letting $r^{\prime}$ be this
projection, and moving along the ray starting at $r^{\prime}$ with direction
$(p,r^{\prime})$, the distance to $q^{\prime\prime}$ is not decreasing. Doing
so, we first encounter $r^{\prime\prime}$ and then $r$, so we conclude that
indeed the distance between $q^{\prime\prime}$ and $r^{\prime\prime}$ is no
greater than the distance between $q=q^{\prime\prime}$ and $r$.

We now prove Lemma 3.4:

######  Proof 3.6 (Proof of Lemma 3.4).

Let $q^{\prime\prime}$ and $r^{\prime\prime}$ be the points on $[p,q]$ and
$[p,r]$ respectively at distance $\epsilon$ from $p$. These two points are
inside the box. As the triangle $p$, $q^{\prime\prime}$, $r^{\prime\prime}$ is
isosceles, the angles on $q^{\prime\prime}$ and $r^{\prime\prime}$ must be
acute. Thus, to show the bounds on points $p^{\prime}$ and $q^{\prime}$ as in
the lemma statement, by Claim 1 it suffices to show the claim on the distance
between $q^{\prime\prime}$ and $r^{\prime\prime}$.

First, up to exchanging $q$ and $r$ if necessary, we assume that the line
parallel to $(q^{\prime\prime},r^{\prime\prime})$ going through $q$ intersects
the line $(p,r)$ within the segment $[p,r]$. Let $r^{\prime\prime\prime}$ be
the intersection point. Considering the point $q$ and the segment $[p,r]$, we
have by Lemma 3.1 a lower bound of $\frac{1}{\sqrt{2}n}$ on the distance
between $q$ and $[p,r]$, translating to the same lower bound on the distance
between $q$ and the point $r^{\prime\prime\prime}$ which belongs to $[p,r]$.

We now use Thales’s theorem to show that the ratio between the lengths of
$[p,q^{\prime\prime}]$ and $[p,q]$ is the same as the ratio between the
lengths of $[q^{\prime\prime},r^{\prime\prime}]$ and
$[q,r^{\prime\prime\prime}]$. From the lower bound of Lemma 3.1, letting $x$
be the distance between $p$ and $q$, we have:

$\frac{\epsilon}{x}\leq d\sqrt{2}n$

We deduce:

$d\geq\frac{\epsilon}{x\sqrt{2}n}$

Now, $x\leq\sqrt{2}n$ given the range of coordinates, so we deduce:

$d\geq\frac{\epsilon}{2n^{2}}$

Thus, we have shown our lower bound on the distance between $q^{\prime\prime}$
and $r^{\prime\prime}$, which as we had argued implies a lower bound on point
$q^{\prime}$ and $r^{\prime}$ as in the lemma statement.

##  4 Approximating lines with paths

Our idea is to start from the drawing function defined in the previous section
and transform it to a topological embedding into a sufficiently large wall
graph. To do this, we will first argue how each straight line segment in the
drawing can be transformed to a path in a wall graph which stays sufficiently
close to the line. Formally, we show:

$p_{0}$$p_{1}^{\prime}$$p_{2}^{\prime}$$p_{3}^{\prime}$$p_{3}$$p_{4}^{\prime}$$p_{5}^{\prime}$$p_{6}^{\prime}$$p_{6}$
Figure 5: Approximating a segment by a path in a wall graph. The points
$p_{i}$ are equal to $p_{i}^{\prime}$ unless otherwise written.

######  Lemma 4.1.

Let $r,s$ be two integers, and consider two distinct integer points $(i,j)$
and $(i^{\prime},j^{\prime})$ that are vertices of the $(r,s)$-wall $W_{r,s}$,
with $1\leq i,i^{\prime}\leq r$ and $1\leq j,j^{\prime}\leq s$. Consider the
segment $[(i,j),(i^{\prime},j^{\prime})]$. Then we can construct in $O(r\times
s)$ a simple path from $(i,j)$ to $(i^{\prime},j^{\prime})$ in $W_{r,s}$ such
that, for each traversed vertex, its distance to the segment is at most $2$.

The lemma is illustrated on Figure 5.

######  Proof 4.2.

The claim is immediate if the segment is horizontal, i.e., $i=i^{\prime}$, so
we focus on the case of a non-horizontal segment. Up to swapping both points,
we assume that $i^{\prime}>i$. We consider points $p_{0},\ldots,p_{n}$ with
$n=i^{\prime}-i$, i.e., $n>0$, defined in the following way: $p_{0}$ is
$(i,j)$, and for $k>0$ the point $p_{k}$ is some point of the wall graph with
first coordinate $i+k$ which is at minimal distance of the point $\pi_{k}$ of
the segment having this first coordinate, i.e., having ordinate value $i+k$
(pay attention to the fact that the point $(x,y)$ is at row $x$, i.e.,
ordinate value $x$, and column $y$, i.e., abscissa $y$). In particular, we
must have $p_{n}=(i^{\prime},j^{\prime})$, and the distance of each $p_{k}$ to
$\pi_{k}$ is only due to the second coordinate, and it is at most $1/2$.

We now modify slightly our choice of the points $p_{1},\ldots,p_{n}$ to obtain
points $p_{1}^{\prime},\ldots,p_{n}^{\prime}$ and ensure that the latter
points have an incident vertical edge pointing up, i.e., if
$p_{k}=(i^{\prime\prime},j^{\prime\prime})$, we want to make sure that the
vertex is adjacent to $(i^{\prime\prime}-1,j^{\prime\prime})$. This is the
case of every other vertex on each row, so it can be enforced by replacing
each point $p_{i}$ not satisfying the condition by a left or right neighbor
$p_{i}^{\prime}$ which does, i.e., incrementing or decrementing the first
component. (It may be the case that only one of these two options is possible
if we are close to the borders of the wall.) Specifically, we choose the
neighbor which is closest to the segment. In so doing, the distance of the
intermediate points to the segment becomes at most $1$, achieved in the case
where $\pi_{k}=p_{k}$ and $p_{k}$ is not suitable (see the case of $p_{3}$ on
Figure 5).

It suffices now to design a path in the wall graph that successively visits
the points $p_{0}=p_{0}^{\prime},\ldots,p_{n}^{\prime},p_{n}$ (the last step
being one single edge, or no edge if $p_{n}=p_{n}^{\prime}$). We do so
inductively: from a vertex $p_{k}^{\prime}$, we first change the second
component to be that of $p_{k+1}^{\prime}$ while keeping the first component
unchanged, then we increase the second component (traversing the edge whose
existence is guaranteed by the choice of $p_{k+1}^{\prime}$ relative to
$p_{k+1}$). The only exceptional case is the last: if the node $p_{n}$ reached
is not a segment endpoint but a left or right neighbor, we finish by
traversing the requisite edge. It is clear that this definition ensures that
the path is simple. The path is illustrated again in Figure 5.

What is more, the distance of this path to the segment is at most 2. Indeed,
consider any choice of $k>0$, and let us study how far away the path from
$p_{k-1}^{\prime}$ to $p_{k}^{\prime}$ strays from the segment. The segment
connects $\pi_{k-1}$ to $\pi_{k}$, and we know that the first coordinate of
$p_{k-1}^{\prime}$ and $\pi_{k-1}^{\prime}$ is $i+k-1$ and the first
coordinate of $p_{k}^{\prime}$ and $\pi_{k}^{\prime}$ is $i+k$. So the segment
is at distance at most $1$ to any point in the wall graph whose first
coordinate is $i+k-1$ or $i+k$ and whose second coordinate is between that of
$\pi_{k-1}$ and that of $\pi_{k}$. But we know the path from
$p_{k-1}^{\prime}$ to $p_{k}^{\prime}$ visits only points satisfying these
conditions except that the second coordinate of $p_{k-1}^{\prime}$ and of
$p_{k}^{\prime}$ may each differ by at most $1$ for that of $\pi_{k-1}$ and of
$\pi_{k}$. So in total the distance of the visited vertices to the segment is
at most $1+1=2$. This bound of $2$ holds for the path from $p_{0}$ to
$p_{n}^{\prime}$, and the last edge added in case $p_{n}^{\prime}\neq p_{n}$
is not a problem because then we are clearly at distance $\leq 1$ from the
segment. This concludes the proof.

##  5 Scaling up the drawing

Figure 6: Illustration of the global construction. We consider a box
$B_{v}^{\prime\prime}$ centered on every vertex $v$ (in blue), and a distance
margin $M_{u,v}$ around every segment $[u,v]$ corresponding to an edge
$\\{u,v\\}$ (in orange). We choose the box sizes to guarantee several things:
(i) the boxes do not overlap; (ii) the margins around two different segments
with the same endpoint do not intersect outside of the box of this endpoint
(using Lemma 3.4, see dashed red circle near the bottom left of figure); (iii)
a box cannot intersect with the distance margin around a segment unless its
vertex is an endpoint of that segment (using Lemma 3.1, see dashed red circle
in the middle of figure). This guarantees that the path approximations that
stay close to each edge (Lemma 4.1) cannot intersect except within each of the
boxes.

Let us recall what we showed in Section 3. Let us fix a box size
$\epsilon\colonequals\frac{1}{4n}$. We will consider boxes $B_{v}$ of radius
$\epsilon$ centered on each vertex (recall Definition 3.3), and then scale up
the drawing. For the scale-up, define the scale factor $\sigma\colonequals
40n^{3}$. Take the drawing function $\delta$ defined in Section 3, and
multiply it by $\sigma$. We can now consider the $(r,s)$-wall graph $W_{r,s}$
with $r=\sigma(n-2)$ and $s=\sigma(n-2)$. The vertices of the drawing
correspond to points of the wall graph that are multiples of $\sigma$.

For each vertex $v$, we will consider the box $B_{v}^{\prime}$ centered on $v$
obtained from the box $B_{v}$ after scaling up, whose radius is
$\sigma\epsilon=10n^{2}$. We will also consider a larger box
$B_{v}^{\prime\prime}$ centered on $v$ with radius $\sigma\epsilon+2$. We will
finally consider, for every segment $[u,v]$ corresponding to an edge
$\\{u,v\\}$, the _margin_ $M_{u,v}$ at distance 2 around $[u,v]$, consisting
of all points at Euclidean distance $\leq 2$ from the segment. See Figure 6
for a summary of the situation. We make four claims:

  1. (i)

For any two distinct vertices $u\neq v$, the boxes $B_{u}^{\prime\prime}$ and
$B_{v}^{\prime\prime}$ for $u$ and $v$ do not intersect. This is because
$2\sigma\epsilon+4<\sigma$.

  2. (ii)

For any two segments $[u,v]$ and $[u,w]$ corresponding to edges $\\{u,v\\}$
and $\\{u,w\\}$ sharing one vertex endpoint $u$, the margins $M_{u,v}$ and
$M_{u,w}$ do not intersect except inside the larger box $B_{u}^{\prime\prime}$
of $u$. This is intuitively obtained by scaling up the bound from Lemma 3.4.
Specifically, consider any point $x$ in $M_{u,v}\cap M_{u,w}$. By definition,
$x$ is at distance $\leq 2$ from both $[u,v]$ and $[u,w]$, and the projections
$v^{\prime}$ and $w^{\prime}$ of $x$ on $[u,v]$ and $[u,w]$ respectively are
then at distance $\leq 4$ by the triangle inequality. Now, scaling up the
bound from Lemma 3.4, we know that any two points respectively on segments
$[u,v]$ and $[u,w]$ which are both outside the box $B_{u}^{\prime}$ must be at
distance at least $\frac{\sigma\epsilon}{2n^{2}}$, i.e., at least $5$. Thus,
at least one of the projections $v^{\prime}$ and $w^{\prime}$ must be inside
the smaller box $B_{u}^{\prime}$. Now, remember that the point $x$ is at
distance at most $2$ from that projection, so we conclude that $x$ is inside
the larger box $B_{u}^{\prime\prime}$, which concludes.

  3. (iii)

For any segment $[u,v]$ of the drawing and point $w$ different from $u$ and
$v$, the box $B_{w}^{\prime\prime}$ does not contain any point of the margin
$M_{u,v}$ of $[u,v]$. This is obtained by scaling up the bound from Lemma 3.1.
Specifically, considering the point $w$ and the segment $[u,v]$, we know that
the distance between $w$ and $[u,v]$ is at least $\frac{\sigma}{\sqrt{2}n}$,
which is at least $20n^{2}$. Now, the points of the box $B_{w}^{\prime\prime}$
are at distance $\leq\sqrt{2}\times(\epsilon\sigma+2)$ from $w$, i.e., at
distance $\leq\sqrt{2}\times(10n^{2}+2)$. Further, the points of the margin
are at distance $\leq 2$ from the segment. Now, we have
$\sqrt{2}\times(10n^{2}+2)+2<20n^{2}$ because $\sqrt{2}<1.5$ and $n\geq 1$, so
we conclude that the box $B_{w}^{\prime\prime}$ and margin do not intersect.

  4. (iv)

For two segments that do not share any endpoints, their margins do not
intersect. Indeed, the segments do not intersect (this uses the fact that
there are no edge crossings), and the distance between each endpoint pair is
at least $\sigma$, hence, at least $5$. (Note that, for any two segments that
do not intersect, the minimum of the distance from one segment to another can
always be achieved by taking one endpoint of one of the segments.)

In summary, after scaling up, we obtain a situation similar to Figure 6. The
vertices are at points whose coordinates are multiples of the integer
$\sigma$, and considering the box $B_{w}^{\prime\prime}$ of each vertex $w$,
and the margin $M_{u,v}$ at distance 2 around each segment $[u,v]$, then (i)
the boxes are pairwise disjoint; (ii) the margins of two segments sharing an
endpoint intersect only within the box of that endpoint; (iii) the box on a
vertex only intersects with the margins of the segments where this vertex
occurs; (iv) two margins of segments that do not share an endpoint do not
intersect.

Now, compute in polynomial time with Lemma 4.1 a path for each edge, that
connects the endpoints of the edge (i.e., the vertices) while staying at
distance at most $2$ from the segment that represents the edge, i.e., staying
in the margin of the segment corresponding to the edge. The total time to
compute these paths can be upper bounded by the total grid size, which is
$O(n^{8})$, times the number of paths, which is $O(n^{2})$, hence an upper
bound of $O(n^{10})$.

We know that the path for each segment remains in the margin at distance 2 of
that segment. We now claim that the paths of two segments can only share some
intermediate vertices if the segments share an endpoint $v$, and that then the
shared intermediate vertices are within the box $B_{v}^{\prime\prime}$ of that
endpoint. Indeed, if the segments do not share any endpoints then their
margins do not intersect by (iv), and as the paths are contained within the
margins, they also share no vertices in that case. Now, if the segments share
an endpoint $v$, the margins only intersect within $B_{v}^{\prime\prime}$ by
(ii), hence the same is true of the paths.

Thus, the only remaining part is to fix the embedding by changing the paths
within the boxes. We can do so for each box independently, as the boxes are
disjoint by (i), and by (iii) the box $B_{v}^{\prime\prime}$ centered on a
vertex $v$ does not contain any vertex for paths corresponding to edges that
do not involve $v$.

##  6 Making the paths disjoint within the boxes

For each vertex $v$ of the graph, let $G_{v}$ be the subgraph induced by the
vertices of the box $B_{v}^{\prime\prime}$ of radius $\sigma\epsilon+2$
centered on $v$. Note that, because the coordinates of the box centers are
multiples of the even integer $\sigma$ and the box radius $\sigma\epsilon+2$
is an even integer, we know that $G_{v}$ is isomorphic to a
$(2\sigma\epsilon+4,2\sigma\epsilon+4)$-wall graph. For each edge
$e=\\{u,v\\}$, let $u_{e}$ and $v_{e}$ be respectively the last and first
vertices of the path from $u$ to $v$ which are in the boxes
$B_{u}^{\prime\prime}$ and $B_{v}^{\prime\prime}$ respectively, and let
$P_{e}$ be the subpath starting just after $u_{e}$ and finishing just before
$v_{e}$.

We know that the paths $P_{e}$ and $P_{e^{\prime}}$ for two distinct edges $e$
and $e^{\prime}$ do not intersect, because these paths are outside the boxes
of the vertex endpoints, they are within the margin of the segment so cannot
enter any other box by (iii), and they cannot be within the margin of any
other segment by (ii) and (iv).

$v_{3}$$v_{2}$$v_{1}$$u$ Figure 7: Choosing a vertex of the wall graph to
embed the vertex $u$ of the graph with three neighbors $w_{1},w_{2},w_{3}$
such that the last vertices in the box in the paths approximating the edges
$\\{u,w_{1}\\}$ and $\\{u,w_{2}\\}$ and $\\{u,w_{3}\\}$ are $v_{1}$ and
$v_{2}$ and $v_{3}$. We show in black the beginning of the segments
$[u,w_{1}]$ and $[u,w_{2}]$ and $[u,w_{3}]$, and show in blue the paths given
by Lemma 4.1, which overlap. To fix the issue we simply connect $v_{1}$ and
$v_{2}$ and $v_{3}$ as explained in the text and choose our target vertex for
$u$ accordingly.

So let us now fix the rest of the paths, which are within the boxes. Consider
the paths from a vertex $u$ to the vertices of the form $u_{e}$ that are just
before the paths $P_{e}$. There are at most $3$ such vertices, because the
graph is degree-$3$. See Figure 7 to understand why the paths from $u$ to
these three vertices may intersect. So we change completely these paths, in
the process possibly also changing the image of the vertex $v$ in the
embedding to be another vertex of the box.

Let us state what we need:

######  Lemma 6.1.

For any $(r,s)$-wall graph $W_{r,s}$ with $r\geq 1$ and $s\geq 2$, given three
distinct vertices $p$, $q$, $r$, we can compute in time $O(r\times s)$ a
vertex $x$ of $W_{r,s}$ and three vertex-disjoint paths between $x$ and $p$,
and $x$ and $q$, and $x$ and $r$.

######  Proof 6.2.

As $s\geq 2$, the graph is connected. Find in linear time an arbitrary simple
path from $p$ to $q$. If $r$ is in the path, take $x=r$, which concludes.
Otherwise, find in linear time an arbitrary simple path from $r$ to $p$, and
stop as soon as it encounters a vertex of the previous path (which may be $p$,
$q$, or an intermediate vertex of that path). Take the encountered vertex to
be $x$, and the three vertex-disjoint paths connecting $x$ and $p$, $x$ and
$q$, and $x$ and $r$, are then easy to find.

Thus, for each vertex $v$, we consider the box $B_{v}^{\prime\prime}$ and the
graph $G_{v}$. If $v$ has strictly less than 2 neighbors, there is nothing to
do. If $v$ has two neighbors, letting $v_{1}$ and $v_{2}$ be the last vertices
before the paths $P_{e_{1}}$ and $P_{e_{2}}$ corresponding to the edge, we set
the image of $v$ to be $v_{1}$ and pick an arbitrary simple path from $v_{1}$
to $v_{2}$ in $G_{v}$. If $v$ has three neighbors, we use Lemma 6.1 to find
the image of $v$ and the paths. This process is in linear time in each box, so
in time $O(n^{8})$ overall where $n$ is the number of graph vertices.

We have explained how to fix the embedding inside the boxes to ensure that
there are no intersections inside the boxes, and there are no intersections
outside the boxes, so this concludes the computation of the embedding and
concludes the proof of Theorem 1.1.

## References

  * [1] Antoine Amarilli.  Leveraging the structure of uncertain data.  PhD thesis, Télécom ParisTech, 2016.
  * [2] Chandra Chekuri and Julia Chuzhoy.  Polynomial bounds for the grid-minor theorem.  Journal of the ACM (JACM), 63(5), 2016.
  * [3] Marek Chrobak and Thomas H. Payne.  A linear-time algorithm for drawing a planar graph on a grid.  Information Processing Letters, 54(4), 1995.
  * [4] Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach.  Spanners in sparse graphs.  Journal of Computer and System Sciences (JCSS), 77(6), 2011.
  * [5] Neil Robertson, Paul Seymour, and Robin Thomas.  Quickly excluding a planar graph.  Journal of Combinatorial Theory, Series B, 62(2), 1994.
  * [6] Walter Schnyder.  Embedding planar graphs on the grid.  In Proc. SODA, 1990.
  * [7] Roberto Tamassia and Ioannis G. Tollis.  Planar grid embedding in linear time.  IEEE Transactions on circuits and systems, 36(9), 1989.
  * [8] user67422 (https://cstheory.stackexchange.com/users/67422/user67422).  Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time.  Theoretical Computer Science Stack Exchange.  URL: https://cstheory.stackexchange.com/q/52489, arXiv:https://cstheory.stackexchange.com/q/52489.