# Convex Grid Drawings of Planar Graphs
with Constant Edge-Vertex Resolution

Michael A. Bekos1, Martin Gronemann2,
Fabrizio Montecchiani3, Antonios Symvonis4
1Department of Mathematics, University of Ioannina, Ioannina, Greece
<EMAIL_ADDRESS>
2Algorithms and Complexity Group, TU Wien, Vienna, Austria
<EMAIL_ADDRESS>
3Department of Engineering, University of Perugia, Perugia, Italy
<EMAIL_ADDRESS>
4School of Applied Mathematical & Physical Sciences,
National Technical University of Athens, Athens, Greece
<EMAIL_ADDRESS>
###### Abstract

We continue the study of the area requirement of convex straight-line grid
drawings of $3$-connected plane graphs, which has been intensively
investigated in the last decades. Motivated by applications, such as graph
editors, we additionally require the obtained drawings to have bounded _edge-
vertex resolution_ , that is, the closest distance between a vertex and any
non-incident edge is lower bounded by a constant that does not depend on the
size of the graph. We present a drawing algorithm that takes as input a
$3$-connected plane graph with $n$ vertices and $f$ internal faces and
computes a convex straight-line drawing with edge-vertex resolution at least
$\frac{1}{2}$ on an integer grid of size $(n-2+a)\times(n-2+a)$, where
$a=\min\\{n-3,f\\}$. Our result improves the previously best-known area bound
of $(3n-7)\times(3n-7)/2$ by Chrobak, Goodrich and Tamassia.

##  1 Introduction

Fáry’s theorem [20] is a fundamental result in planar graph drawing, as it
guarantees the existence of a planar straight-line drawing for every planar
graph. In such a drawing, the vertices of the graph are mapped to distinct
points of the Euclidean plane in such a way that the edges are straight, non-
intersecting line-segments. This central result has been independently proved
by several researchers in early works [30, 31, 36], some of which also
suggested corresponding constructive algorithms requiring high-precision
arithmetics; see, e.g., [9, 33]. In this regard, a breakthrough has been
introduced by de Fraysseix, Pach and Pollack [13] in the late 80’s, who
proposed a method that additionally guarantees the obtained drawings to be on
an integer grid (thus making the high-precision operations unnecessary). A
linear-time implementation of this method was proposed by Chrobak and Payne
[12]. Over the years, several works have studied the area requirement of
planar graphs under different settings, by providing bounds on the required
size of the underlying grid; see, e.g., [16, 18, 21, 24, 29]. In the original
work by de Fraysseix et al. the size of the underlying grid is
$(2n-4)\times(n-2)$ with $n$ being the number of vertices of the graph; such a
bound is asymptotically worst-case optimal, as it is known that there exist
$n$-vertex planar graphs that need $\Omega(n)\times\Omega(n)$ area in any of
their planar drawings [13, 22].

The corresponding best-known111Note that improvements on this bound are known
but they are obtained by exploiting either the structure of the input graph
[8, 16, 18, 37] or higher connectivity [21, 24]. upper bound is due to Chrobak
and Kant [11], who presented a linear-time algorithm to embed any $n$-vertex
planar graph into a grid of size $(n-2)\times(n-2)$; see also [29]. In
contrast to the work by de Fraysseix, Pach and Pollack [13], which requires an
augmentation of the input planar graph to maximal planar, the algorithm by
Chrobak and Kant [12] requires just $3$-connectivity. Furthermore, it
guarantees an additional property, which is desired when drawing $3$-connected
planar graphs (see, e.g., [32]): the obtained drawings are _convex_ , i.e.,
the boundary of each face is a convex polygon.

(a)

(b)

Figure 1: Two planar straight-line grid drawings of the same graph; the
drawing in (a) contains an edge-vertex intersection (on vertex C), while the
one in (b) does not as it has edge-vertex resolution at least $\frac{1}{2}$.

Back in 1996, Chrobak, Goodrich and Tamassia [10] studied the area requirement
of $3$-connected planar graphs under an additional requirement, which is
essential in practical applications. In particular, they introduced the notion
of _edge-vertex resolution_ , which measures how close a vertex is to any non-
incident edge, and required that the obtained drawings have bounded edge-
vertex resolution. This requirement becomes essential in several practical
situations, for instance, consider graph editors which usually represent each
vertex by an object of a certain size (rather than a point) containing a
distinguishing label. Having high edge-vertex resolution allows to avoid
potential overlaps between vertices and edges, in particular, having edge-
vertex resolution at least $\frac{1}{2}$ allows each vertex to be represented
as an open disk of unit diameter, such that overlaps between vertices and non-
incident edges are completely avoided, and simultaneously vertices centered at
neighboring grid-points do not overlap (although may touch); see Fig. 1. In
their work [10], Chrobak, Goodrich and Tamassia claimed that every
$3$-connected planar graph admits a convex planar straight-line grid drawing
on a grid of size $(3n-7)\times(3n-7)/2$ with edge-vertex resolution at least
$\frac{1}{2}$. However, the details of the algorithm (and of its proof)
supporting this claim never appeared in the literature. In this regard, very
recently, Bekos et al. [5] referred to the drawings with edge-vertex
resolution at least $\frac{1}{2}$ as _disk-link_ and proved (among other
results) that every planar graph admits a planar straight-line disk-link
drawing on a grid of size $(3n-7)\times(3n-7)/2$. However, the obtained
drawing is not necessarily convex.

Contribution. We improve both results mentioned above by providing a linear-
time algorithm to compute planar straight-line disk-link drawings that are
convex and that fit on a grid of size $(n-2+a)\times(n-2+a)$, where
$a=\min\\{f,n-3\\}$ and $f$ denotes the number of internal faces of the input
graph. In particular, if the input graph is maximal planar (that is,
$f=2n-5$), our technique yields drawings of area $(2n-5)\times(2n-5)$. On the
other hand, if the input graph is $3$-connected cubic (that is,
$f=\frac{n}{2}+1$), then our technique yields drawings of area
$(\frac{3n}{2}-1)\times(\frac{3n}{2}-1)$. Our result is summarized in the next
theorem.

######  Theorem 1.

Every $3$-connected plane graph with $n$ vertices and $f$ internal faces
admits a convex planar straight-line grid drawing with edge-vertex resolution
at least $\frac{1}{2}$ on a grid of size $(n-2+a)\times(n-2+a)$, where
$a=\min\\{f,n-3\\}$. Also, the drawing can be computed in $O(n)$ time.

Related work. Bárány and Rote [2] prove that every $3$-connected planar graph
has a _strictly_ convex drawing on a quartic grid, improving a previous result
by Rote [27]. We recall that a planar drawing is strictly convex if each face
is bounded by a strictly convex polygon. We point the interested reader to the
surveys by Di Battista and Frati [14, 15] for additional references and
results concerning convex and strictly-convex drawings of planar graphs in
small area.

