11institutetext: David R. Cheriton School of Computer Science, University of
Waterloo22institutetext: Department of Computer Science, Saint Louis
University33institutetext: Computer Science Department, University of
California, Irvine44institutetext: Univ. Grenoble Alpes, CNRS, Grenoble INP,
GIPSA-lab, 38000 Grenoble, France55institutetext: Department of Computational
Mathematics, Science and Engineering, Michigan State University

# Homotopy height, grid-major height and graph-drawing height††thanks: Erin
Chambers was supported in part by NSF grants CCF-1614562 and DBI-1759807.
David Eppstein was supported in part by NSF grants CCF-1618301 and
CCF-1616248. Arnaud de Mesmay was supported in part by grants
ANR-18-CE40-0004-01 (FOCAL) and ANR-16-CE40-0009-01 (GATO). This work began at
the Fifth Annual Workshop on Geometry and Graphs, at the Bellairs Research
Institute of McGill University.

Therese Biedl 11 Erin Wolf Chambers 22 David Eppstein 33 Arnaud De Mesmay 44
Tim Ophelders 55

###### Abstract

It is well-known that both the pathwidth and the outer-planarity of a graph
can be used to obtain lower bounds on the height of a planar straight-line
drawing of a graph. But both bounds fall short for some graphs. In this paper,
we consider two other parameters, the (simple) homotopy height and the
(simple) grid-major height. We discuss the relationship between them and to
the other parameters, and argue that they give lower bounds on the straight-
line drawing height that are never worse than the ones obtained from pathwidth
and outer-planarity.

##  1 Introduction

Straight-line drawings of planar graphs are one of the oldest and most
intensely studied problems in graph drawing [30, 14, 26, 29, 19, 25]. It has
been known since the 1990s that every planar graph has a straight-line drawing
of height $n{-}1$ [19, 25] and that some planar graphs require height
$\frac{2}{3}n$ if the outer-face must be respected [11, 18]. Nevertheless many
problems surrounding the height of planar straight-line drawings remain open;
it is not even known whether minimizing height is NP-hard (although the
problem is NP-hard when edges may only connect adjacent rows [22] and it is
fixed-parameter tractable in the output height [12]).

One of the chief obstacles is that very few tools are known for arguing that a
planar graph requires a certain height in all planar straight-line drawings.
Two graph parameters are commonly used for this: the pathwidth (as the height
is at least $\textit{pw}(G)$ [15, 12]) and the outer-planarity (as the height
is at least twice the outer-planarity minus 1 [11, 18]); for detailed
definitions see Section 2. However, both parameters may be constant in graphs
that require linear height [4](see also Fig. 7(b)).

In this paper, we study two other graph parameters, the _homotopy height_
$\textit{Hh}(G)$ and the _grid-major height_ $\textit{GMh}(G)$ and their
simple variants $\textit{sHh}(G)$ and $\textit{sGMh}(G)$. Roughly speaking,
the homotopy height is defined as the minimum $k$ such that a sequence of
paths of length at most $k$ sweep the graph111We note that there are _many_
possible variants of homotopy height, all quantifying in slightly different
ways the optimal way to sweep a planar graph with a curve. We have chosen here
one particular variant that seems to be most suitable for graph drawing
purposes, and we only study it for triangulated graphs. We refer the reader to
other recent works on this parameter [8, 21, 7] for further discussion.of
other variants and their complexity., while the grid-major height is the
minimum height of a grid of which the graph is a minor. Fig. 1 illustrates
this and graph parameters used in the paper. Our simple variants add
simplicity constraints to the paths involved in the sweeping or the columns of
the grid-major representation. We show that despite their apparent
differences, homotopy height and grid-major height are equal, and that both
the normal and the simple variants are lower bounds on the graph drawing
height. More precisely, any planar triangulated graph $G$ has

$pw(G)\stackrel{{\scriptstyle(*)}}{{\leq}}\textit{Hh}(G)=\textit{GMh}(G)\stackrel{{\scriptstyle(*)}}{{\leq}}\textit{sHh}(G)=\textit{sGMh}(G)\stackrel{{\scriptstyle(*)}}{{\leq}}\textit{VRh}(G)=\textit{SLh}(G),$
(1)

where $\textit{VRh}(G)$ and $\textit{SLh}(G)$ are the minimum height of a
visibility representation and straight-line drawing of $G$. As we will show,
the inequalities marked with $(*)$ are strict for some planar graphs. More
strongly, the parameters separated by these inequalities can differ by non-
constant factors from each other.

In particular, the (simple) grid-major height and homotopy-height can both
serve as lower bounds on the height of a straight-line drawing. For some
graphs (e.g. the one in Fig. 7(b)) this gives a better lower bound than can be
achieved via pathwidth, though not a better lower bound than what was known
[4]. We should mention that the outer-planarity $op$ is also related to these
parameters via

$2op(G)-1\stackrel{{\scriptstyle(*)}}{{\leq}}\textit{GMh}(G),$ (2)

so the homotopy-height and grid-major height can also can replace outer-
planarity as lower-bound tool for graph-drawing height, and in fact, provide a
convenient vehicle for unifying both tools. While these results have not yet
led us to new lower bound results for straight-line drawings, they provide new
tools which had not been considered previously, and suggest a promising new
line of inquiry.

(a)

(b)

(c)

(d)

(e)

Figure 1: The same graph with (a) a straight-line drawing, (b) a flat
visibility representation, (c) a simple grid-major representation, (d) the
corresponding contact-representation, (e) a simple homotopy. The height is
always four. The moves of the homotopy are: a face-flip at $\\{u,v,x\\}$, a
boundary-move, an edge-slide at $(v,y)$, a face-flip at $\\{x,y,w\\}$ and
face-flip at $\\{u,x,w\\}$.

Our results naturally raise the question of the complexity of computing these
parameters. Computing the optimal height of homotopies is conjectured but not
known to be NP-hard [8]; even arguing that it is in NP is non-trivial [7],
although it has a logarithmic approximation [21, 7]. Our equalities imply that
computing the homotopy-height $k=\textit{Hh}(G)$ is (non-uniform) fixed-
parameter tractable in $k$. Indeed, it equals grid-major height, which is
closed under taking minors. Minor testing can be expressed in second-order
logic, and the graphs of bounded grid-major height have bounded pathwidth, so
it follows from graph minor theory and Courcelle’s theorem [10] that for any
$k$, the graphs with grid-major height $k$ and homotopy-height $k$ can be
recognized in linear time. However, this method uses the (unknown!) forbidden
minors for grid-major height; finding them remains an open problem of
independent interest. We can also show more directly using Courcelle’s theorem
that simple grid-major height is fixed-parameter tractable.

All our results are only for _triangulated planar graphs_ , planar graphs
where all faces (including the outer-face) are triangles. This is not a big
restriction for graph drawing height, as any planar graph $G$ is a subgraph of
a triangulated planar graph $G^{\prime}$ that has a straight-line drawing of
the same height, up to a small additive term. (Obtain $G^{\prime}$ by
triangulating the convex hull of a drawing of $G$ and adding three vertices
that surround the drawing.) Most of our parameters naturally carry over to
non-triangulated planar graphs, but some parameters would be much more
cumbersome to define and work with for non-triangle faces.

##  2 Definitions

All graphs in this paper are _planar_ : they can be drawn in the plane without
crossings. Their _faces_ are maximal connected regions that remain when
removing the drawing); we call the unbounded face the _outer-face_. Unless
otherwise stated, we study only _simple_ graphs that have no loops and at most
one edge between any two vertices, and we almost always study _triangulated
graphs_ , where all faces (including the outer-face) are bounded by a simple
cycle of length 3. Such a graph is _maximal planar_ : no edge can be added
without violating simplicity or planarity. Its planar embedding is unique up
to the choice of outer-face.

Let $G$ be a triangulated graph with fixed outer-face $f$. We define _outer-
planarity_ $op(G)$ via a removal process as follows: In a first step, remove
all vertices on the outer-face. In each subsequent step, remove all vertices
on the outer-face of the remaining graph. Then $op(G,f)$ is the number of
steps until no vertices remain, and $op(G)$ is the minimum of $op(G,f)$ over
all choices of face $f$.

#### Graph-drawing parameters:

The _$W\times H$ -grid_ has vertices at the _grid-points_
$\\{1,\dots,W\\}\times\\{1,\dots,H\\}$ and an edge between any two grid-points
of distance one. A _straight-line drawing_ of $G$ consists of a mapping of $G$
to grid-points such that if all edges are drawn as straight-line segments
between their endpoints, no two edges cross and no edge overlaps a non-
incident vertex. Every planar graph has such a drawing [30, 14, 26] whose
supporting grid has height at most $n-1$ [19, 25]. We use $\textit{SLh}(G)$ to
denote the smallest height $h$ of a straight-line drawing of $G$.

A _flat visibility-representation_ of $G$ consists of an assignment of a
horizontal segment (_bar_) to every vertex of $G$ such that for any edge
$(v,w)$ there exists a _line of visibility_ , i.e., a line segment connecting
bars of $v,w$ that intersects no other bar. In the original definition lines
of visibility had to be horizontal; for us it will be more convenient to allow
both horizontal and vertical lines of visibility, as long as they do not
cross. Every planar graph has a flat visibility representation [31, 28, 24].
We use $\textit{VRh}(G)$ to denote the smallest height $h$ of such a
representation, presuming all bars reside at positive integral
$y$-coordinates.

#### Width parameters:

A _path decomposition_ of a graph $G$ is a collection $X_{1},\dots,X_{L}$ of
vertex-sets (_bags_) that satisfies the following: each vertex $v$ appears in
at least one bag, the bags containing $v$ are consecutive, and for each edge
$(v,w)$ at least one bag contains both $v$ and $w$. The _width_ of a path
decomposition of $G$ is the largest bag-size minus 1, and the _pathwidth_
$\textit{pw}(G)$ of a graph is the smallest possible width of a path
decomposition.

We introduce another width parameter which is quite natural, but to our
knowledge has not been studied before. A _grid-representation_ of a graph $G$
consists of a $W\times H$-grid where each gridpoint is labelled with one
vertex of $G$ in such a way that (1) every vertex appears at least once as a
label, (2) for any vertex $v$ the grid-points that are labelled $v$ induce a
connected subgraph of the grid, and (3) for any edge $(v,w)$ of $G$ there
exists a grid-edge where the ends are labelled $v$ and $w$. In particular, if
$G$ has a grid-representation then it is a minor of the $W\times H$-grid. Let
$\textit{GMh}(G)$ be the _grid-major height_ , i.e., the smallest $h$ such
that $G$ has a grid-representation where the grid has height $h$.

We say that a grid-major representation of $G$ is _simple_ if in every column
$c$ of the grid and for any vertex $v$ of $G$, the nodes labeled $v$ in $c$
form a connected subgraph (which is thus a path). The _simple grid-major
height_ of $G$, denoted $\textit{sGMh}(G)$, is the smallest $h$ such that $G$
has a simple grid-major representation of height $h$.

A grid-major representation of height $h$ can be viewed, equivalently, as a
_contact-representation_ with integral orthogonal polygons as follows: Assign
to every vertex $v$ the polygon $P(v)$ that we obtain if we replace every
grid-point labelled $v$ with a unit square centered at that grid-point and
take their union. Since the grid-representation uses integral points, the
coordinates of sides of $P(v)$ are halfway between integers. See Fig. 1(d). We
get a set of interior-disjoint orthogonal polygons with integer edge-lengths
whose union is a rectangle of height $h$, where $(v,w)$ is an edge of $G$ if
and only if $P(v)$ and $P(w)$ share at least one unit-length segment on their
boundaries. Conversely any contact-representation with integral orthogonal
polygons that uses all points inside a bounding rectangle can be viewed as a
grid-major representation. A simple grid-major representation becomes a
contact representation with _$x$ -monotone polygons_ (every vertical line
intersects the polygon in an interval) and vice versa. Contact-representations
of graphs have been studied extensively (see e.g. [2] and the references
therein), but to our knowledge the question of the required height of such
representations has not previously been considered.

#### Homotopy parameters:

A homotopy of a triangulated graph $G$ is a sequence of paths, connected by
elementary moves, that together sweep the entirety of the graph $G$. We will
allow these paths to have moving endpoints on the outer-face of $G$.
Precisely, a _(discrete) simple homotopy_ is defined for a planar triangulated
graph $G$ with a fixed outer-face $\\{u,v,w\\}$, and it consists of a sequence
$h_{0},\dots,h_{W}$ of walks in $G$ (we call these _curves_) such that:

  1. 1.