Concerning the edge-vertex resolution requirement there exist multiple related
streams of research. A _closed rectangle-of-influence_ (closed RI for short)
drawing is a planar straight-line drawing such that no vertex lies in the
axis-parallel rectangle (including the boundary) defined by the two ends of
every edge [1, 4, 6, 7, 23, 28]. Any closed RI drawing whose vertices are at
integer coordinates can be seen as a disk-link drawing. This implies that
disk-link drawings (not necessarily convex) in quadratic area exist for
several classes of plane graphs [4, 6, 28]. However, any plane graph with a
filled $3$-cycle does not admit a closed RI drawing [6]. Another related
direction considers drawings where vertices are objects with integer
coordinates and the edges are fat segments [3]. In such drawings the edges do
not connect the centers of the incident vertex-disks but rather simply enter
these vertex-objects through varying angles. Duncan et al. [17] also use fat
edges but, in contrast to [3], they do not compute a drawing from scratch but
rather try to extend an existing one without modifying the area of the layout.
Van Kreveld [34] studies _bold drawings_ , in which vertices are drawn as
disks of radius $r$ and edges as rectangles of width $w$, where $r>w/2$. A
bold drawing is _good_ if all of its vertices and edges are at least partially
visible (neither a vertex disk nor an edge-rectangle is completely hidden by
overlapping edges). Although disk-link drawings form a special case of bold
drawings in which $r=\frac{1}{2}-\varepsilon$ and $w=2\varepsilon$ (for some
sufficiently small $\varepsilon>0$), the research on bold drawings has mainly
focused on finding feasible values of $r$ and $w$, rather than on area bounds
for fixed values of $r$ and $w$.

##  2 Preliminaries

Basic definitions. A _drawing_ of a graph maps each vertex to a distinct point
of the Euclidean plane, and each edge to a Jordan arc connecting its
endpoints. A drawing of a graph is _planar_ if no two edges intersect, except
possibly at a common endpoint. A planar drawing partitions the plane into
topologically connected regions, which are commonly called _faces_. The
unbounded region is called _outer face_ ; any other face is an _internal
face_. A graph is _planar_ if and and only if it admits a planar drawing. A
_planar embedding_ of a planar graph is an equivalence class of topologically-
equivalent (i.e., isotopic) planar drawings. A planar graph with a given
planar embedding is a _plane graph_.

A drawing is _straight-line_ if the Jordan arcs representing the edges are
straight-line segments. The _slope_ of a line $\ell$ is the tangent of the
minimum-angle that a horizontal line needs to be rotated in order to make it
overlap with $\ell$; a positive slope corresponds to a counter-clockwise
rotation, while a negative one corresponds to a clockwise rotation. The
_slope_ of a segment is the slope of the supporting line containing it. A
_grid drawing_ of a graph is a straight-line drawing whose vertices are at
integer coordinates. We say that the grid size of a grid drawing $\Gamma$ is
$W\times H$ (or, equivalently, the area of $\Gamma$ is $W\times H$), if the
minimum axis-aligned box containing $\Gamma$ has side lengths $W-1$ and $H-1$.
Moreover, for a vertex $v$ of a graph $G$, we denote by $x_{\Gamma}(v)$ and by
$y_{\Gamma}(v)$ the $x$\- and $y$-coordinate of $v$ in drawing $\Gamma$ of
$G$, respectively. When the reference to $\Gamma$ is clear from the context,
we simply write $x(v)$ and $y(v)$.

Disk-link drawings. The _edge-vertex resolution_ of a grid drawing of a graph
is the minimum Euclidean distance between a point representing a vertex and
any edge that is not incident to that vertex. A _disk-link drawing_ of a graph
is a grid drawing of edge-vertex resolution at least $\frac{1}{2}$. Observe
that, in a disk-link drawing $\Gamma$, for each vertex $v$ one can draw an
open disk with radius $\overline{\rho}\leq\frac{1}{2}$ centered at the point
of $\Gamma$ representing $v$, and this results in a diagram in which no two
disks intersect, and no disk is intersected by a non-incident edge. For
simplicity, we assume that $\overline{\rho}=\frac{1}{2}$, i.e., the disks have
unit diameter. This assumption is not restrictive, since our results carry
over for any constant radius up to some multiplicative constant factor for the
area.

Canonical order. Even though we assume familiarity with basic concepts of
planar graph drawing [26, 35], we recall in this section a key concept that is
central in several algorithms for producing planar grid drawings of plane
graphs, e.g., [10, 13, 22]. Namely, the _canonical order_ [22] for 3-connected
plane graphs, which is defined as follows: Let $G$ be a $3$-connected plane
graph with $n$ vertices and let $\pi=(P_{0},\ldots,P_{m})$ be a partition of
the vertex-set of $G$ into paths, such that $P_{0}=\\{v_{1},v_{2}\\}$,
$P_{m}=\\{v_{n}\\}$, and edges $(v_{1},v_{2})$ and $(v_{1},v_{n})$ exist and
belong to the outer face of $G$. For $k=0,\ldots,m$, let $G_{k}$ be the
subgraph induced by $\cup_{i=0}^{k}P_{i}$ and denote by $C_{k}$ the _contour_
of $G_{k}$ defined as follows: If $k=0$, then $C_{0}$ is the edge
$(v_{1},v_{2})$, while if $k>0$, then $C_{k}$ is the path from $v_{1}$ to
$v_{2}$ obtained by removing $(v_{1},v_{2})$ from the cycle delimiting the
outer face of $G_{k}$. We say that $\pi$ is a _canonical order_ of $G$ if for
each $k=1,\ldots,m-1$ the following properties hold:

  1. P.1

$G_{k}$ is biconnected and internally $3$-connected,

  2. P.2

all neighbors of $P_{k}$ in $G_{k-1}$ are on $C_{k-1}$,

  3. P.3

either $P_{k}$ is a _singleton_ (that is, $|P_{k}|=1$), or $P_{k}$ is a
_chain_ (that is, $|P_{k}|>1$) and the degree of each vertex of $P_{k}$ is $2$
in $G_{k}$, and

  4. P.4

all vertices of $P_{k}$ with $0\leq k<m$ have at least one neighbor in $P_{j}$
for some $j>k$.

A canonical order of $G$ can be computed in linear time [22]. A vertex on
contour $C_{k}$ is called _saturated_ in $G_{k}$ if and only if it is not
adjacent to a vertex belonging to a path $P_{k^{\prime}}$ with $k^{\prime}>k$.

##  3 Convex planar grid disk-link drawings