$h_{0}$ and $h_{W}$ are trivial curves at two distinct vertices of the outer-
face, say $u$ and $v$.

  2. 2.

The vertices $u$ and $v$ partition the outer-face into two subpaths $s(uv)$
and $t(uv)$. For $0\leq i\leq W$, the curve $h_{i}$ starts on $s(uv)$ and ends
on $t(uv)$.

  3. 3.

For all $0\leq i<W$ we can obtain $h_{i+1}$ from $h_{i}$ with a face-flip,
edge-slide, a boundary-move or a boundary-edge-slide; see Fig. 2.

Figure 2: An illustration of the types of moves in a discrete homotopy.

inline]TB: The second kind of face-flip is weird! I guess this matches the
definition, but if you disallow the first time of face-flip (resulting in a
spike) in this situation then the proof of Lemma 5 needs a bit more work.
Specifically, Fig. 5(c) is a face-flip for simple homotopies, but might be
“half” of this second kind of face-flip if the vertex below the junction also
shows up higher up again.

inline]A:I think that we should disallow the second kind of face-flip because
it is the concatenation of a spike and the first kind of face flip. Actually I
think that the definition already disallows it (“that contains edges of
$h_{i}$”), so I removed it.

Here a _face-flip_ consists of picking an inner face $\\{x,y,z\\}$ such that
the subsequence $x$-$y$ is in $h_{i}$, and replacing the sub-path $x$-$y$ by
$x$-$z$-$y$ to obtain $h_{i+1}$. The reverse move, going from $x$-$z$-$y$ to
$x$-$y$, is also allowed. An _edge-slide_ 222Edge-slides are typically not
allowed in discrete homotopies, but the result of one edge-slide is the same
as flipping two inner faces consecutively. Thus, allowing edge-slides only
results in an additive difference of at most one for the homotopy height.
consists of picking an edge $e=(x,y)$ adjacent to two inner faces
$\\{x,y,z\\}$ and $\\{x,y,t\\}$, such that the subsequence $z$-$x$-$t$ is in
$h_{i}$. Then replace the subpath $z$-$x$-$t$ in $h_{i}$ by $z$-$y$-$t$ to
obtain $h_{i+1}$. A _boundary-move_ consists of picking an edge $e=(x,y)$ on
the outer face, and, if $e\in s(uv)$, and $x$ is the start of $h_{i}$, it
appends $y$ so that it becomes the new starting point (thus replacing $x$ by
the subsequence $y$-$x$). If $e\in t(uv)$ and $x$ is the end of $h_{i}$, it
appends $y$ at the end. The reverse operations are also allowed. A _boundary-
edge-slide_ consists of picking an edge $e=(x,y)$ on the outer face adjacent
to an inner face $\\{x,y,z\\}$, and, if $e\in s(uv)$ and $h_{i}$ starts with
$x$-$z$, we flip $\\{x,y,z\\}$ and remove $e$, i.e., we replace the starting
subsequence $x$-$z$ by $y$-$x$. The symmetric operation for edges on $t(uv)$
is also allowed. (Observe that this boundary-edge-slide is the same as
flipping a face and removing the boundary edge with a boundary move.). See
Fig. 2.

The _height_ of a simple homotopy is the length of the longest path $h_{i}$,
counting as path-length the number of vertices. Let $\textit{sHh}(G,f)$ be the
minimum height of a simple homotopy of $G$ that uses $f$ as outer-face, and
set $\textit{sHh}(G)$ (the _simple homotopy height_) to be the minimum of
$\textit{sHh}(G,f)$ over all choices of outer-faces $f$. (Since we only study
triangulated graphs the rotation scheme is unique and so this covers all
possible planar embeddings.)

The definition of a (non-simple) homotopy is obtained by removing the
simplicity assumption on the curves $h_{i}$, and allowing two other kinds of
moves (spikes and unspikes) leveraging the non-simplicity of the curves. For
technical reasons and to obtain a maximal generality, we will also relax the
conditions on the endpoints and the starting and ending curves. Since the
precise definition is somewhat technical, we postpone it to Section 3.2.

#### Some simple results:

We briefly review some relationships that are well-known, or easily derived.

  * •

$\textit{pw}(G)\leq\textit{GMh}(G)$ since a $W\times H$-grid has pathwidth at
most $H$ and pathwidth is closed under taking minors.

  * •

Obviously $\textit{GMh}(G)\leq\textit{sGMh}(G)$.

  * •

$\textit{sGMh}(G)\leq\textit{VRh}(G)$ since a flat visibility representation
can easily be converted into a simple grid-major representation by assigning
label $v$ to all grid-points of the bar of $v$ as well as all grid-points that
this bar can see downward or rightward without intersecting other bars or non-
incident edges. See Fig. 1(b-c).

  * •

$\textit{VRh}(G)=\textit{SLh}(G)$ since flat visibility representations can be
transformed into straight-line drawings of the same height, and vice versa
([5]. using [23, 13]).

  * •

Finally we have $2op(G)-1\leq\textit{GMh}(G)$. To this end, assume that we
have a grid-major representation $\Gamma$ of $G$ of height $h$. Observe that
the grid-graph $\Gamma$ has outer-planarity $\lceil h/2\rceil$. Since outer-
planarity does not increase when taking minors it follows that
$op(G)\leq\lceil h/2\rceil\leq\frac{h+1}{2}$.

##  3 Homotopy-height and grid-major height

The above inequalities fill in most of the chain in Equation 1, but one key
new part is missing: how does the (simple) homotopy height relate to the
(simple) grid-major height?

###  3.1 Simple grid-major height and simple homotopy height

######  Lemma 1.

For any triangulated planar graph $G$ we have
$\textit{sGMh}(G)\leq\textit{sHh}(G)$.

###### Proof.

Let $h_{0},\dots,h_{W}$ be a simple homotopy of height $k=\textit{sHh}(G)$.
The rough idea is to label a $W\times k$-grid by giving the gridpoints in the
$i$th column the labels of the vertices in $h_{i}$, in top-to-bottom-order,
and adding some duplicate copies of vertices in $h_{i}$ to fill the column.
However, we must insert more columns in between to ensure the properties of a
simple grid-major representation.

It will be easier to describe this by giving a contact-representation of $G$
where all polygons are $x$-monotone and the height is $k$. Curve $h_{0}$ is a
vertex $u$; we initialize $P(u)$ as a $1\times k$ rectangle. Now assume that
for some $i\geq 0$, we have built a contact representation $\Gamma_{i}$ of the
graph that was swept by $h_{0},\dots,h_{i}$. Furthermore, the right boundary
of the bounding box of $\Gamma_{i}$ contains sides of the vertices in $h_{i}$,
in order. We explain how to expand $\Gamma_{i}$ rightwards to represent
$h_{i+1}$, depending on the move that was used to obtain $h_{i+1}$, see also
Fig. 3.

  * •

Assume first that $h_{i+1}$ was obtained from an edge-slide along $(x,y)$,
thus $h_{i}$ contained $t$-$x$-$z$ for some vertices $t,z$ and this was
replaced by $t$-$y$-$z$ in $h_{i+1}$. Expand $\Gamma_{i}$ rightward by one
unit, and expand all polygons of vertices in $h_{i}$ rightward by one unit,
except for polygon $P(x)$. The pixels to the right of $P(x)$ are used to start
a new polygon $P(y)$.

  * •

A boundary-edge slide is handled in exactly the same way; the only difference
is that $x$ and $y$ are vertices on the outerface and vertex $z$ does not
exist.

  * •

Assume now that $h_{i+1}$ was obtained from a face-flip at face $\\{a,b,c\\}$.
Assume further that it was _increasing_ , i.e., $|h_{i+1}|>|h_{i}|$. Up to
renaming, path $a$-$b$ in $h_{i}$ was replaced by path $a$-$c$-$b$ in
$h_{i+1}$. So $|h_{i}|=|h_{i+1}|{-}1\leq k{-}1$, which means that at least one
polygon $P(d)$ for some $d\in h_{i}$ has height 2 or more on the right
boundary. Insert an (upward or downward) staircase that shifts this extra
height to $a$ or $b$ while keeping all polygons of $h_{i}$ on the right
boundary, see Fig. 3. This may take up to $k$ units of width, but does not
affect the height.

Now one of $P(a),P(b)$ has height 2 or more on the right boundary. Expand the
drawing rightward by one more unit, and expand all polygons rightward by one
unit, except that at the horizontal line between $P(a)$ and $P(b)$ we remove
one pixel from the polygon that has height at least 2 and start polygon $P(c)$
there.

  * •

Assume now that $h_{i+1}$ was obtained from a face-flip at face
$\\{a^{\prime},b^{\prime},c^{\prime}\\}$ that was _decreasing_ , i.e.,
$|h_{i+1}|<|h_{i}|$. Up to renaming, $h_{i}$ contains
$a^{\prime}$-$c^{\prime}$-$b^{\prime}$ which was replaced by
$a^{\prime}$-$b^{\prime}$ in $h_{i+1}$. Expand $\Gamma_{i}$ rightward by one
unit, and expand all polygons of vertices in $h_{i}$ rightward by one unit,
except for polygon $P(c^{\prime})$. The pixels to the right of $P(c^{\prime})$
added to $P(a)$ or $P(b)$.

  * •

An (increasing or decreasing) boundary-move is handled similarly; the only
difference is that $c=v$ or $c=w$ and $b$ does not exist.

Figure 3: Converting a discrete simple homotopy into a contact-representation.

In all cases the polygons remain connected and are $x$-monotone. Furthermore
we realized exactly those incidences that were added to the graph when
sweeping to $h_{i+1}$, and the right boundary contains exactly the polygons of
vertices of $h_{i+1}$, in order. Therefore, repeating gives a contact-
representation of height $k$ that uses $x$-monotone polygons, and thus the
desired simple grid-major representation. ∎

######  Lemma 2.

For any triangulated planar graph $G$ we have
$\textit{sHh}(G)\leq\textit{sGMh}(G)$.

###### Proof.

Fix a simple grid representation $\Gamma$ of $G$ of height $\textit{sGMh}(G)$.
For this proof it will be easier to interpret $\Gamma$ as a contact
representation. So for any vertex $z$, let $P(z)$ be the orthogonal polygon
obtained by taking the unions of all unit squares whose centerpoint is a grid
point labelled $z$. Since the grid-representation uses integral points, the
coordinates of sides of $P(v)$ are halfway between integers. $P(z)$ is
$x$-monotone since $\Gamma$ is simple, and it therefore has a unique _leftmost
side_ , i.e., vertical side of $P(z)$ that minimizes the $x$-coordinate.

The idea of obtaining a simple homotopy from this is easy: For each integer
$i$, let $h_{i}$ be the set of vertices whose polygons intersect the vertical
line $\\{x=i\\}$, listed from top to bottom. This is clearly a walk in the
contact-graph of $\Gamma$, and hence a walk in $G$ since $G$ is maximal. It is
also simple since polygons are $x$-monotone. However, to argue that these
curves satisfy the assumptions on a homotopy, we first need to modify the
contact representation (without changing its heights) to satisfy additional
properties.

A _junction_ is a point that belongs to at least three sides of polygons; we
call it _interior/exterior_ depending on whether it lies on the boundary of
the rectangle $\cal R$ that encloses the contact representation. No junction
can belong to four sides since $G$ is maximal, so it can be classified as
_horizontal_ or _vertical_ depending on the majority among its incident sides.
A _corner_ is a point that belongs to exactly two sides of polygons; thus this
is either a corner of $\cal R$ or a place where a reflex corner of one polygon
$P(v)$ equals a convex corner of an adjacent polygon $P(v^{\prime})$. A _side_
of the contact representation is a horizontal or vertical line segments that
connects two junctions or corners. (This may be equal to or a subset of a side
of polygon, but the meaning of “side” will be clear from context.) It is not
possible for both ends of a side to be exterior junctions, or else the
corresponding edge of $G$ would be a bridge of the graph, contradicting the
3-connectivity of the triangulated graph $G$.

######  Claim 1.

We may assume that $\Gamma$ has no interior vertical junction.

###### Proof.