In this section, we present our algorithm to compute convex planar grid disk-
link drawings of 3-connected plane graphs. As our algorithm builds upon an
algorithm by Chrobak and Kant [11], which yields convex planar grid drawings
(that are not necessarily disk-link) of 3-connected plane graphs with $n$
vertices on grids of size $(n-2)\times(n-2)$, for completeness, we first
recall its basic ingredients before we enter the details of our approach.

###  3.1 The algorithm by Chrobak and Kant [11].

This algorithm is incrementally computing a convex planar drawing $\Gamma$ of
a 3-connected plane graph $G$ using a canonical order
$\pi=(P_{0},\ldots,P_{m})$ of $G$. The drawing $\Gamma$ has integer grid
coordinates and fits in a grid of size $(n-2)\times(n-2)$. In order to ease
the presentation, we define a Schnyder-like [19, 29] $4$-coloring of the edges
of $G$ based on the canonical order $\pi$. $G_{0}$ consists of a single edge
$(v_{1},v_{2})$, which is assigned the black color. Assuming that a
$4$-coloring has been constructed for $G_{k-1}$ with $k=1,\ldots,m$, we extend
it for $G_{k}$ as follows (see Fig. 2(a)): We first color the edges of $G_{k}$
that do not belong to $G_{k-1}$ and are on contour $C_{k}$. We color the first
such edge encountered in a traversal of $C_{k}$ from $v_{1}$ to $v_{2}$ blue,
the last one green and all remaining ones (i.e., those having both endpoints
in $P_{k}$, when $P_{k}$ is a chain) black. Similar to the Schnyder coloring
of maximal planar graphs, we assign the color red to the remaining edges of
$G_{k}$ that do not belong to $G_{k-1}$ (i.e., those that are incident to
$P_{k}$ and are not part of contour $C_{k}$). Note that the latter case only
arises if $P_{k}$ is a singleton by Property P.3 of the canonical order.

(a) Contour condition

(b) Placement of $P_{k}$ in $\Gamma_{k-1}$

Figure 2: Introducing a singleton $P_{k}$ in $\Gamma_{k-1}$ according to the
algorithm by Chrobak and Kant [11]; the white-filled vertices are the critical
vertices $w_{\ell^{\prime}}$ and $w_{r^{\prime}}$.

Based on the canonical order $\pi$ of $G$, drawing $\Gamma$ is constructed as
follows: Initially, the vertices $v_{1}$ and $v_{2}$ of $P_{0}$ are placed at
points $(0,0)$ and $(1,0)$, respectively. For $k=1,\ldots,m$, assume that a
planar convex grid drawing $\Gamma_{k-1}$ of $G_{k-1}$ has been constructed in
which the edges of contour $C_{k-1}$ are drawn as straight-line segments with
slopes $0$, $-1$ or in $[1,+\infty]$ (_contour condition_ ; see Fig. 2(a)). In
particular, the slope of each blue edge of $C_{k-1}$ is at least $1$, the
slope of each black edge of $C_{k-1}$ is $0$, while the slope of each green
edge of $C_{k-1}$ is $-1$ (note that $C_{k-1}$ does not contain any red edge
by definition). Also, each vertex $v$ in $G_{k-1}$ has been associated with a
so-called _shift-set_ , denoted by $S(v)$; the shift-sets of $v_{1}$ and
$v_{2}$ of path $P_{0}$ are singletons such that $S(v_{1})=\\{v_{1}\\}$ and
$S(v_{2})=\\{v_{2}\\}$.

Let $(w_{1},\ldots,w_{p})$ be the vertices of $C_{k-1}$ from left to right in
$\Gamma_{k-1}$, where $w_{1}=v_{1}$ and $w_{p}=v_{2}$. For the next path
$P_{k}=\\{z_{1},\ldots,z_{q}\\}$ in $\pi$, let $w_{\ell}$ and $w_{r}$ be the
leftmost and rightmost neighbors of $P_{k}$ on $C_{k-1}$ in $\Gamma_{k-1}$,
where $1\leq\ell<r\leq p$. For the definition of the shift-set $S(v)$ of each
vertex $v$ in $P_{k}$, the algorithm identifies two _critical_ vertices on the
contour $C_{k-1}$, which we denote by $w_{\ell^{\prime}}$ and
$w_{r^{\prime}}$, such that $\ell<\ell^{\prime}\leq r$ and $\ell\leq
r^{\prime}<r$ (refer to the white-filled vertices of Fig. 2); note that it is
possible to have $w_{\ell^{\prime}}=w_{r^{\prime}}$. Vertex
$w_{\ell^{\prime}}$ is the first vertex encountered in the traversal of
$C_{k-1}$ starting from $w_{\ell+1}$ towards $w_{r}$ that either has a
neighbor in $P_{k}$ or the edge $(w_{\ell^{\prime}},w_{\ell^{\prime}+1})$ is
blue or black; note that it is possible to have $w_{\ell^{\prime}}=w_{r}$.
Symmetrically, vertex $w_{r^{\prime}}$ is the first vertex encountered in the
traversal of $C_{k-1}$ starting from $w_{r-1}$ towards $w_{\ell}$ that either
has a neighbor in $P_{k}$ or the edge $(w_{r^{\prime}-1},w_{r^{\prime}})$ is
green or black; note that it is possible to have $w_{r^{\prime}}=w_{\ell}$. We
refer to $w_{\ell^{\prime}}$ and $w_{r^{\prime}}$ as the _left-critical_ and
_right-critical vertices_ of $P_{k}$. More importantly, since each internal
face of $\Gamma_{k}$ is convex, in the case where $P_{k}$ is either a chain or
a singleton of degree $2$ in $G_{k}$, vertices $w_{\ell^{\prime}}$ and
$w_{r^{\prime}}$ are either consecutive along $C_{k-1}$ or
$w_{\ell^{\prime}}=w_{r^{\prime}}$ holds. Once $w_{\ell^{\prime}}$ and
$w_{r^{\prime}}$ have been identified, the algorithm sets the shift-sets of
the vertices $z_{1},\ldots,z_{q}$ of $P_{k}$ as follows:

$S(z_{1})=\\{z_{1}\\}\cup\bigcup_{i=\ell^{\prime}}^{r^{\prime}}S(w_{i}),\qquad\text{and}\qquad
S(z_{i})=\\{z_{i}\\},\text{ for }i=2,\ldots,q$ (1)

Furthermore, to guarantee that the resulting drawing is convex, the algorithm
updates the shift-sets of $w_{\ell}$ and $w_{r}$ of $G_{k-1}$ as follows:

$S(w_{\ell})=\bigcup_{i=\ell}^{\ell^{\prime}-1}S(w_{i}),\qquad\text{and}\qquad
S(w_{r})=\bigcup_{i=r^{\prime}+1}^{r}S(w_{i}).$ (2)