An interior vertical junction can be replaced by a corner and an interior
horizontal junction (after lengthening some other horizontal edges) without
changing the height or the adjacencies. See Fig. 4(a). This change can be done
in two ways. Let $P(z)$ be the polygon whose side $s$ includes both vertical
sides incident to the junction. If $P(z)$ is $x$-monotone then $s$ either on
the top or the bottom chain (or it is leftmost or rightmost, but then both
methods of doing the change work). If $s$ was part of the top chain of $P(z)$,
then the change where $P(z)$ is below the new horizontal edge maintains
$x$-monotonicity, else the other one does. All other polygons have no new
horizontal sides and so clearly stay $x$-monotone. ∎

######  Claim 2.

We may assume that no two vertical sides have the same $x$-coordinate unless
they are both on the left boundary or both on the right boundary.

###### Proof.

Let $e$ and $e^{\prime}$ be two vertical sides with the same $x$-coordinate,
and let $\ell$ be the line through them, where $\ell$ is not the left or right
boundary. Walking from $e$ towards $e^{\prime}$ along $\ell$, we must
encounter an end of $e$, which is a junction or a corner. If it is a junction
then it must be horizontal since $e$ is not on the left or right boundary.
Either way, there is a region between $e$ and $e^{\prime}$ on $\ell$ that does
not belong to a side of a polygon. Therefore we can move $e$ slightly
rightward so that the sides have different $x$-coordinates. See Fig. 4(b). ∎

(a)

(b)

(c)

Figure 4: (a) Bringing $P(v)$ to the left boundary. (b) Removing vertical
interior junctions. (c) Making $x$-coordinates distinct. (d) Bringing a third
vertex to the left boundary. (e) Making the left and right boundary support
two distinct edges.

We say that a polygon $P(z)$ _touches the top/left/bottom/right boundary_ if
it contains part of this boundary of $\cal R$.

######  Claim 3.

We may assume that at least two polygons touch the left boundary.

###### Proof.

Assume that only one polygon $P(u)$ touches the left boundary. Let $v\neq u$
be such that the left side $e_{v}$ of $P(v)$ has minimal $x$-coordinate. (Fig.
4(c) illustrates the scenario if one ignores $P(w)$.) Since $v\neq u$, side
$e_{v}$ is not on the left boundary, hence interior (except perhaps at its
ends). No junction lies in the open segment $e_{v}$, because this would be an
interior vertical junction and we removed those. Not both ends of $e_{v}$ can
be corners, else both those corners would be convex for $P(v)$ (by choice of
$e_{v}$ as leftmost side), hence reflex for the polygon $P$ to the left of
$e_{v}$, which contradicts $x$-monotonicity. Neither end of $e_{v}$ can be an
interior junction, else the polygon $P(w)$ with $w\neq u,v$ at it would have
points farther left, contradicting the choice of $v$. So at least one end of
$e_{v}$ is an exterior junction and $v$ touches the boundary. The other end of
$e_{v}$ cannot be an exterior junction (otherwise $v$ would be a cutvertex)
and so it must be a corner, creating a horizontal side common to $P(v)$ and
$P(u)$. So we can remove everything to the left of the line $\ell$ through
$e_{v}$ (which contains only points of $P(u)$) and retain a contact
representation of the same graph since $P(u)$ and $P(v)$ have a horizontal
side in common. ∎

######  Claim 4.

We may assume that the union of the four boundaries consists of exactly three
vertices, while preserving the previous assumption.

###### Proof.

First observe that there cannot be more than three different vertices
occupying the left, top right, and bottom boundaries of $\cal R$, since $G$ is
triangulated.

By Claim 3 we can assume that at least two different vertices touch the left
boundary, and at least two different vertices touch the right boundary by a
symmetric claim. This proves the claim unless the same two vertices $u,v$
touch both left and right boundary, which in particular means that they meet
at two exterior junctions. Let $v\neq u,w$ be a vertex that minimizes the
$x$-coordinate of its leftmost side $e_{v}$. Exactly as in Claim 3 one argues
that not both ends of $e_{v}$ can be corners, so one end of $e_{v}$ is a
junction. This junction is internal (else $v$ would touch the top or bottom
boundary), so it is horizontal. The other two polygons at this junction must
be $P(u)$ and $P(w)$ because they occupy points farther left than $v$, see
Fig. 4(c). This implies that the other end of $e_{v}$ _must_ be a corner, else
three vertices would have points to the left of $e_{v}$, contradicting the
choice of $v$. Therefore $P(v)$ is adjacent to both $P(u)$ and $P(w)$ at
horizontal sides. We can now delete everything to the left of the line $\ell$
through $e_{v}$; this changes no adjacency since $v$ is adjacent to $u,w$ via
horizontal sides and $(u,w)$ is realized at the other external junction. ∎

######  Claim 5.

We may assume that exactly one vertex touches the left boundary and exactly
one different vertex touches the right boundary, while preserving the previous
assumptions (except those of Claim 3).

###### Proof.

We already know that three vertices touch some boundary, and that at least two
of them touch the left boundary and (by a symmetric argument) at least two of
them touch the right boundary. Not all three of them can touch both the left
and the right boundary, else at least one of them would be a cutvertex. So
assume (up to a horizontal flip) that exactly two vertices touch the right
boundary.

If three vertices touch the left boundary, then let $v$ be the “middle” one,
i.e., neither of the left corners of $\cal R$ belong to $P(v)$. Otherwise
choose $v$ arbitrarily among the two vertices touching the left boundary. Let
$w\neq v$ be a vertex that touches the right boundary. Insert a new column on
the left and assign it entirely to $P(v)$, and a new column on the right and
assign it entirely to $P(w)$. Any vertex that previously touched the boundary
continues to do so, because it either occupied a corner of $\cal R$ (then it
remains on the boundary) or it was vertex $v$ (which touches the new boundary
on the left).

Finally we apply Claim 1 and 2 to make interior junctions horizontal and make
vertical sides not on the same boundary have different $x$-coordinates.
Neither operation affects incidences with the boundary, and the claim holds. ∎

We are now ready to extract the homotopy as described before. We may assume
that exactly three vertices touch the boundary; they form a triangular face
$f$ in $G$ which we declare to be the outer-face. Set $u\neq v$ to be the
vertices on the left and right boundary. As in the definition of homotopy, let
$s(uv)$ and $t(uv)$ be the subpaths of $G$ between $u$ and $v$ on $f$. By
definition, they consist of the vertices occupying the top and and bottom
boundaries of $\cal R$.

Let the contact representation now have $x$-range
$[-\tfrac{1}{2},W+\tfrac{1}{2}]$. For $i=0,\dots,W$, define $h_{i}$ to be the
vertices whose polygons intersect the vertical line $\\{x=i\\}$, enumerated
from top to bottom. Clearly $h_{0}=\langle u\rangle$, $h_{W}=\langle
v\rangle$, and any $h_{i}$ begins on $s(uv)$ and ends on $t(uv)$. It remains
to show that for $0\leq i<W$ going from $h_{i}$ to $h_{i+1}$ is one of the
permitted moves. Consider some vertical side $e$ that has $x$-coordinate
$i+\tfrac{1}{2}$ (if there is none then $h_{i}=h_{i+1}$ and we are done). Note
that the change from $h_{i}$ to $h_{i+1}$ affects _only_ vertices that are
incident to $e$ or participate in junctions at the ends of $e$, because no
other vertical side has $x$-coordinate $i+\tfrac{1}{2}$ (by $0\leq i<W$ and
assumption) and so there is no difference between the curves elsewhere. Let
$P(x)$ and $P(y)$ be the polygons whose sides contain $e$, with $P(x)$ left of
$e$.

We distinguish cases by what the ends of $e$ are:

  1. (a)

Both ends of $e$ are corners, and the adjacent horizontal sides go in opposite
directions. Then $h_{i}=h_{i+1}$ and we are done. See Fig. 5(a).

  2. (b)

Both ends of $e$ are corners, and the adjacent horizontal sides go in the same
directions. Say they both go right and note that they are interior, else this
would be a junction not a corner. Therefore the vertical line to the right of
$e$ intersects $P(x)$ in two intervals, contradicting $x$-monotonicity. (Note
that in fact we can get from $h_{i}$ to $h_{i+1}$ with a spike or unspike.)
See Fig. 5(b).

  3. (c)

One end of $e$ is a corner, the other is an interior junction (hence
horizontal by assumption). Let $z$ be vertex other than $x,y$ at the junction,
so we have a face $x,y,z$. The change from $h_{i}$ to $h_{i+1}$ is to replace
$x$-$z$ by $x$-$y$-$z$ or $y$-$x$-$z$ by $y$-$z$; this is a face-flip. See
Fig. 5(c).

  4. (d)

One end of $e$ is a corner, the other is an exterior junction. By the
assumptions, this exterior junction is horizontal, and its two vertices, say
$v$ and $w$, belong to $t(uv)$ if the junction is on the top boundary, and to
$s(uv)$ if the junction is on the bottom boundary. The corresponding change is
to replace $v$ by $v$-$w$ at the end of the curve, or vice versa; this is a
boundary-move. See Fig. 5(d).

  5. (e)

Both ends of $e$ are interior junctions, which we know to be horizontal. Let
$z$ and $t$ be the third vertices at these junctions. The change is to replace
$t$-$x$-$z$ by $t$-$y$-$z$; this is an edge-slide along $(x,y)$. See Fig.
5(e).

  6. (f)

Both ends of $e$ are junctions, one is interior (hence horizontal) while the
other is exterior. As before, by assumption, this exterior junction is
horizontal, and its two vertices, say $v$ and $w$, belong to $t(uv)$ if the
junction is on the top boundary, and to $s(uv)$ if the junction is on the
bottom boundary. The change is to replace $t$-$v$ by $t$-$w$; this is a
boundary edge-slide. See Fig. 5(f).

  7. (g)

Both ends of $e$ are exterior junctions. This corresponds to a bridge in $G$,
contradicting the fact that it is triangulated.

Therefore we only use allowed moves and have found a homotopy. It is simple
since polygons are $x$-monotone. The height equals the maximum number of
intersected polygons, which is no more than the height of the contact
representation, hence the height of the grid representation. ∎

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5: The cases of how curves change.

Putting the two results together, the homotopy-height and the simple grid-
major-height are exactly the same value.

###  3.2 Homotopy height and grid-major height

One can reasonably argue that the notion of grid-major height is more natural
than simple grid-major height. Furthermore, it is trivially a minor-closed
quantity, which is advantageous from a structural and algorithmic point of
view. In this subsection we show that grid-major height can also be
interpreted as the height of a more general notion of homotopy than the one
defined in the preliminaries. Compared to the case of simple homotopies, in a
(non-simple) homotopy, we remove the hypothesis that the curves are simple and
we allow two new moves, spikes and unspikes, leveraging this non-simplicity.
Fig. 5(b) illustrates a spike. Furthermore, the conditions are slightly
relaxed: the endpoints are allowed to move along an edge instead of a face,
and the starting and ending vertices are allowed to be the same. This could
allow “trivial” homotopies (for example an empty one, idling on a single
vertex), and thus we add a new condition on topological non-triviality to
disallow those.

The equality with grid-major height gives a non-trivial algorithmic corollary:
since grid-major height is obviously a minor-closed quantity, it is computable
in time FPT in the output, and thus this is also the case for homotopy height.
The proofs are very similar to those in the previous subsection and we only
focus on the salient differences.

Precisely, a _(discrete) homotopy_ is defined for a planar triangulated graph
$G$ with either a fixed outer-face $\\{u,v,w\\}$, or a _fixed outer-edge_ ,
which consists of choosing an edge of the graph, doubling it, and fixing the
new degree $2$ face between these two edges as the outer face of $G$. It
consists of a sequence $h_{0},\dots,h_{W}$ of walks in $G$ (we call these
_curves_) such that:

  1. 1.

$h_{0}$ and $h_{W}$ are trivial curves at two vertices of the outer-face, say
$u$ and $v$ ($u=v$ is allowed).

  2. 2.

The vertices $u$ and $v$ partition the outer-face into two subpaths $s(uv)$
and $t(uv)$. For $0\leq i\leq W$, the curve $h_{i}$ starts on $s(uv)$ and ends
on $t(uv)$.

  3. 3.

For all $0\leq i<W$ we can obtain $h_{i+1}$ from $h_{i}$ with a face-flip,
spike, unspike, edge-slide, a boundary-move or a boundary-edge-slide; see Fig.
6.

  4. 4.