To compute the drawing $\Gamma_{k}$, the algorithm distinguishes two cases. If
$w_{\ell}$ is saturated in $G_{k}$ (i.e., $z_{1}$ is the last neighbor of
$w_{\ell}$ that has not been drawn), then the $x$-coordinate of $z_{1}$ is the
same as the one of $w_{\ell}$, that is, $x(z_{1})=x(w_{\ell})$. Otherwise,
$x(z_{1})=x(w_{\ell})+1$. To accommodate the vertices of $P_{k}$ and to avoid
edge-overlaps, the algorithm shifts each vertex in

$\bigcup_{i=r}^{p}S(w_{i}).$ (3)

by $q$ units to the right (see Fig. 2(b)). Then, the algorithm places vertex
$z_{q}$ at $(x(z_{1})+q-1,y(w_{r})+x(w_{r})-(x(z_{1})+q-1))$, i.e., at the
intersection of the line of slope $-1$ through $w_{r}$ with the vertical line
through point $x(z_{1})+q-1$. Note that this is a grid point above $w_{\ell}$
and $w_{r}$ due to the contour condition and the shifting of $S(w_{r})$. For
$i=1,\ldots,q-1$, vertex $z_{i}$ of $P_{k}$ is placed $q-i$ units to the left
of $z_{q}$. Since $(w_{\ell},z_{1})$ is blue, $(z_{q},w_{r})$ is green, and
the internal edges of $P_{k}$ (if any) are black, the contour condition of the
algorithm is, by construction, maintained after the placement of the vertices
of $P_{k}$ in $\Gamma_{k}$.

The contour condition together with the shifting procedure described above
guarantee Property 2 for the slopes of the edges in $\Gamma_{k}$.

(a)

(b)

Figure 3: Illustration of (a) Property 2 and (b) Property 3.

######  Property 2 (Chrobak and Kant [11]).

A shift can only decrease the slope of a blue edge, increase the slope of a
green edge, while the black and the red edges are _rigid_ , i.e., they
maintain their slope. As a result, in $\Gamma_{k}$ (see Fig. 3(a)):

  * –

the slope of each blue edge ranges in $(0,+\infty]$,

  * –

the slope of each black edge is $0$,

  * –

the slope of each green edge ranges in $[-1,0)$, and

  * –

the slope of each red edge ranges in $[-\infty,-1)$.

Since each face of $\Gamma_{k}$ is formed when a path $P_{k^{\prime}}$ with
$k^{\prime}\leq k$ of canonical order $\pi$ is introduced, Property 2 combined
with the contour condition and Property P.4 of the canonical order imply the
following property for the shape of each face in $\Gamma_{k}$.

######  Property 3.

Let $f$ be a face in $\Gamma_{k}$. Then, a counter-clockwise traversal of $f$
starting from its leftmost vertex that is the bottommost when it is not
uniquely defined consists of the following boundary parts (see Fig. 3(b)):

  1. i.

a strictly descendant path of green edges (possibly empty),

  2. ii.

a black edge (possible non existent),

  3. iii.

a strictly ascendant path of blue edges (possible empty),

  4. iv.

a green or red edge,

  5. v.

a horizontal path of black edges (possibly empty), and

  6. vi.

a blue or red edge.

Boundary parts (i)–(iii) in Property 3 form the _lower envelope_ of $f$ (solid
in Fig. 3(b)). The _upper envelope_ of $f$ is formed by boundary parts
(iv)–(vi) (dotted in Fig. 3(b)). The latter is introduced in $\Gamma_{k}$ when
a path of the canonical order is placed. Thus, the upper envelope cannot
contain black and red edges simultaneously (by Property P.3 of canonical
order). Finally, boundary parts (iii) and (iv) form the _right envelope_ of
$f$, while (vi) and (i) form the _left envelope_ of $f$ (gray-highlighted in
Fig. 3(b)). We next state some lemmata regarding the “behavior” of the
algorithm by Chrobak and Kant [11] that are employed in the proof of
correctness of our modification.

######  Lemma 4.

Let $u$ and $v$ be two distinct vertices of $G_{k}$ belonging to the same face
$f$ of $\Gamma_{k}$. If $u$ and $v$ have the same $y$-coordinate in
$\Gamma_{k}$ with $x(u)<x(v)$, then either $u$ and $v$ are connected by a path
of black edges of $f$ or the $x$-coordinate of the bottommost vertex/vertices
of $f$ is/are in the interval $(x(u),x(v)]$.

###### Proof.

Indeed, if $u$ and $v$ are connected by a path consisting exclusively of black
edges, then by Property 2 $u$ and $v$ have the same $y$-coordinate. Assume now
that $u$ and $v$ are not connected by a path of black edges, and let without
loss of generality $u$ be to the left of $v$ in $\Gamma_{k}$. Since the
vertices of the left/right envelope all have distinct coordinates, $u$ belongs
to the left envelope of $f$, while $v$ to the right envelope of $f$. As a
result, a counter-clockwise traversal of $f$ from $u$ to $v$ contains the
bottommost vertex/vertices of $f$, which proves the statement. ∎

######  Lemma 5.

Let $\mathcal{S}_{k}$ be the vertices of $G_{k-1}$ that were shifted during
the introduction of $P_{k}$ in $\Gamma_{k}$, and let $c$ be a positive
integer. Let $\Gamma_{k}^{\prime}$ be the drawing obtained from $\Gamma_{k-1}$
by first shifting the vertices of $\mathcal{S}_{k}$ by $c$ units to the right
and then attaching $P_{k}$ as in the algorithm by Chrobak and Kant [11]. Then,
$\Gamma_{k}^{\prime}$ is a convex planar grid drawing of $G_{k}$.

###### Proof.

We focus on the case in which $P_{k}$ is a singleton; the case of a chain is
similar. Let $w_{\bar{r}}$ and $w_{r}$ with $\ell\leq\bar{r}<r$ be the
rightmost two neighbors of $P_{k}$ on $C_{k-1}$ in $\Gamma_{k-1}$. Note that,
by construction (see Eq. 3), $\mathcal{S}_{k}$ is the union of the shift-sets
of $w_{r}$ and all the vertices that follow it in the contour $C_{k-1}$. Then,
shifting the vertices of $\mathcal{S}_{k}$ by $c$ units to the right can be
simulated by the following procedure: Attach a degree-$2$ singleton $s_{0}$
with endpoints $w_{r}$ and $w_{\bar{r}}$, and for each $i=1,\ldots,c-1$ attach
a degree-$3$ singleton $s_{i}$ with neighbors $w_{r}$, $s_{i-1}$ and
$w_{\bar{r}}$. By the correctness of the algorithm by Chrobak and Kant [11],
the resulting drawing is a convex planar grid drawing which satisfies the
contour condition. Then, removing vertices $s_{0},\ldots,s_{c-1}$ and
introducing $P_{k}$ as in the algorithm does not violate any of the
aforementioned properties, yielding a convex planar grid drawing
$\Gamma_{k}^{\prime}$ of $G_{k}$. ∎

######  Lemma 6.

Let $f$ be a face of $\Gamma_{k-1}$ that contains a black edge $(u,v)$ at its
lower envelope, such that $u$ is to the left of $v$ in $\Gamma_{k-1}$, and
assume that some vertices of $f$ are not shifted during the introduction of
$P_{k}$ in $\Gamma_{k}$. Then, neither $u$ nor $v$ are shifted, unless $(u,v)$
is the rightmost edge of the lower envelope of $f$, in which case $u$ is not
shifted, while $v$ is shifted.

###### Proof.

By Eq. 2, it follows that if $v$ is not the rightmost edge of the lower
envelope of $f$, then neither vertex $u$ nor vertex $v$ is in the shift-set of
the rightmost vertex of $f$, when $f$ is formed in the incremental
construction of $\Gamma_{k-1}$ based on $\pi$. On the other hand, if $v$ is
the rightmost edge of the lower envelope of face $f$, then $v$ is in the
shift-set $S(v)$, while vertex $u$ is not. Since not all vertices of $f$ are
shifted during the introduction of $P_{k}$ in $\Gamma_{k}$, it follows that,
among the vertices of the lower envelope of $f$, the ones that are shifted are
those in the shift-set of the rightmost vertex of the lower envelope of $f$,
which proves the lemma. ∎

###  3.2 Our modification.

We start by placing $v_{1}$ and $v_{2}$ of path $P_{0}$ as in the algorithm by
Chrobak and Kant [11], that is, at points $(0,0)$ and $(1,0)$, respectively.
Assume now that $\Gamma_{k-1}$ is a convex planar disk-link drawing of
$G_{k-1}$. For placing path $P_{k}$ in drawing $\Gamma_{k-1}$, $k=1,\ldots,m$,
we distinguish two cases. In the first case, $P_{k}$ is a chain and we proceed
as in the algorithm by Chrobak and Kant [11]. Hence, we focus on the more
elaborated case, in which $P_{k}$ is a singleton, i.e., $P_{k}=\\{z_{1}\\}$.
In this case, our algorithm first shifts the vertices of $\Gamma_{k-1}$
appropriately to guarantee that the obtained drawing $\Gamma_{k}$ is a disk-
link drawing (to be shown in Lemma 10). Let $w_{x_{0}},\ldots,w_{x_{\rho+1}}$
be the neighbors of $P_{k}$ along $C_{k-1}$, such that
$\ell=x_{0}<x_{1}<\ldots<x_{\rho}<x_{\rho+1}=r$. Note that, based on this
notation, $\rho$ denotes the number of neighbors of $P_{k}$ between $w_{\ell}$
and $w_{r}$ on $C_{k-1}$. Besides critical vertices $w_{\ell^{\prime}}$ and
$w_{r^{\prime}}$, our modification introduces the following $\rho+1$ _pivot
vertices_ $w_{x_{1}^{\prime}},\ldots,w_{x_{\rho+1}^{\prime}}$, where
$w_{x_{1}^{\prime}}=w_{\ell^{\prime}}$ and $w_{x_{\rho+1}^{\prime}}=w_{r}$.
For $j=2,\ldots,\rho$, the pivot vertex $w_{x_{j}^{\prime}}$ (with
$x_{j-1}<x_{j}^{\prime}\leq x_{j}$) is defined as the first vertex encountered
in the traversal of $C_{k-1}$ starting from $w_{x_{j-1}+1}$ towards
$w_{x_{j}}$ that either is neighboring $z_{1}$ or is followed by an edge of
$C_{k-1}$ that is blue or black. In other words, pivot vertex
$w_{x_{j}^{\prime}}$ would be the vertex that the algorithm by Chrobak and
Kant [11] identifies as left-critical, when attaching a singleton with exactly
two neighbors $w_{x_{j-1}}$ and $w_{x_{j}}$ on $C_{k-1}$. The algorithm
modifies $\Gamma_{k-1}$ by performing $\rho+1$ consecutive refinements of the
vertex positions. In the $j$-th refinement, $j=1,\ldots,\rho+1$, the algorithm
shifts each vertex in $\bigcup_{i=x_{j}^{\prime}}^{p}S(w_{i})$ by one unit to
the right; see Fig. 4(a). This implies that vertices $w_{r},\ldots,w_{p}$ of
$C_{k-1}$ have been shifted in total by $\rho+1$ units to the right. Note that
in the algorithm by Chrobak and Kant [11] these vertices would be shifted by
only one unit. The next observations follow from our shifting strategy.

######  Observation 7.

If $P_{k}$ is a chain, then our shifting strategy and the one by Chrobak and
Kant [11] are identical.

######  Observation 8.

If $P_{k}$ is a singleton, then the horizontal distance between any two
consecutive neighbors of $P_{k}$ in $C_{k-1}$ gets increased by one unit in
$\Gamma_{k}$, while in the algorithm by Chrobak and Kant [11] this would only
be the case for $w_{x_{\rho}}$ and $w_{x_{\rho}+1}=w_{r}$.

(a)

(b)

Figure 4: (a) Introducing a singleton $P_{k}$ in $\Gamma_{k-1}$ according to
our modification of the algorithm by Chrobak and Kant [11]; the white-filled
vertices are the identified pivot vertices, and (b) edge-vertex configurations
used in the proof of Lemma 10.

The construction of $\Gamma_{k}$ is completed by placing the vertices of
$P_{k}$ as in the algorithm by Chrobak and Kant [11], i.e., we set either
$x(z_{1})=x(w_{\ell})$ or $x(z_{1})=x(w_{\ell})+1$ (depending on whether
$z_{1}$ is saturated or not, respectively), we place $z_{q}$ at the
intersection of the line of slope $-1$ through $w_{r}$ with the vertical line
through point $x(z_{1})+q-1$ and for $i=1,\ldots,q-1$, vertex $v_{i}$ of
$P_{k}$ is placed $q-i$ units to the left of $z_{q}$. Thus, the contour
condition is maintained in $\Gamma_{k}$.

######  Lemma 9.

The drawing $\Gamma_{k}$ produced by our modification of the algorithm by
Chrobak and Kant [11] is planar and convex.

###### Proof.