$h$ is _topologically non-trivial_ (see below).

Figure 6: The last type of homotopy move.

A _spike_ consists of picking some edge $e=(x,y)$ where $x\in h_{i}$ and
replacing $x$ by the subsequence $x$-$y$-$x$ (traversing $e$ twice). An
_unspike_ is the reverse operation of a spike, i.e., replace $x$-$y$-$x$ by
$x$. The other moves are defined in Section 2.

The topological non-triviality hypothesis is there to exclude some trivial
instances of homotopies in the case $u=v$, for example the empty homotopy
starting at $u$ and finishing at $v=u$. In order to do so, we define an
algebraic flipping number for each face. Assume without loss of generality (by
reversing the embedding if necessary) that the vertices and edges on the
outer-face are ordered $u,t(uv),v,s(vu)$ in clockwise order. In particular, if
they contain at least two edges, the paths $t(uv)$ and $s(vu)$ go clockwise.
Then whenever a face is flipped with a move (either using a face-flip or an
edge-slide) between $h_{i}$ and $h_{i+1}$, this flip is called _positive_
(respectively _negative_) if the face lies to the right (respectively to the
left) of the edge used to flip it (using the direction of the edge induced by
the path $h_{i}$). The _algebraic flipping number_ of each face is defined to
be the sum of the positive flips minus the sum of the negative flips over all
the moves of a homotopy. A homotopy is _topologically non-trivial_ if each
face except the outer face has algebraic flipping number one. It is easy to
prove that a simple homotopy is always topologically non-trivial. Furthermore,
it can be proved that when $u\neq v$, this hypothesis is always satisfied (but
since we embedded it in the definition, we will not need this fact).

As in the simple case, the _height_ of a homotopy is the length of the longest
path $h_{i}$, counting as path-length the number of vertices, and
$\textit{Hh}(G)$ is the minimum height of a homotopy over all the possible
choices of outer-faces and outer-edges.

######  Lemma 3.

For any triangulated planar graph we have $gmh(G)\leq\textit{Hh}(G)$.

###### Proof.

The proof proceeds similarly to the proof of Lemma 1. There are two main
differences: we need to explain how to handle the edge-spikes, and the proof
that we obtain a grid-major representation is more involved, since we do not
have simplicity to leverage. We first explain how to build the grid and defer
the proof that it is a grid-major representation to the end of the proof.

The proof starts exactly the same way as that of Lemma 1. We build inductively
a contact representation following the homotopy, and we use exactly the same
notations. Having built a contact representation $\Gamma_{i}$, we explain how
to expand $\Gamma_{i}$ rightwards to represent $h_{i+1}$. Note that since the
grid-major representation may not be simple, the polygons may not be
$x$-monotone, and thus may have several right and left boundaries.

  * •

The cases of edge-slides, boundary edge-slides, boundary moves and face flips
are identical to the other proof.

  * •

Let us assume that $h_{i+1}$ was obtained from an edge spike (the unspike case
is symmetric and is handled identically) along an edge $(x,y)$, i.e., $h_{i}$
contained $x$ which got replaced by $x$-$y$-$x$ in $h_{i+1}$. So $|h_{i}|\leq
k-2$ which implies that at least one polygon $P(d)$ for some $d\in h_{i}$ has
height at least $3$ on one of its right boundaries, or at least two polygons
$P(d_{1})$ and $P(d_{2})$ (possibly equal) have height at least $2$ on one of
their right boundaries. We insert an (upward or downward) staircase that
shifts this extra height to $x$ while keeping all polygons of $h_{i}$ on the
right boundary. This may take up to $2k$ units of width but does not affect
the height. Now $P(x)$ has height $3$ on the right boundary, and we can start
a $1$-pixel high polygon $P(y)$ for the vertex $y$ right inbetween.

It remains to prove that this is a valid grid-major representation. This is
not true in general: it is easy to build examples (for example by spiking an
edge and immediately unspiking it) where the sets of vertices with a common
label in the grid representation are not connected. What we will show is that
we can assume that the homotopy we work with has a special property called
_monotonicity_ , which requires that:

  1. 1.

each curve $h_{i}$ does not cross itself, i.e., it can be locally perturbed in
the plane to be simple (in the topological sense),

  2. 2.

for any $0\leq i<W$, the move connecting $h_{i}$ to $h_{i+1}$ uses an edge or
a face lying to the right of $h_{i}$, for the orientation induced by the
ordering of the vertices in a curve from $s(uv)$ to $t(uv)$.

The second hypothesis implies that the faces are only flipped positively, and
thus each face is flipped exactly once, but it is stronger since it also
constrains edges. For example, while a spiked path is non-simple in the graph-
theoretical sense, it can be locally (topologically) perturbed to a simple
curve, and is thus allowed in a monotone homotopy. On the other hand, spiking
an edge and immediately unspiking it is forbidden, since the unspike goes in
the opposite direction of the spike. The following claim will be proved in
Lemma 4.

######  Claim 6.

If there exists a discrete homotopy of $G$ of height at most $k$, there exists
a monotone discrete homotopy of $G$ of height at most $k$.

Assuming that the homotopy we started with is indeed monotone, we can now
prove that our construction yields a valid grid-major representation. This is
intuitive but somewhat technical to prove. Denote by $G^{*}$ the graph dual to
$G$, and view this dual graph as a _cross-metric surface_ (see, e.g., [9]),
i.e., it provides a metric for the curves crossing it _transversely_ by
counting the number of edges that each edge crosses. As is customary for
cross-metric surfaces, we puncture the vertex dual to the outer face, so that
the cross-metric surface is a topological disk $D$ whose boundary is made of
the two subpaths $s(uv)$ and $t(uv)$. Discrete homotopies are defined on
cross-metric surfaces by dualizing the moves described in Section 2, or see
[7] for more background on discrete homotopies on cross-metric surfaces.

Our monotone homotopy induces a (dual) discrete monotone homotopy with respect
to $G^{*}$. Now, the advantage of working with the cross-metric setting is
that we can realize the slight perturbations of the curves $h_{i}$ to make
them simple. Furthermore, we can interpolate continuously inside each homotopy
move in the natural way to obtain a _continuous homotopy_ : a continuous map
$h:[0,1]\times[0,1]\rightarrow D$ where $D$ is the disk bounded by the outer
face, $h(0,\cdot)$ and $h(1,\cdot)$ are infinitesmal paths in the dual faces
$u^{*}$ and $v^{*}$, and $h(\cdot,0)\in s(uv)$ and $h(\cdot,1)\in t(uv)$. By
the monotonicity assumption, the curves $h(t,\cdot)$ are all simple and
locally disjoint for small perturbations of $t$. This implies that the map $h$
is locally injective and therefore a local homeomorphism. The topological non-
triviality hypothesis ensures that $h$ has topological degree one, and thus it
is a homeomorphism into its image $D$. The preimages of the faces of $G^{*}$
in $D$ are therefore connected sets in $[0,1]\times[0,1]$. Now the proof
follows by observing that the contact representation is exactly a discrete
version of these connected sets. Indeed, the labels on the columns of the
contact representation mirror the faces crossed by the curves $h(\cdot,t)$,
and the construction associated to each move was made to ensure that the
connectedness of the labels between two moves in $h$ is faithfully represented
by the connectedness of the grid between the two columns.

∎

To conclude the proof, we establish the needed monotonicity property in the
following lemma. The gist of it is that it was proved in [7] that optimal
homotopies can be assumed to be monotone, but for a slightly different notion
of discrete homotopy which did not allow edge slides. In order to use the
result of [7], we therefore first need to change the graph $G$ into a
different one. Note that since allowing edge-slides change the value of the
height by at most $1$, the reader content with this small leeway can apply
directly the results of [7] to obtain monotonicity.

######  Lemma 4.

If there exists a discrete homotopy of $G$ of height at most $k$, there exists
a monotone discrete homotopy of $G$ of height at most $k$.

###### Proof.

We denote by $R(G)$ the _radial graph_ of $G$, which is obtained by putting a
vertex in the middle of each inner face, connecting each pair of vertices
lying on adjacent pairs (vertex,face), removing the inner edges and
subdividing each outer edge once. The resulting graph $R(G)$ is a bipartite
quadrangulation, and discrete homotopies on $R(G)$ are defined with discrete
moves as in $G$: now the faces of degree $4$ can be flipped, and that there
are no edge-slides since these do not make sense in a quadrangulation (see
e.g.,the introduction of [7] for an inventory of the discrete homotopy moves
in general non-triangulated graphs). The outer face is not allowed to be
flipped, and for any subdivided outer edge $e$, we allow a _double boundary
edge-slide_ to slide in one step over the two corresponding edges in $R(G)$.

We claim that any discrete homotopy of $G$ of height at most $k$ between two
vertices $u$ and $v$ induces a discrete homotopy of $R(G)$ of height at most
$2k$ between the vertices $u$ and $v$ of $R(G)$. Indeed, any edge $e$ in $G$
can be pushed on either side to yield a $2$-edge path going through either of
the two adjacent faces of $e$ (these perturbations are called _vibrations_ in
[16]). Furthermore, the choice of which way to push does not matter since one
can switch between both ways without occuring any increase in the height by
doing a face-flip at the face of $R(G)$ corresponding to $e$. Now, simply
observe that a spike, face-flip, edge-slide, boundary-move and boundary edge-
slide in $G$ corresponds respectively to two consecutive edge spikes, one edge
spike, one face-flip, two boundary-moves and one double boundary edge-slide in
$R(G)$.

Conversely, any discrete homotopy of $R(G)$ of height at most $2k$ between two
vertices $u$ and $v$ that are also vertices in $G$ induces a discrete homotopy
of $G$ of height at most $k$ between $u$ and $v$. Indeed, the graph $R(G)$ is
bipartite and thus any curve in $R(G)$ can be decomposed into pairs of
adjacent edges connecting vertices of $G$. Each of these pairs can be pushed
towards $G$ by doing the reverse of the vibrations described above, and the
dictionary between moves of $G$ and $R(G)$ can be read in reverse to extract a
discrete homotopy of $G$ of height at most $k$ between $u$ and $v$.

Now the proof of Lemma 4 simply follows from Theorem 4 of [7] showing that
optimal homotopies can be assumed to be monotone. More precisely, while
Theorem 4 handles homotopies between two cycles forming the boundary of an
annulus, the reduction of Proposition 13 in that paper explains how to simply
obtain a similar monotonicity property in the setting that we are working with
in this paper, where curves are paths with moving endpoints on two boundaries.
This reduction naturally relies on the double boundary-edge-slide move,
corresponding to a face-flip with the new vertex on the outer face. ∎

We now prove the reverse inequality.

######  Lemma 5.

For any triangulated graph we have $\textit{Hh}(G)\leq gmh(G)$.

###### Proof.

Here as well, the proof is very similar to that of Lemma 2. We will reuse the
parts that can be used verbatim, but need to do some slight changes at many
places. We start from a grid-major representation which we interpret as a
contact representation, and use the same notations as in Lemma 2: for any
vertex $z$, $P(z)$ is an orthogonal polygon (but it may not be $x$-monotone).

We will build the homotopy from this contact representation by intersecting it
with the vertical lines, but must first modify it to satisfy additional
properties.

Claim 1 carries verbatim and the proof becomes even easier: since there are no
$x$-monotonicity constraints, any of the two ways works. Claim 2 also carries
verbatim, so all vertical sides have distinct $x$-coordinates unless they are
on the left or right boundary. Also observe that no polygon $P(x)$ can attach
at the left boundary in two disjoint sides (else $x$ would be a cutvertex), so
the leftmost side of a polygon $P(x)$ is now defined even though $P(x)$ need
not be $x$-monotone. Claim 4 used Claim 3, for which $x$-monotonicity was
crucial, so we prove a weaker version of this claim in a different fashion.

######  Claim 7.

We may assume that the union of the four boundaries consists of either two or
three vertices, while preserving the previous assumption.

###### Proof.

First observe that there cannot be more than three different vertices
occupying the left, top, right, and bottom boundaries of $\cal R$, since $G$
is triangulated.