The fact that drawing $\Gamma_{k}$ is planar is implied by the original proof
of Chrobak and Kant [11], since the contour condition is maintained for
$\Gamma_{k}$. We next argue about the convexity of $\Gamma_{k}$. Since
$\Gamma_{k-1}$ is convex, if $P_{k}$ is a chain, then $\Gamma_{k}$ is also
convex by Observation 7. Assume that $P_{k}$ is a singleton, i.e.,
$P_{k}=\\{z_{1}\\}$. In this case, we claim that the extra shifts that our
modification performs (see Observation 8) do not affect the convexity of
$\Gamma_{k}$. To prove the claim, consider any two consecutive neighbors
$w_{x_{j}}$ and $w_{x_{j+1}}$ of $z_{1}$ along $(w_{1},\ldots,w_{p})$ of
$C_{k-1}$ with $0\leq j\leq\rho$. If the algorithm by Chrobak and Kant were
about to place a singleton connecting only $w_{x_{j}}$ and $w_{x_{j+1}}$ to
derive $\Gamma_{k}$, then it would perform a shift using as left-critical
vertex the one that our modification identifies as pivot $w_{x_{j}^{\prime}}$,
and as right-critical vertex either the same vertex or its right neighbor
(since the singleton is of degree $2$). Thus, convexity would be maintained.
Applying the same reasoning to any pair of consecutive neighbors of $P_{k}$,
proves that the subdrawing of $\Gamma_{k}$ induced by $G_{k-1}$ is indeed
convex. In addition, the same reasoning implies that Properties 2 and 3 of the
algorithm by Chrobak and Kant [11] also hold. To complete the proof of our
claim, we note that the fact that the faces incident to $P_{k}$ in
$\Gamma_{k}$ are convex follows using the same approach as in the algorithm by
Chrobak and Kant, as the contour condition is maintained. ∎

Note that since the contour condition is maintained and we do not modify the
shift-sets, the fact that Properties 2 and 3 hold in our modification implies
that Lemmata 4, 5 and 6 also hold. To complete the proof of correctness of our
algorithm, we prove in the following lemma that $\Gamma_{k}$ is a disk-link
drawing of $G_{k}$. To ease the proof, we denote by $\Gamma_{k-1}^{\prime}$
the drawing of $G_{k-1}$ obtained after the preparatory shifting in drawing
$\Gamma_{k-1}$ for the introduction of $P_{k}$.

######  Lemma 10.

Let $\Gamma_{k-1}$ be a disk-link drawing of $G_{k-1}$ computed by our
algorithm. The following statements hold:  (i) the edge-vertex resolution of
$\Gamma_{k-1}^{\prime}$ is no less than that of $\Gamma_{k-1}$, and  (ii)
introducing the new edges of $\Gamma_{k}$, which are either part of $P_{k}$ or
incident to the endpoints of $P_{k}$, preserves the edge-vertex resolution to
at least $\frac{1}{2}$.

###### Proof.

Since the drawing of $G_{k-1}$ is planar in $\Gamma_{k}$, it is sufficient to
only consider its faces in order to prove statement (i). To this end, consider
any arbitrary face $f$ in $\Gamma_{k-1}^{\prime}$. If either none or all of
the vertices of $f$ are shifted by the same amount, then statement (i)
obviously holds. Consider now the case where $f$ contains at least one vertex
that is shifted and one vertex that remains stationary in
$\Gamma_{k-1}^{\prime}$. Suppose, for a contradiction, that $f$ contains an
edge $(u,v)$ and a vertex $w$ that is not incident to $(u,v)$ such that
$(u,v)$ intersects the disk of $w$ in $\Gamma_{k-1}^{\prime}$. Since
$\Gamma_{k-1}^{\prime}$ is a grid drawing of $G_{k-1}$, it follows by Property
2 that $(u,v)$ cannot be a black edge. Assume that the slope of $(u,v)$ is
negative (i.e., $(u,v)$ is green or red), as the case in which it is positive
(i.e., $(u,v)$ is blue) is similar. W.l.o.g., further assume that $u$ is above
$v$ in $\Gamma_{k-1}^{\prime}$ (see Fig. 4(b)).

Since $\Gamma_{k-1}^{\prime}$ is a grid drawing of $G_{k-1}$, it follows that,
regardless of whether $w$ was shifted or not, $w$ is neither above nor below
the _horizontal_ strip delimited by the two horizontal lines through $u$ and
$v$ in $\Gamma_{k-1}^{\prime}$ (green in Fig. 4(b)). Similarly, one observes
that $w$ is neither to the left nor to the right of the _vertical_ strip
delimited by the two vertical lines through $u$ and $v$ (blue in Fig. 4(b)).
It follows that $w$ is either in the interior (yellow in Fig. 4(b)) or on the
boundary of the axis-aligned bounding box $B_{uv}$ of the edge $(u,v)$ in
$\Gamma_{k-1}^{\prime}$.

We next argue that $w$ can be neither in the interior of $B_{uv}$ nor along
its two vertical sides, which implies that $w$ is necessarily on one of the
two horizontal sides of $B_{uv}$ (purple in Fig. 4(b)). To see this, assume
for a contradiction that $w$ is in the interior of $B_{uv}$ or along one of
its two vertical sides but not at its corners. Since $\Gamma_{k-1}$ is a disk-
link drawing of $G_{k-1}$ while $\Gamma_{k-1}^{\prime}$ is not, it follows
that the distance between $w$ and $(u,v)$ decreased after the shifting (by one
unit) to obtain $\Gamma_{k-1}^{\prime}$ from $\Gamma_{k-1}$. If the shifting
were sufficiently large (and greater than one unit), then $w$ would be on
different sides of $(u,v)$ in $\Gamma_{k-1}$ and in $\Gamma_{k-1}^{\prime}$,
violating the planarity of the drawing (which is implied by Lemma 5); a
contradiction.

It follows that $w$ is on any of the two horizontal sides of $B_{uv}$, as we
initially claimed. We proceed by considering two subcases depending on whether
$(u,v)$ is on the upper or lower envelope of $f$. Consider first the case
where $(u,v)$ is on the upper envelope of $f$. By Property 3, it follows that
$w$ is on the lower envelope of $f$ and, thus, on the lower edge of $B_{uv}$.
If $w$ and $v$ are not adjacent, the fact that $w$ and $v$ have the same
$y$-coordinate implies that the $x$-coordinate of the bottomost
vertex/vertices of $f$ is delimited by $w$ and $v$ (by Lemma 4). This further
implies that $w$ and $v$ are on the left and right envelopes of $f$,
respectively. Since not all vertices of $f$ are shifted in
$\Gamma_{k-1}^{\prime}$, it follows that, among the vertices of the lower
envelope of $f$, the ones that are shifted are those in the shift-set of the
rightmost vertex of the lower envelope of $f$, which implies that $w$ has not
been shifted. On the other hand, if $w$ and $v$ are adjacent, then the edge
connecting them is black (by Property 2), and thus by Lemma 6, we conclude
again that $w$ is not shifted. In both cases, however, the edge-vertex
resolution of $\Gamma_{k-1}^{\prime}$ cannot be smaller than the one of
$\Gamma_{k-1}$; a contradiction.