We first assume that a single vertex $u$ occupies the entire left, top right
and bottom boundaries of $\cal R$. Let $v\neq u$ be a vertex that minimizes
the $x$-coordinate of its leftmost side $e_{v}$. Side $e_{v}$ lies in the
interior by $v\neq u$, and cannot contain a junction (not even at its ends),
else $v$ would touch a boundary or some vertex $w\neq u,v$ would be farther
left than $v$. Therefore both ends are corners, and convex for $P(v)$ since
$e_{v}$ is leftmost. Removing everything to the left of the line $\ell$
through $e_{v}$ then gives a contact-representation of the same graph, since
$P(u)$ remains connected (via the top, right and bottom boundary) and the
adjacency $(u,v)$ is realized at the horizontal sides. Therefore we can assume
that at least two vertices occupy the four boundaries.

If necessary, we reapply the previous claims to ensure the absence of vertical
junctions and of two inner vertical sides not on the same boundary having the
same $x$-coordinates. ∎

######  Claim 8.

We may assume that exactly one vertex touches the left boundary and exactly
one vertex different touches the right boundary, while preserving the previous
assumptions.

###### Proof.

Let us assume that there is more than one vertex touching the left boundary.
If all the outer vertices touch the left boundary and one of them, say, $w$
occupies both the top left and bottom left corner, then it also occupies the
entire top, right and bottom boundaries. Without loss of generality, assume
that $u\neq w$ has a minimal $y$-coordinate on the leftmost column. Then we
can replace all the pixels below that vertex by $u$. This does not break
connectivity of $v$ and also does not remove any adjacencies: indeed, since
there are no interior vertical junctions, the part of $P(w)$ on the leftmost
column was adjacent to at most one polygon which was not $P(u)$, and it is
still adjacent to it after the replacement.

Thus we can assume that the two vertices adjacent to the top left and bottom
left corners are distinct. If there is a third vertex adjacent to the left
boundary, choose it. Otherwise, choose arbitrarily one of the vertices on the
left boundary. Denoting by $u$ the chosen vertex, we append a new column to
the left of $\cal R$ and we extend $u$ to the left so that it fills entirely
that column. This does not break any boundary-adjacency since the vertices
that were on the top left and bottom left corners are still adjacent to the
boundary.

If necessary, repeat on the right boundary, and reapply the previous claims to
remove interior junctions and interior vertical sides not both on the same
boundary and with the same $x$-coordinates.

∎

Note that in contrast to Claim 5, we do not prove that the two vertices can be
assumed to be different.

We can now build the homotopy exactly as in the proof of Lemma 2. If there are
three vertices on the four boundaries of the contact representations, we fix
these three vertices to be the outer-face. If there are two vertices, they
form the outer-edge. Then the only change is case $(b)$, which is now allowed:

  * (b)

Both ends of $e$ are corners, and the adjacent horizontal sides go in the same
direction. Say that they both go right, the other case being symmetric.
Denoting by $P(x)$ the locally convex polygon and by $P(y)$ the other one,
this corresponds to a spike: the change from $h_{i}$ to $h_{i+1}$ is to
replace $y$ by $y-x-y$.

Finally, in the contact representation, the faces correspond to junctions, and
when the induced homotopy is a face-flip or an edge-slide, the faces are swept
positively. Since there are no loops nor multiple edges (except perhaps the
outer-edge), each junction appears once, and thus each face is swept once.
Therefore the homotopy is topologically non-trivial, which concludes the
proof.

∎

Since grid-major height is trivially minor-closed, testing whether a graph has
grid-major height at most $k$ can be decided in time $O(f(k)|G|^{3})$ by
testing the (unknown!) forbidden minors, which are in finite number by
Robertson-Seymour theory. Because minor testing can be expressed in second-
order logic, and the graphs of bounded grid-major height have bounded
pathwidth, it follows from Courcelle’s theorem [10] that these minors can be
tested in linear time. Therefore, the two previous lemmas give us the
following corollary.

######  Corollary 1.

We can decide whether a triangulated planar graph has homotopy height
$\textit{Hh}(G)$ at most $k$ in time $O(f(k){\mathit{p}oly}(|G|))$ for some
computable function $f(k)$. In particular, the problem of computing the
homotopy height is FPT when parameterized by the output.

##  4 Strictness examples

We have now given all the inequalities needed for Equations 1 and 2. In this
section, we argue that many of these inequalities are strict by exhibiting
suitable planar triangulations.

###  4.1 Pathwidth vs. Grid-major height

Recall that $\textit{pw}(G)\leq\textit{GMh}(G)$ since a grid of height $k$ has
pathwidth $k$. We now show that this is strict.

######  Lemma 6.

There exists a planar triangulated graph $G$ with $pw(G)=3$ and
$\textit{GMh}(G)\in\Omega(n)$.

###### Proof.

Graph $G$ is the “nested triangles graph” from [11, 18], consisting of $n/3$
triangles that are stacked inside each other and connected in such a way that
the result is triangulated and has pathwidth 3. See Fig. 7(a). For any choice
of outer-face there are at least $n/6$ triangles that remain stacked inside
each other. Therefore $op(G)\geq n/6$ and $\textit{GMh}(G)\geq n/3-1$. ∎

###  4.2 Grid-major height, simple grid-major height and outer-planarity

Directly from the definition we have $\textit{GMh}(G)\leq\textit{sGMh}(G)$. We
now show that this can be strict.

######  Lemma 7.

There exists a planar triangulated graph that has grid-major height at most 4,
but simple grid-major-height $\Omega(n)$.

###### Proof.

Consider graph $G$ in Fig. 7(b), which is taken from [4]. It is a minor of the
graph $G^{\prime}$ in Fig. 7(c), which has a straight-line drawing of height
4. Therefore $\textit{sGMh}(G^{\prime})\leq\textit{SLh}(G^{\prime})\leq 4$,
which implies $\textit{GMh}(G)\leq 4$ since $G$ is a minor of $G^{\prime}$.

(a)

(b)

(c)

Figure 7: (a) Nested triangles. (b) The graph from [4]. (c) A graph of which
it is a minor.

We claim that $\textit{sGMh}(G)\in\Omega(n)$, and prove this by arguing that
$\textit{sHh}(G)\in\Omega(n)$; the two parameters are the same. Crucial to our
argument is that for many vertex-pairs any path connecting them _without_
using $x$ has length $\Omega(n)$; we will find such a path from the curves in
a homotopy.

So consider a simple discrete homotopy of height $k$, and let $f$ be the face
it uses as the outer-face (it need not be the outer-face used in Fig. 7(b)).
Graph $G\setminus x$ is connected, but $d_{G\setminus x}(a,b)=(n-3)/2$. Define
$d_{a}$ to be the minimum distance in $G\setminus x$ from $a$ to some vertex
on face $f$, and similarly define $d_{b}$. Since $f$ is a triangle, we can
combine two such shortest paths to obtain a path from $a$ to $b$ in
$G\setminus x$ of length at most $d_{a}+d_{b}+1$, therefore (up to renaming)
$d_{a}\geq(n-5)/4$.

In particular, for $n\geq 7$ vertex $a$ is not on $f$. Let $h_{i}$ be a curve
of the homotopy that contains $a$ and note that it begins and ends on $f$.
Split $h_{i}$ into two paths $\pi_{1}$ and $\pi_{2}$ at vertex $a$. These
paths are vertex-disjoint except for $a$ since the homotopy is simple. At most
one of these paths contains $x$. Say $\pi_{1}$ does not contain $x$ and hence
connects $f$ to $a$ without visiting $x$. Therefore $|\pi_{1}|\geq
d_{a}\geq(n-5)/4$, and the height of the homotopy is $\Omega(n)$. ∎

In particular, Lemma 7 provides a different (and in our opinion more
accessible) proof that the graph in Fig. 7(b) requires $\Omega(n)$ height in
any straight-line drawing [4].

###  4.3 Grid-major height and graph-drawing height

Recall that $\textit{sGMh}(G)\leq\textit{VRh}(G)=\textit{SLh}(G)$ since a
visibility representation can easily be turned into a simple grid-major
representation. We now show that this is strict. We need a definition.

A graph $G$ is called a _series-parallel graph (with terminals $s$ and $t$)_
if it either is an edge $(s,t)$, or if it was obtained via a combination in
series or in parallel. Here, a _combination in series_ takes two such graphs
$G_{i}$ with terminals $s_{i},t_{i}$ for $i=1,2$, and identifies $t_{1}$ with
$s_{2}$. A _combination in parallel_ also takes two such graphs and identifies
$s_{1}$ with $s_{2}$ and $t_{1}$ with $t_{2}$. It is well-known that such
graphs are planar.

######  Lemma 8.

Any series-parallel graph has a simple grid-major representation of height
$O(\log n)$.

###### Proof.

Roughly speaking, we “bend” some of the bars in the visibility representations
of series-parallel graphs from [4] to guarantee logarithmic height. Formally
we proceed by induction on $m$, and prove that if $G$ has $m$ edges, then it
has a simple grid-major representation of height $2\lceil\log m\rceil+2$ where
the top-right corner is labelled $s$ and the bottom-right corner is labelled
$t$. Furthermore, any column that contains $s$ and/or $t$ also has its
topmost/bottommost grid point labelled with $s$/$t$. In the base case $G$ is
an edge $(s,t)$ and we can simply label a $1\times 2$ grid with $s$ and $t$.

Assume first that $G$ was obtained by parallel combinations of $G_{1}$ and
$G_{2}$. Consider Fig. 8. After renaming we may assume $m(G_{2})\leq
m(G_{1})$, so $m(G_{2})\leq m/2$. Recursively obtain a grid-major
representation $\Gamma_{1}$ of $G_{1}$, and pad it with duplicate rows (if
needed) so that it has height $2\lceil\log m\rceil+2$. Recursively obtain a
grid-major representation $\Gamma_{2}$ of $G_{2}$ of height at most
$2\lceil\log(m(G_{2})\rceil+2\leq 2\lceil\log m\rceil$. Place $\Gamma_{2}$ to
the right of $\Gamma_{1}$, leaving the top and bottom row unused. Label the
points above $\Gamma_{2}$ with $s$ and the points below $\Gamma_{2}$ with $t$
and verify all conditions.

Now assume that $G$ was obtained by a series combination of two graphs
$G_{1},G_{2}$ where $G_{1}$ had terminals $s,x$ and $G_{2}$ had terminals
$x,t$. We assume $m(G_{2})\leq m(G_{1})$, the other case is symmetric.
Recursively obtain grid-major representations $\Gamma_{1}$ and $\Gamma_{2}$ of
$G_{1}$ and $G_{2}$ of height $2\lceil\log m\rceil+2$ and $2\lceil\log
m\rceil$ as before. Place $\Gamma_{2}$ to the right of $\Gamma_{1}$, leaving
the top two rows unused, and leaving one column between the representations
unused. All grid-points in this column, as well as in the row above
$\Gamma_{2}$, are labelled $x$. (In particular, the grid-points labelled $x$
form an “$S$-shape” as if we had bent a bar in the middle.) The second row
above $\Gamma_{2}$ is labelled $s$ so that again the top-right corner has $s$.
One easily verifies that this is a simple grid-major representation of $G$
with height $2\lceil\log m\rceil+2\in O(\log n)$. ∎

Figure 8: Grid-major representations of series-parallel graphs.

######  Theorem 4.1.

There exists a planar triangulated graph $G$ for which $\textit{sGMh}(G)\in
O(\log n)$ but $\textit{SLh}(G)\in\Omega(2^{\sqrt{\log n}})$.

###### Proof.

We know from Frati [17] that for any $N$, there exists a series-parallel graph
$G_{N}$ with $n\geq N$ vertices for which any planar straight-line drawing has
height $\Omega(2^{\sqrt{\log n}})$. Let $\Gamma_{N}$ be a simple grid-major
representation of $G^{\prime}$ of height $O(\log n(G^{\prime}))$. Let
$\Gamma_{N}^{\prime}$ be the simple grid-major representation obtained by
adding new grid-lines on all four sides of $\Gamma_{N}$, and by labelling the
top and right with a new vertex $s^{\prime}$ and the remaining gridpoints with
another new vertex $t^{\prime}$. If $\Gamma_{N}^{\prime}$ induces a face of
degree 4, then one interior face of the grid has four distinct labels; we can
duplicate the left column and change one label so that an extra edge is added
to the represented graph. The final result is a grid-representation of a
planar graph $G$ that is triangulated except its outer-face is a duplicate
edge $(s^{\prime},t^{\prime})$. After deleting one copy, we get the desired
graph: $G$ has $n+2$ vertices, a simple grid-major representation $\Gamma$ of
height $O(\log n)$, and contains $G_{N}$ as a subgraph, so any straight-line
drawing of $G$ has height $\Omega(2^{\sqrt{\log n)}})$. ∎

######  Lemma 9.

There exists a planar triangulated graph $G$ with $op(G)=2$ but
$\textit{GMh}(G)\in\Omega(\log n)$.

###### Proof.

Take any tree $T$ that has pathwidth $\Omega(\log n)$, for example a complete
binary tree. This is an outer-planar graph; add edges to the graph while
maintaining outer-planarity until the graph is maximal outer-planar, hence
2-connected and all faces except the outer-face are triangles. Insert a new
vertex in the outer-face and make it adjacent to all other vertices; the
result (see Fig. 9) is a triangulated planar graph $G$ with outer-planarity 2
and $\textit{GMh}(G)\geq\textit{pw}(G)\geq\textit{pw}(T)\in\Omega(\log n)$. ∎

Figure 9: A graph with $op(G)=2$ but $\textit{GMh}(G)\in\Omega(\log n)$ (Lemma
9): a complete binary tree (thick black edges), augmented to become maximal
outer-planar (dashed blue edges), with a new vertex added in the outer face
(thin red edges).

##  5 Algorithms for simple grid-major height

In this section we develop a fixed-parameter tractable algorithm for simple
grid-major height. Our algorithm uses Courcelle’s theorem to recognize the
contact-representations of simple grid-major representations. To do this, we
prove that (for fixed values of the height) the following properties of these
contact-representations all hold:

  * •

The contact-representation can be assumed to have only a bounded number of
distinct shapes of boundary between pairs of adjacent orthogonal polygons
(Lemma 15).

  * •

The realizability of a single orthogonal polygon, with specified shapes for
each of the boundaries with its adjacent polygons, can be expressed in logical
terms (Claim 9).

  * •

A contact-representation with specified boundary shapes exists if and only if
each of its polygons is realizable, independently of the others (Lemma 17).

###  5.1 Boundary shapes

We will assume throughout this section that a contact-representation of height
$h$ has vertices with integer $y$-coordinates ranging from $0$ to $h$.
However, we allow the $x$-coordinates to be arbitrary real numbers rather than
requiring them to be integers. This relaxation has no effect on the existence
of contact-representations, but is convenient for us in allowing parts of the
representation to be transformed by arbitrary monotone transformations of
their $x$-coordinates (keeping the $y$-coordinates unchanged).

We define the _shape_ of the boundary $B$ of two polygons in a simple
orthogonal contact-representation to be a polygonal chain $C$ with the
following properties:

  * •

The line segments of $C$ correspond one-to-one with the line segments of $B$,
with the same orientations. (We will call these _segments_ for short, to
distinguish them from the edges of the underlying maximal planar graph.)

  * •

All $y$-coordinates (heights) of vertices in $C$ equal the coordinates of the
corresponding vertices in $B$.

  * •

The $x$-coordinates of vertices in $C$ are non-negative integers.

  * •

The $x$-coordinate of the leftmost vertex (or vertices) in $C$ equals zero.

  * •

When two vertices in $C$ are connected by a horizontal segment in $C$, their
$x$-coordinates differ by $\pm 1$.

These properties define a unique shape for each polygon-polygon boundary,
invariant under $x$-monotone transformations of the boundary. Our goal in this
section is to show that the number of distinct shapes can be bounded by a
function of the height $h$ of the contact-representation.

######  Lemma 10.

In a simple contact-representation, if two polygons $X$ and $Y$ share a non-
vertical boundary, then one of them is consistently above or below the other
one at all $x$-coordinates shared by both polygons.

###### Proof.

Suppose otherwise, that at $x$-coordinate $x_{1}$ polygon $Y$ is below polygon
$X$, and at $x$-coordinate $x_{2}$ polygon $Y$ is above $X$. Choose points
$p_{i}$ in $X$ and $q_{i}$ in $Y$ (for $i\in\\{1,2\\}$) with points $p_{i}$
and $q_{i}$ having $x$-coordinate $x_{i}$ respectively. By the assumption that
the contact-representation is simple, there exists an $x$-monotone curve $P$
within $X$ from $p_{1}$ to $p_{2}$, and another $x$-monotone curve $Q$ within
$Y$ from $q_{1}$ to $Q_{2}$. These curves lie within disjoint polygons, so
they cannot cross each other. However at $x_{1}$, $P$ is below $Q$, and at
$x_{2}$, $Q$ is below $P$. by the intermediate value theorem there must be an
$x$-coordinate between $x_{1}$ and $x_{2}$ where they cross. This
contradiction shows that inconsistent above-below relations are impossible. ∎

Define the _extended shape_ of a polygon-polygon boundary to be its shape as
described above, augmented with a single bit of information that (according to
Lemma 10) describes which of the two adjacent polygons is above and which is
below. (For boundaries that have no horizontal segments, we instead use the
same bit of information to specify which polygon is to the left of the
boundary and which is to the right.)

Given two adjacent polygons $X$ and $Y$, with $X$ above $Y$, consider the
sequence of integer heights of points along the boundary between $X$ and $Y$,
with consecutive duplicates removed, not including the two points where the
boundary begins and ends. Define the sequence of extrema of boundary $XY$ to
be the subsequence of heights that are either local minima or local maxima of
this sequence.

######  Lemma 11.

In any sequence of extrema, local minima and local maxima alternate with each
other.

###### Proof.

The extrema are the points where the sequence of differences of heights
between consecutive elements of the height sequence changes sign. At a local
maximum the sequence of differences changes sign from positive to negative and
at a local minimum it changes from negative to positive. When it changes sign
in one direction it cannot change in the same direction until it has changed
back in the other direction. ∎

We define the _bend complexity_ of a contact-representation to be the sum,
over all pairs of adjacent polygons, of the number of bends in the boundary
between the two polygons. Again, we do not count the endpoints of the boundary
as bends.

######  Lemma 12.

In a simple contact representation of minimum bend complexity for its height,
it is not possible to have four consecutive extrema in which the outer two
extrema are the maximum and minimum of the four.

Figure 10: Simplifying a boundary that violates Lemma 12

###### Proof.

Proof: Whenever this happens, we could apply a monotonic transformation to the
parts of the contact representation above this portion of the XY-boundary,
leaving the parts below the boundary untransformed, emptying the shallower of
the two pockets in the upper region and allowing the border to be simplified;
see Figure 10. ∎

######  Lemma 13.

Let $B$ be the boundary between polygons $X$ and $Y$ in a simple contact-
representation of minimum bend complexity for its height. In the sequence of
extrema of heights of the points in $B$, each pair of a global maximum and
global minimum of height must be adjacent to each other; hence there can be at
most three global extrema, two maxima and one minimum or two minima and one
maximum. The local maxima must strictly increase from the start to the first
global maximum and strictly decrease after the last global maximum.
Symmetrically, the local minima must strictly decrease from the start to the
first global minimum and decrease after the last global minimum.

Figure 11: Schematic view of the extrema of heights in the boundary of two
polygons of a simple contact-representation of minimum bend complexity,
according to Lemma 13

###### Proof.

Immediately following the global maximum, the next local maximum must be non-
increasing (by global maximality) This forces the next two local minima to be
non-decreasing (by Lemma 12), which forces the next two local maxima to be
non-increasing, etc. So by induction the maxima must be non-increasing and the
minima must be non-decreasing from the global maximum to the end of the
sequence. The same argument applies symmetrically between the global maximum
and the start of the sequence. ∎

For a schematic view of a sequence obeying Lemma 13, see Figure 11.

######  Lemma 14.

In a simple contact representation of minimum bend complexity for its height
$h$, the number of bends on the boundary between any two polygons is
$O(h^{2})$.

###### Proof.

By Lemma 13 it can have $O(h)$ local extrema of height, and between any two
local extrema there can only be $O(h)$ bends. ∎

######  Lemma 15.

In a simple contact representation of minimum bend complexity for its height
$h$, the number of distinct extended shapes of boundaries between any two
polygons is $2^{O(h^{2}\log h)}$.

###### Proof.

By Lemma 14 the number of line segments along the boundary is $O(h^{2})$, and
each has $O(h)$ possibilities for its height and orientation. The extra bit of
information needed to specify the extended shape from the shape does not
affect the result of this calculation. ∎

###  5.2 Single-polygon realizability

Consider any assignment $A$ of extended boundary shapes to the edges of our
given maximal planar graph $G$. We wish to characterize the assignments that
are realizable as simple contact-representations; in this section, we do so
only for local realizability of a single polygon in the representation. If $A$
is realizable, then each extended shape in $A$, associated to an edge $e$, may
be interpreted as describing the shape of the boundary between the two
polygons corresponding to the two endpoints of $e$.

The boundary of each polygon in a simple contact-representation has a unique
decomposition into four polygonal chains of axis-parallel line segments, which
we call the _left_ , _right_ , _top_ , and _bottom_ boundary chains:

  * •

The top boundary chain consists of all horizontal boundary segments that the
polygon is below, together with all vertical segments between two of these
horizontal segments.

  * •

The bottom boundary chain similarly consists of all horizontal boundary
segments that the polygon is above, together with all vertical segments
between two of these horizontal segments.

  * •

The left boundary chain consists of all vertical segments that the polygon is
to the right of and that are between a horizontal segment of the top boundary
and a horizontal segment of the bottom boundary.

  * •

The right boundary chain consists of all vertical segments that the polygon is
to the right of and that are between a horizontal segment of the top boundary
and a horizontal segment of the bottom boundary.

Conversely, if a collection of boundary shapes can be realized as a polygon,
and can be partitioned in this way into exactly four chains, then the
resulting polygon must be $x$-monotone, suitable for taking part in a simple
contact-representation.

Let $v$ be any vertex in graph $G$. We define the _boundary cycle_ of $v$ to
be a cycle whose vertices are neighbors of $v$ in $G$, and whose edges belong
to face triangles of $G$ that are incident to $v$. That is, the boundary cycle
connects the neighboring vertices of $v$ in their cyclic order around $v$. It
is not necessarily an induced cycle, because $G$ can also include edges
between non-consecutive neighbors of $v$ (forming, with $v$, non-facial
separating triangles in $G$). The definition of a boundary cycle is somewhat
counterintuitive, because the shapes of the boundary of $v$’s polygon in a
contact-representation are not associated with the cycle edges; they are
instead associated with the star of edges incident to $v$. However, the
boundary cycle conveys important information about the cyclic ordering of
$v$’s neighbors that is missing from the star incident to $v$. When we express
the realizability of a polygon in graph logic, we will need this ordering
information, in order to express conditions involving contiguous subsequences
of neighbors by representing these subsequences as paths in the boundary
cycle.

We say that $v$ has a _monotone boundary_ in an extended shape assignment $A$
when the boundary cycle of $v$ can be partitioned into four paths as above:

  * •

a path that contains all neighboring vertices $u$ of $v$ such that the
extended shape associated with edge $uv$ includes horizontal segments that are
above the region for $v$,

  * •

a path that contains all neighboring vertices $u$ of $v$ such that the
extended shape associated with edge $uv$ includes horizontal segments that are
below the region for $v$,

  * •

a path that contains all neighboring vertices $u$ of $v$ such that the
extended shape associated with edge $uv$ includes vertical segments to the
left of the region for $v$ that are between one above-$v$ horizontal segment
and one below-$v$ horizontal segment, and

  * •

a path that contains all neighboring vertices $u$ of $v$ such that the
extended shape associated with edge $uv$ includes vertical segments to the
right of the region for $v$ that are between one above-$v$ horizontal segment
and one below-$v$ horizontal segment.

Note that the extended shape of an edge incident to $v$ may include multiple
line segments. Therefore, even though the four boundary chains of a polygon in
a contact-representation are interior-disjoint, the corresponding paths in the
boundary cycle of a vertex with monotone boundary might share vertices (but
not edges) with each other. Some of the boundary paths may be degenerate
(consisting of a single vertex) but it is not possible for three to be
degenerate and for the fourth to be a cycle containing all vertices rather
than a path, as (by Lemma 10) the top and bottom boundary paths must be
vertex-disjoint. Additionally, for $v$ to have a monotone boundary, we require
that the four boundary paths appear in an order consistent with the embedding
of $G$: for a vertex corresponding to an interior face of the embedding, the
clockwise ordering of these paths should be left, above, right, below, and for
the vertex corresponding to the outer face this ordering should be reversed.