Consider now the case where $(u,v)$ is on the lower envelope of $f$. In this
case, vertex $w$ can be either on the lower or on the upper envelope of $f$.
The former case can be ruled out by adopting an argument similar to the one of
the previous paragraph. In the latter case, vertex $w$ is on the top side of
$B_{uv}$. By Property 3, vertices $u$ and $w$ are connected by a path of black
edges contradicting the fact that $(u,v)$ is green, since, by Property 3.vi,
the left edge connecting to a black path on the upper envelope is blue.

We now prove statement (ii). Assume for a contradiction that an edge $(u,v)$
added in $\Gamma_{k}$ during the introduction of $P_{k}$ intersects the disk
of a vertex $w$. Clearly, $w$ belongs to $G_{k-1}$, since by construction we
have no edge-disk intersections between elements of $P_{k}$. Thus, one
endpoint of $(u,v)$, say $u$, belongs to $P_{k}$ and the other, say $v$, to
$G_{k-1}$, i.e., $(u,v)$ is not a black edge. If $(u,v)$ is green, then its
slope in $\Gamma_{k}$ is $-1$, and hence it cannot intersect any non-adjacent
disk. Assume first that $(u,v)$ is blue, and observe that the construction is
such that the horizontal distance between $u$ and $v$ is either $0$ or $1$. In
the former case, $(u,v)$ is vertical and cannot intersect any non-adjacent
vertex-disk. In the latter case, the shifting performed by the algorithm
guarantees that the part of the grid column along which vertex $u$ is placed
that is contained in the horizontal strip bounded by the horizontal lines
through $u$ and $v$ in $\Gamma_{k}$ contains no vertex of $C_{k-1}$, and
therefore edge $(u,v)$ again cannot intersect any non-adjacent vertex disk.
The argument for the case in which $(u,v)$ is red is analogous. ∎

We conclude the proof of our main result by analyzing the area of the produced
drawings and the time complexity of the algorithm.

Proof of Theorem 1. Let $G$ be an $n$-vertex $3$-connected plane graph with
$f$ internal faces. Let $\Gamma$ be a planar drawing of $G$ computed by our
algorithm. By Lemma 9, drawing $\Gamma$ is convex, and, by Lemma 10, its edge-
vertex resolution is at least $\frac{1}{2}$. By the contour condition,
$\Gamma$ is inside a right isosceles triangle, such that it has a horizontal
side (which corresponds to edge $(v_{1},v_{2})$) and a vertical side (which
contains edge $(v_{1},v_{n})$) that have the same length and meet at point
$(0,0)$. In the algorithm by Chrobak and Kant, the value of the width and the
height of this triangle is $n-2$ [11]. The additional unit-shifts due to the
introduction of singletons performed by our modification increase the value of
the width and the height by the same amount $a$ (see Observations 7 and 8). We
focus on the width of $\Gamma$, and we distinguish two cases: either
$\min\\{f,n-3\\}=n-3$ or $\min\\{f,n-3\\}=f$.

  * –

Assume first that $\min\\{f,n-3\\}=n-3$. We develop a charging argument that
charges each additional one-unit shift to the red edges of $G$. In particular,
consider a singleton $P_{k}$. The additional shifts due to this singleton are
two less than its degree in $G_{k}$, which equals the number of red edges
incident to $P_{k}$ in $G_{k}$. It is immediate to see that each red edge is
charged to exactly one additional shift. Hence, the total number of additional
shifts is at most the number of red edges in $G$, which is at most $n-3$
(recall that the red subgraph of $G$ is a forest with at most $n-3$ edges).
Consequently, in this case $a\leq n-3$.

  * –

Assume now that $\min\\{f,n-3\\}=f$. In this case we develop a similar
charging argument, in which we charge each additional one-unit shift to the
internal faces of $G$, rather than to its red edges. Again, consider a
singleton $P_{k}$, and observe that the additional shifts due to this
singleton are two less than its degree in $G_{k}$. This value equals the
number of internal faces incident to $P_{k}$ in $G_{k}$ minus one, in
particular, we can avoid charging the shift to the rightmost internal face
incident to $P_{k}$. It is not difficult to see that each internal face is
charged to at most one additional shift. Hence, the total number of additional
shifts is at most the number of internal faces $f$ in $G$. Consequently, in
this case $a\leq f$.

Finally, we discuss the time complexity. The algorithm by Chrobak and Kant can
be implemented to run in linear time [11]. In particular, the key ingredient
to achieve linear time complexity, is the use of relative coordinates for the
vertices, which avoids shifting entire subgraphs. Since our algorithm only
requires a linear number of additional one-unit shifts and it does not modify
the shift-sets of the vertices, this translates into different relative
coordinates and requires neither additional operations nor different data
structures. Therefore it can be implemented to also run in linear time. ∎

##  4 Open Problems

In this work, we present improvements upon results in [5, 10]. The following
research directions naturally stem from our work.

  1. (i)

Can the bounded edge-vertex resolution requirement be incorporated into an
area lower bound so to improve the one given in [13, 22]?

  2. (ii)

Can the area bound of Theorem 1 be improved in the case where the input graph
is 4-connected? Note that such graphs admit $W\times H$ drawings with $W+H\leq
n-1$ [25] but their edge-vertex resolution may be arbitrarily small.

  3. (iii)

Finally, it is of interest to study the edge-vertex resolution requirement for
strictly convex drawings.