From an assignment of extended shapes to edges of $G$, and a partition of the
boundary cycle of a vertex $v$ into boundary paths, we may construct polygonal
chains, the top, bottom, left or right _boundary shapes_ of $v$, by
concatenating the extended shapes associated with edges $uv$ for vertices $u$
in the boundary path, keeping only the appropriate subsets of the extended
shapes associated with the endpoints of the path.

Given any point $p$ in any extended shape, we can recover from the definition
of an extended shape the height $\operatorname{height}(p)$ at which $p$ should
be realized. For a point $p$ in the upper or lower boundary chain of a polygon
(or in the upper or lower boundary shape of a vertex of $G$ whose shapes are
not yet known to be realizable as a polygon) we define
$\operatorname{left}(p)$ to be the largest height among all points strictly to
the left of $p$ in the same part of the boundary. Symmetrically, we define
$\operatorname{right}(p)$ to be the largest height among all points strictly
to the right of $p$ in the same part of the boundary.

######  Lemma 16.

Let $A$ be an assignment of extended shapes to the edges of a maximal planar
graph $G$, and let $v$ be a vertex of $G$. Then there exists an $x$-monotone
polygon corresponding to $A$, whose boundary realizes the extended shapes
assigned by $A$ to the edges in $G$ incident to $v$, if and only if the
following conditions are met:

  * •

Vertex $v$ has a monotone boundary.

  * •

For every point $p$ in an extended shape of the upper boundary of $v$, there
must exist a corresponding point $q$ in the extended shape of the lower
boundary of $v$, such that

$\operatorname{height}(p)>\operatorname{height}(q),$
$\operatorname{left}(p)>\operatorname{left}(q),$

and

$\operatorname{right}(p)>\operatorname{right}(q),$

###### Proof.

If there exists an $x$-monotone polygon $P$ realizing the boundary shapes of
$v$ in shape assignment $A$, then (as above) this polygon’s boundary can be
partitioned into above, below, left, and right chains, and the corresponding
paths in $G$ show that $v$ has a monotone boundary. For any point $p$ in any
extended shape of the upper boundary of $v$, let $p^{\prime}$ be any point of
the segment of $P$ corresponding to the segment containing $p$ in the extended
shape. Let $q^{\prime}$ be the point of the lower boundary of $P$ directly
below $p^{\prime}$, and let $q$ be any point of the corresponding segment of
one of the extended shapes of the lower boundary of $v$. Then $p$ and
$p^{\prime}$ have the same heights, as do $q$ and $q^{\prime}$, so $q$ must be
below $p$. At the point of the lower boundary realizing
$\operatorname{height}(\operatorname{left}(q))$, the point on the upper
boundary with the same $x$-coordinate must be even higher, and to the left of
$p^{\prime}$, so the second of the three inequalities above must be valid. The
third inequality must also be valid by symmetric reasoning. Therefore, the
existence of $P$ implies that the conditions of the lemma are all met.

Conversely, suppose that assignment $A$ satisfies all the conditions of the
lemma for the boundary of $v$. We must show that in this case there exists an
$x$-monotone polygon $P$ realizingthe boundary shapes of $v$ in shape
assignment $A$. To do so, we first fix an arbitrary realization for the left,
right, and lower boundaries of $P$, by concatenating together the shapes of
the boundary segments. By monotonicity, this concatenation cannot be self-
crossing. It remains to realize the upper boundary, consistently with this
realization of the other parts of the boundary.

To do so, we first perturb the horizontal segments of the lower boundary
upwards or downwards by real numbers less than $1/2$, so that no two segments
have the same height as each other. Because this perturbation is less than the
unit amount by which top and bottom segments of the boundary must clear each
other, it has no effect on realizability. Next, we choose for each horizontal
segment $u_{i}$ of the upper boundary an interior point $p_{i}$, assign
$p_{i}$ a point $q_{i}$ on a horizontal segment of the lower boundary that
meets the conditions of the lemma, and let $\ell_{i}$ be the segment of the
lower boundary containing $q_{i}$. By the conditions of the lemma, at least
one point $q_{i}$ exists, and we choose $q_{i}$ to be any of the points that
match the conditions of the lemma and have the minimum possible height.
Because of the perturbation, $\ell_{i}$ is uniquely defined in this way from
$u_{i}$.

We claim that, for each two consecutive segments $u_{i}$ and $u_{i+1}$ of the
upper boundary, with $u_{i}$ to the left of $u_{i+1}$, the corresponding lower
boundary segments $\ell_{i}$ and $\ell_{i+1}$ have the same left-right
relation to each other. For, if $u_{i}$ is lower than $u_{i+1}$, we have that
$\operatorname{left}(p_{i})\leq\operatorname{left}(p_{i+1})$ (because
additional points on $u_{i+1}$ itself can contribute to the maximization in
the definition of $\operatorname{left}(p_{i+1})$) but
$\operatorname{right}(p_{i})=\operatorname{right}(p_{i+1})$ (the additional
points on $u_{i}$ can never have maximum height among all points to the right
of $p_{i}$). Therefore, the left constraint on $p_{i+1}$ is relaxed, allowing
$q_{i+1}$ to be farther to the right, while the right constraint is unchanged.
A symmetric argument applies to the case when $u_{i}$ is higher than
$u_{i+1}$. In this way, the assignment of lower segments $u_{i}$ to upper
segments $\ell_{i}$ is $x$-monotone.

To complete the realization, we assign each vertex point $p$ in each segment
of the upper boundary an $x$-coordinate. To do so, we choose a vertex
$p^{\prime}$ that should have the same $x$-coordinate as $p$. If $p$ is
incident to two horizontal segments of the upper boundary, we let
$p^{\prime}=p$; otherwise we let $p^{\prime}$ be the lower of the two
endpoints of the vertical segment incident to $p$. Let $u_{i}$ be a horizontal
segment incident to $p^{\prime}$, and let $\ell_{i}$ be the corresponding
lower segment. The mapping from each $p$ to $\ell_{i}$, defined in this way,
associates each vertex of the upper boundary to a segment of the lower
boundary, in an $x$-monotone way. We assign each point $p$ an $x$-coordinate
interior to the range of $x$-coordinates spanned by $\ell_{i}$. It is possible
to do this in such a way that upper boundary vertices that should have the
same $x$-coordinate (because they are connected by vertical segments) share
the same $x$-coordinate, other pairs of upper boundary vertices have distinct
$x$-coordinates, and the $x$-coordinates vary monotonically within the set of
all upper boundary vertices assigned to the same $\ell_{i}$.

In this way we find a monotonic $x$-coordinate assignment that realizes the
upper boundary of the polygon for vertex $v$. By monotonicity, the upper
boundary cannot cross itself. And by the condition that each upper boundary
vertex corresponds to a lower boundary segment of lower height, the
realization of the upper boundary remains at each point above the lower
boundary, so the upper and lower boundaries cannot cross each other.
Therefore, we have constructed a realization of the whole region for $v$ as an
$x$-monotone polygon, as desired. ∎

###  5.3 Logical expression

To recognize the graphs that have simple contact-representations, we will
apply Courcelle’s theorem [10], according to which every graph property that
can described in monadic second-order logic (more specifically a form of this
logic called MSO2) can be recognized for graphs of bounded treewidth in linear
time. Here, MSO2 is a form of logic in which the variables may represent
vertices, edges, sets of vertices, or sets of edges of a graph. The logic
allows both universal quantification ($\forall$) and existential
quantification ($\exists$) over these variables. There are three predicates on
pairs of variables: equality of variables of the same type ($=$), set
membership ($\in$), and incidence between an edge and a vertex (which we
represent by the non-standard binary operator $\multimap$). In addition, all
of the usual connectives of Boolean logic are available. We will use variables
$v_{i}$ for vertices, $V_{i}$ for sets of vertices, $e_{i}$ for edges, and
$E_{i}$ for sets of edges. If $G$ is a graph and $F$ is a formula of this
type, then the notation $G\models F$ (“$G$ models $F$”) means that the formula
becomes true when quantification and the predicates are given their usual
meanings for the vertices and edges of $G$. Because the equality sign has a
meaning as a predicate within this logic, we use $\equiv$ to indicate that two
formulas are syntactically equal or to assign a name to a formula. When we use
such a name within another formula, it means that the definition of that name
should be expanded at that point of the formula, eventually producing
(possibly after multiple expansions) a formula that uses only the notation
described above.

In this logic, for instance, graph $G$ is connected if and only if it cannot
be partitioned into two nonempty vertex sets with no edges between them. That
is, we can define a formula

$\begin{split}\operatorname{connected}\equiv\lnot\exists V_{1}\Bigl{(}&\exists
v_{2}(v_{2}\in V_{1})\wedge\\\ &\exists v_{3}\bigl{(}\lnot(v_{3}\in
V_{1})\bigr{)}\wedge\\\ &\lnot\exists v_{4},v_{5},e_{6}\bigl{(}v_{4}\in
V_{1}\wedge\lnot(v_{5}\in V_{1})\wedge e_{6}\multimap v_{4}\wedge
e_{6}\multimap v_{5})\bigr{)}\Bigr{)}\\\ \end{split}$

such that $G\models\operatorname{connected}$ if and only if $G$ is a connected
graph. Using similar logic, we can define a formula
$\operatorname{connected\\_subgraph}(E_{i})$ that is true when the set of
edges $E_{i}$ defines a connected subgraph of the given graph $G$; we need
merely add another clause to the third line of the definition of
$\operatorname{connected}$ requiring $e_{6}$ to belong to $E_{i}$. Using this
formula, we can define another more complicated formula
$\operatorname{path}(E_{i})$ that is true when $E_{i}$ is the edge set of a
path: a path is a connected subgraph that has two vertices of degree one and
all other vertices of degree two, and the degree conditions are
straightforward (if a bit tedious) to formulate in MSO2. Similarly a cycle is
a connected subgraph in which all vertices have degree exactly two.

A _peripheral cycle_ in a graph $G$ is a simple cycle $C$ with the property
that, for every two edges $e_{1}$ and $e_{2}$ not belonging to $C$, there
exists a path in $G$ containing both $e_{1}$ and $e_{2}$ whose degree-two
vertices are all disjoint from $C$. In a maximal planar graph (or more
generally in a 3-connected planar graph) the faces of the unique planar
embedding of the graph are exactly the peripheral cycles [29]. Because the
property of being a peripheral cycle admits a simple logical description in
MSO2, we can determine within MSO2 which triangles of our given maximal planar
graph are faces. Based on that determination we can also construct a formula
that is true of an edge set $E_{i}$ and vertex $v_{j}$ when $E_{i}$ is the
boundary cycle of $v_{j}$, and false otherwise.

In order to formulate the characterization of single-polygon realizability
from Lemma 16 in logical terms, we need some way to express an assignment of
extended shapes to the edges of $G$. For fixed $h$ there are by Lemma 15 only
$O(1)$ distinct extended shapes possible, allowing us to express any such
assignment within a logical formula with $O(1)$ edge set variables. Possibly
the simplest way of doing so is to use one edge set variable for each distinct
extended shape, having as its members the edges to which that shape has been
assigned. One can quantify over a shape assignment by applying the same
quantifier to each of these edge set variables, and then within the
quantification using a conjunction with a subformula that requires each edge
to belong to exactly one of these sets. With this logical expression of shape
assignments, it is again straightforward (but extremely tedious) to formulate
a logical expression $\operatorname{height\\_triple}(v,A,P,h_{1},h_{2},h_{3})$
that is true when $v$ is a vertex in $G$, $A$ is an extended shape assignment
for $G$, $P$ is either the upper or lower boundary of $v$ with respect to $A$,
and there exists a point $p$ within the shape of one of the edges of $P$ for
which $\operatorname{left}(p)=h_{1}$, $\operatorname{height}(p)=h_{2}$, and
$\operatorname{right}(p)=h_{3}$. Here, the numerical heights are not
themselves logical variables; rather, there is one such formula for each of
the $O(h^{3})$ different possible combinations of heights.

Using this subformula, it is straightforward to express the conditions of
Lemma 16 logically, by asking for the existence of a cycle and four paths that
form the boundary cycle for $v$ and the decomposition of this cycle into
boundary paths, and requiring that for these paths and for each realizable
triple of heights on the upper boundary there exists a compatible triple of
heights on the lower boundary. That is, for each expression
$\operatorname{height\\_triple}(v,A,P,h_{1},h_{2},h_{3})$ we write a logical
implication from the expression applied to the upper boundary to a disjunction
of expressions for compatible triples applied to the lower boundary, and we
take the conjunction of all such implications.

We summarize the discussion of this section by the following:

######  Claim 9.

For any fixed height $h$ there exists a logical formula
$\operatorname{realizable}(v,A)$ that is true whenever $A$ is an extended
shape assignment (described as a system of logical variables) for which there
exists an $x$-monotone polygon whose boundary realizes the extended shapes
assigned by $A$ to the edges in $G$ incident to $v$.

###  5.4 Global realizability

As we now prove, local realizability of each polygon in a contact-
representation implies global realizability of the entire representation. This
local-global principle is analogous to similar local-global principles for
realizability of upward planar graph drawings [3], rectilinear planar graph
drawings [27], level planar graph drawings, and flat-foldable graph drawings
[1].

######  Lemma 17.

Let $G$ be a maximal planar graph, and suppose that for an extended shape
assignment to $G$ of height $h$ each polygon is individually realizable (per
Lemma 16). Then there exists a simple contact-representation of height $h$ for
$G$.

###### Proof.

We may order the vertices of $G$ (and with them, the polygons of the
realization) by the heights of their lowest boundary segments in the shape
assignment, breaking ties arbitrarily. We will construct the realization
(again, allowing real numbers as $x$-coordinates) for each polygon in order
from lowest to highest in this order. By Lemma 10, the bottom boundary of each
polygon $P$ will have already been determined from the realizations of its
lower neighboring polygons, at the time we realize polygon $P$. Given an
arbitrary realization of polygon $P$ (assumed to exist by the preconditions of
this lemma), we may find an $x$-monotone transformation from that realization
to the fixed set of $x$-coordinates of its vertices in the realization of the
polygons below $F$. Applying the same transformation to the upper boundary of
$P$ produces a realization of $P$ compatible with the lower polygons. This
transformed copy of $P$ can be added to the realization of all polygons up to
$F$ in the height order. By induction on position within the height order, all
interior polygons are simultaneously realizable. Once they are all realized,
the exterior polygon is automatically realized as well. ∎

###  5.5 Recognition algorithm

######  Theorem 5.1.

There exists an algorithm for recognizing $n$-vertex graphs of simple grid-
major height $h$, and constructing a simple contact-representation for them,
in time $O(f(h)n)$ for a computable function $f$.

###### Proof.

We construct the formula $\operatorname{realizable}(v,A)$ for $h$, as
described in Claim 9, and from it construct the formula

$\operatorname{representable}\equiv\exists A\Bigl{(}\forall
v\bigl{(}\operatorname{realizable}(v,A)\bigr{)}\Bigr{)}$

(as before, expanding the mapping $A$ from edges to extended shapes into a
large number of edge set variables and expanding the existential quantifier on
$A$ into many existential quantifiers for each of these variables). By Lemma
17, $G\models\operatorname{representable}$ if and only if $G$ has a simple
grid-major contact-representation of height $h$. Next, by standard methods we
check that $G$ has treewidth at most $h$ (true of all graphs of simple grid-
major height $h$) and if so construct a tree-decomposition for $G$. If not, we
reject $G$ as not having simple grid-major height $h$. Finally, we use
Courcelle’s theorem to check from the formula for
$\operatorname{representable}$ and from the tree-decomposition of $G$ whether
$G\models\operatorname{representable}$. Standard variations of Courcelle’s
theorem for formulas whose outer quantifiers are existential, such as the
formula for $G\models\operatorname{representable}$, can find values for the
quantified variables for which the rest of the formula is true, and we use
these to find the extended shapes of the boundaries in a realizable simple
contact-representation of $G$. From these, it is straightforward to construct
the contact-representation itself, along the lines of the proofs of Lemmas 16
and 17. ∎

Because the logical formula used to express contact-representation
realizability has size exponential in $h^{2}\log h$, and Courcelle’s theorem
has non-elementary dependence on formula length, our simple grid-major height
algorithm is not practical. It remains open to find a practical fixed-
parameter tractable algorithm for the same problem.

##  6 Outlook

In this paper, we studied two parameters of planar triangulated graphs, the
homotopy height (well-known in computational geometry but not previously used
for graph drawing) and the grid-major height (related to contact-
representations, but not explicitly expressed as a graph parameter before). We
argue that these two seemingly unrelated parameters are actually equal, and
that they, as well as their variations that require simplicity in some sense,
can serve as lower bounds for the height of straight-line drawings of planar
graphs. Their equality also implies that testing whether homotopy height is at
most $k$ is fixed-parameter tractable in $k$. We leave many open problems:

  * •

What is the complexity of computing these various graph parameters? In
particular, while it is strongly believed that computing the minimum height of
a planar drawing is NP-hard, we are not aware of any proof of this. Similarly,
it is not known whether computing the homotopy height, or equivalently the
grid-major height, is NP-hard or polynomial. The same goes for the simple
variants. On the other hand, computing the pathwidth is NP-hard even for
planar graphs [20], while computing the outerplanarity is polynomial [6].

  * •

The trivial minor-closedness of grid-major height proves the existence of an
FPT algorithm to compute it when parameterized by the output. However, this
algorithm relies on finding the forbidden minors, which are unknown. Finding
an explicit algorithm for this problem, for instance along the lines of
Section 5, is still open. And because Section 5 uses Courcelle’s theorem, its
algorithm for simple grid-major height is not very efficient; finding a more
efficient algorithm again remains open.

  * •

We focused on straight-line drawings, but _poly-line drawings_ of $G$ (i.e.,
straight-line drawings of some subdivision $G^{\prime}$ of $G$) are also of
interest. Letting $\textit{PLh}(G)$ be the smallest height of such drawings,
one sees that
$\textit{GMh}(G)\leq\textit{sGMh}(G^{\prime})\leq\textit{SLh}(G^{\prime})\leq\textit{PLh}(G)$,
but is it true that $\textit{sGMh}(G)\leq\textit{PLh}(G)$?

## References

  * [1] Z. Abel, E. D. Demaine, M. L. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.  Flat foldings of plane graphs with prescribed angles and edge lengths.  J. Comput. Geom., 9(1):74–93, 2018.  doi:10.20382/jocg.v9i1a3.
  * [2] Md. J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S. G. Kobourov, and T. Ueckerdt.  Computing cartograms with optimal complexity.  Discrete Comput. Geom., 50(3):784–810, 2013.  doi:10.1007/s00454-013-9521-1.
  * [3] P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino.  Upward drawings of triconnected digraphs.  Algorithmica, 12(6):476–497, 1994.  doi:10.1007/BF01188716.
  * [4] T. Biedl.  Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs.  Discrete Comput. Geom., 45(1):141–160, 2011.  doi:10.1007/s00454-010-9310-z.
  * [5] T. Biedl.  Height-preserving transformations of planar graph drawings.  In C. Duncan and A. Symvonis, editors, Graph Drawing (GD’14), volume 8871 of Lecture Notes in Computer Science, pages 380–391. Springer, 2014.  doi:10.1007/978-3-662-45803-7_32.
  * [6] D. Bienstock and C. L. Monma.  On the complexity of embedding planar graphs to minimize certain distance measures.  Algorithmica, 5(1):93–109, 1990.  doi:10.1007/BF01840379.
  * [7] E. W. Chambers, A. de Mesmay, and T. Ophelders.  On the complexity of optimal homotopies.  In Symp. on Discrete Algorithms (SODA’18), pages 1121–1134. SIAM, 2018.
  * [8] E. W. Chambers and D. Letscher.  On the height of a homotopy.  In Canadian Conf. Comput. Geom. (CCCG’09), pages 103–106, 2009\.
  * [9] É. Colin de Verdière and J. Erickson.  Tightening nonsimple paths and cycles on surfaces.  SIAM J. Comput., 39(8):3784–3813, 2010.  doi:10.1137/090761653.
  * [10] B. Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inform. and Comput., 85(1):12–75, 1990.  doi:10.1016/0890-5401(90)90043-H.
  * [11] D. Dolev, T. Leighton, and H. Trickey.  Planar embedding of planar graphs.  Advances in Computing Research, 2:147–161, 1984.
  * [12] V. Dujmović, M. R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, and D. R. Wood.  On the parameterized complexity of layered graph drawing.  Algorithmica, 52(2):267–292, 2008.  doi:10.1007/s00453-007-9151-1.
  * [13] P. Eades, Q. Feng, X. Lin, and H. Nagamochi.  Straight-line drawing algorithms for hierarchical graphs and clustered graphs.  Algorithmica, 44(1):1–32, 2006.  doi:10.1007/s00453-004-1144-8.
  * [14] I. Fáry.  On straight line representation of planar graphs.  Acta Scientiarum Mathematicarum (Szeged), 11(4):229–233, 1948.
  * [15] S. Felsner, G. Liotta, and S. Wismath.  Straight-line drawings on restricted integer grids in two and three dimensions.  J. Graph Algorithms and Applications, 7(4):335–362, 2003.  doi:10.7155/jgaa.00075.
  * [16] F. V. Fomin and D. M. Thilikos.  New upper bounds on the decomposability of planar graphs.  J. Graph Theory, 51(1):53–81, 2006.  doi:10.1002/jgt.20121.
  * [17] F. Frati.  Lower bounds on the area requirements of series-parallel graphs.  Discrete Mathematics & Theoretical Computer Science, 12(5):139–174, 2010.  URL: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1472.1.html.
  * [18] H. de Fraysseix, J. Pach, and R. Pollack.  Small sets supporting Fáry embeddings of planar graphs.  In Symp. Theory of Computing (STOC’88), pages 426–433. ACM, 1988\.  doi:10.1145/62212.62254.
  * [19] H. de Fraysseix, J. Pach, and R. Pollack.  How to draw a planar graph on a grid.  Combinatorica, 10:41–51, 1990.  doi:10.1007/BF02122694.
  * [20] J. Gustedt.  On the pathwidth of chordal graphs.  Discrete Appl. Math., 45(3):233–248, 1993.  doi:10.1016/0166-218X(93)90012-D.
  * [21] S. Har-Peled, A. Nayyeri, M. Salavatipour, and A. Sidiropoulos.  How to walk your dog in the mountains with no magic leash.  Discrete Comput. Geom., 55(1):39–73, 2016.  doi:10.1007/s00454-015-9737-3.
  * [22] L. S. Heath and A. L. Rosenberg.  Laying out graphs using queues.  SIAM J. Comput., 21(5):927–958, 1992.  doi:10.1137/0221055.
  * [23] J. Pach and G. Tóth.  Monotone drawings of planar graphs.  J. Graph Theory, 46(1):39–47, 2004.  doi:10.1002/jgt.10168.
  * [24] P. Rosenstiehl and R. E. Tarjan.  Rectilinear planar layouts and bipolar orientation of planar graphs.  Discrete Comput. Geom., 1:343–353, 1986.  doi:10.1007/BF02187706.
  * [25] Walter Schnyder.  Embedding planar graphs on the grid.  In Symp. on Discrete Algorithms (SODA’90), pages 138–148. SIAM, 1990.
  * [26] S. K. Stein.  Convex maps.  Proc. Amer. Math. Soc., 2:464–466, 1951.  doi:10.2307/2031777.
  * [27] R. Tamassia.  On embedding a graph in the grid with the minimum number of bends.  SIAM J. Comput., 16(3):421–444, 1987.  doi:10.1137/0216030.
  * [28] R. Tamassia and I. Tollis.  A unified approach to visibility representations of planar graphs.  Discrete Comput. Geom., 1:321–341, 1986.  doi:10.1007/BF02187705.
  * [29] W. T. Tutte.  How to draw a graph.  Proc. London Math. Soc., 13:743–767, 1963.  doi:10.1112/plms/s3-13.1.743.
  * [30] K. Wagner.  Bemerkungen zum Vierfarbenproblem.  Jahresber. Dtsch. Math.-Ver., 46:26–32, 1936.
  * [31] S. K. Wismath.  Characterizing bar line-of-sight graphs.  In Symp. Computational Geometry (SoCG’85), pages 147–152. ACM, 1985\.  doi:10.1145/323233.323253.