## References

  * [1] S. Alamdari and T. C. Biedl.  Open rectangle-of-influence drawings of non-triangulated planar graphs.  In W. Didimo and M. Patrignani, editors, GD, volume 7704 of LNCS, pages 102–113. Springer, 2012.  doi:10.1007/978-3-642-36763-2\\_10.
  * [2] I. Bárány and G. Rote.  Strictly convex drawings of planar graphs.  Documenta Mathematica, 11:369–391, 2006.  URL: http://eudml.org/doc/53043.
  * [3] G. Barequet, M. T. Goodrich, and C. Riley.  Drawing planar graphs with large vertices and thick edges.  J. Graph Algorithms Appl., 8:3–20, 2004.  doi:10.7155/jgaa.00078.
  * [4] L. Barrière and C. Huemer.  4-labelings and grid embeddings of plane quadrangulations.  Discret. Math., 312(10):1722–1731, 2012.  doi:10.1016/j.disc.2012.01.027.
  * [5] M. A. Bekos, M. Gronemann, F. Montecchiani, D. Pálvölgyi, A. Symvonis, and L. Theocharous.  Grid drawings of graphs with constant edge-vertex resolution.  Comput. Geom., 98:101789, 2021.  doi:10.1016/j.comgeo.2021.101789.
  * [6] T. C. Biedl, A. Bretscher, and H. Meijer.  Rectangle of influence drawings of graphs without filled 3-cycles.  In J. Kratochvíl, editor, GD, volume 1731 of LNCS, pages 359–368. Springer, 1999.  doi:10.1007/3-540-46648-7\\_37.
  * [7] T. C. Biedl, A. Lubiw, S. Mehrabi, and S. Verdonschot.  Rectangle-of-influence triangulations.  In T. C. Shermer, editor, CCCG, pages 237–243, 2016.
  * [8] N. Bonichon, S. Felsner, and M. Mosbah.  Convex drawings of 3-connected plane graphs.  Algorithmica, 47(4):399–420, 2007.  URL: https://doi.org/10.1007/s00453-006-0177-6, doi:10.1007/s00453-006-0177-6.
  * [9] N. Chiba, K. Onoguchi, and T. Nishizeki.  Drawing planar graphs nicely.  Acta Inform., 22:187–201, 1985.  doi:10.1007/BF00264230.
  * [10] M. Chrobak, M. T. Goodrich, and R. Tamassia.  Convex drawings of graphs in two and three dimensions (preliminary version).  In S. Whitesides, editor, SoCG, pages 319–328. ACM, 1996.  doi:10.1145/237218.237401.
  * [11] M. Chrobak and G. Kant.  Convex grid drawings of 3-connected planar graphs.  Int. J. Comput. Geom. Appl., 7(3):211–223, 1997.  doi:10.1142/S0218195997000144.
  * [12] M. Chrobak and T. H. Payne.  A linear-time algorithm for drawing a planar graph on a grid.  Inf. Process. Lett., 54(4):241–246, 1995.  doi:10.1016/0020-0190(95)00020-D.
  * [13] H. de Fraysseix, J. Pach, and R. Pollack.  Small sets supporting Fáry embeddings of planar graphs.  In J. Simon, editor, STOC, pages 426–433. ACM, 1988.  doi:10.1145/62212.62254.
  * [14] G. Di Battista and F. Frati.  Drawing trees, outerplanar graphs, series-parallel graphs, and planar graphs in a small area.  In J. Pach, editor, Thirty Essays on Geometric Graph Theory, pages 121–165. Springer New York, 2013.  URL: https://doi.org/10.1007/978-1-4614-0110-0_9, doi:10.1007/978-1-4614-0110-0_9.
  * [15] G. Di Battista and F. Frati.  A survey on small-area planar graph drawing.  CoRR, abs/1410.1006, 2014.
  * [16] G. Di Battista, R. Tamassia, and L. Vismara.  Output-sensitive reporting of disjoint paths.  Algorithmica, 23(4):302–340, 1999.  URL: https://doi.org/10.1007/PL00009264, doi:10.1007/PL00009264.
  * [17] C. A. Duncan, A. Efrat, S. G. Kobourov, and C. Wenk.  Drawing with fat edges.  Int. J. Found. Comput. Sci., 17(5):1143–1164, 2006.  doi:10.1142/S0129054106004315.
  * [18] S. Felsner.  Convex drawings of planar graphs and the order dimension of 3-polytopes.  Order, 18(1):19–37, 2001.  URL: https://doi.org/10.1023/A:1010604726900, doi:10.1023/A:1010604726900.
  * [19] S. Felsner.  Geometric Graphs and Arrangements.  Advanced Lectures in Mathematics. Vieweg, 2004.  doi:10.1007/978-3-322-80303-0.
  * [20] I. Fáry.  On straight lines representation of planar graphs.  Acta Sci. Math. (Szeged), 11:229–233, 1948.
  * [21] X. He.  Grid embedding of 4-connected plane graphs.  Discret. Comput. Geom., 17(3):339–358, 1997.  URL: https://doi.org/10.1007/PL00009290, doi:10.1007/PL00009290.
  * [22] G. Kant.  Drawing planar graphs using the canonical ordering.  Algorithmica, 16(1):4–32, 1996.  doi:10.1007/BF02086606.
  * [23] K. Miura, T. Matsuno, and T. Nishizeki.  Open rectangle-of-influence drawings of inner triangulated plane graphs.  Discret. Comput. Geom., 41(4):643–670, 2009.  doi:10.1007/s00454-008-9098-2.
  * [24] K. Miura, S. Nakano, and T. Nishizeki.  Grid drawings of 4-connected plane graphs.  Discret. Comput. Geom., 26(1):73–87, 2001.  URL: https://doi.org/10.1007/s00454-001-0004-4, doi:10.1007/s00454-001-0004-4.
  * [25] K. Miura, S. Nakano, and T. Nishizeki.  Convex grid drawings of four-connected plane graphs.  Int. J. Found. Comput. Sci., 17(5):1031–1060, 2006.  URL: https://doi.org/10.1142/S012905410600425X, doi:10.1142/S012905410600425X.
  * [26] T. Nishizeki and M. S. Rahman.  Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing.  World Scientific, 2004.  doi:10.1142/5648.
  * [27] G. Rote.  Strictly convex drawings of planar graphs.  In SODA, pages 728–734. SIAM, 2005.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070535.
  * [28] S. Sadasivam and H. Zhang.  Closed rectangle-of-influence drawings for irreducible triangulations.  Comput. Geom., 44(1):9–19, 2011.  doi:10.1016/j.comgeo.2010.07.001.
  * [29] W. Schnyder.  Embedding planar graphs on the grid.  In SODA, pages 138–148. SIAM, 1990.  URL: http://dl.acm.org/citation.cfm?id=320176.320191.
  * [30] S. K. Stein.  Convex maps.  Proc. American Math. Soc., 2(3):464–466, 1951.
  * [31] E. Steinitz and H. Rademacher.  Vorlesungen über die Theorie der Polyeder.  Julius Springer, Berlin, Germany, 1934.
  * [32] C. Thomassen.  A refinement of Kuratowski’s theorem.  J. Comb. Theory, Ser. B, 37(3):245–253, 1984.  URL: https://doi.org/10.1016/0095-8956(84)90057-1, doi:10.1016/0095-8956(84)90057-1.
  * [33] W. T. Tutte.  How to draw a graph.  Proc. London Math. Soc., 13:743–768, 1963.
  * [34] M. J. van Kreveld.  Bold graph drawings.  Comput. Geom., 44(9):499–506, 2011.  doi:10.1016/j.comgeo.2011.06.002.
  * [35] L. Vismara.  Planar straight-line drawing algorithms.  In R. Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 193–222. Chapman and Hall/CRC, 2013.
  * [36] K. Wagner.  Bemerkungen zum Vierfarbenproblem.  Jahresbericht der Deutschen Mathematiker-Vereinigung, 46:26–32, 1936.
  * [37] H. Zhang and X. He.  Compact visibility representation and straight-line grid embedding of plane graphs.  In F. K. H. A. Dehne, J. Sack, and M. H. M. Smid, editors, WADS, volume 2748 of LNCS, pages 493–504. Springer, 2003.  URL: https://doi.org/10.1007/978-3-540-45078-8_43, doi:10.1007/978-3-540-45078-8\\_43.