# Free Sets in Planar Graphs: History and Applications††thanks: This research
is partially funded by the grants from NSERC and the University Research Chair
of University of Ottawa.

Vida Dujmović Department of Computer Science and Electrical Engineering,
University of Ottawa. Pat Morin School of Computer Science, Carleton
University.

A subset $S$ of vertices in a planar graph $G$ is a _free set_ if, for every
set $P$ of $|S|$ points in the plane, there exists a straight-line crossing-
free drawing of $G$ in which vertices of $S$ are mapped to distinct points in
$P$. In this survey, we review

  * •

several equivalent definitions of free sets,

  * •

results on the existence of large free sets in planar graphs and subclasses of
planar graphs,

  * •

and applications of free sets in graph drawing.

The survey concludes with a list of open problems in this still very active
research area.

###### Contents

  1. 1 Introduction
  2. 2 Four Definitions of Free Sets
  3. 3 Graph Classes with Large Free Sets
    1. 3.1 Subclasses of planar graphs with linear-sized free sets
    2. 3.2 Free Sets in Planar Graphs
    3. 3.3 Free Sets in Max-Degree-$\Delta$ Planar Graphs
  4. 4 Applications
    1. 4.1 Untangling
    2. 4.2 Universal point subsets
    3. 4.3 Simultaneous Geometric Embeddings
      1. 4.3.1 Without Mapping
      2. 4.3.2 With Mapping
    4. 4.4 Column planarity
  5. 5 A One-Bend Variant
  6. 6 Open Problems

##  1 Introduction

In 2005, an online game called _Planarity_ became wildly popular. In this
single-player game, created by John Tantalo based on a concept by Mary
Radcliffe, the player is presented with a straight-line drawing $\Gamma$ of a
planar graph $G$. Although the graph $G$ is planar, the drawing $\Gamma$ is
not crossing-free; some pairs of edges cross each other and an edge may even
contain a vertex in its interior. Since $\Gamma$ draws the edges of $G$ as
straight line segments, the drawing is completely determined by the vertex
locations. The job of the player is to move vertices in the drawing $\Gamma$
in order to obtain a crossing-free drawing of $G$. Since $G$ is planar, Fáry’s
Theorem guarantees that this always possible.

The act of moving some vertices in $\Gamma$ to obtain a crossing-free drawing
is referred to as _untangling_. For a combinatorially inclined player, this
naturally leads to the question: What is the fewest number,
$\operatorname{shift}(\Gamma)$, of vertices that need to be moved in order
untangle $\Gamma$?111The Planarity game actually measures the amount of time
the player takes to accomplish this task, not the number of vertices moved,
but we won’t let facts get in the way of a good story. Equivalently, what is
the maximum number,
$\operatorname{fix}(\Gamma):=|V(G)|-\operatorname{shift}(\Gamma)$ of vertices
that can be kept fixed while untangling $G$? For a planar graph $G$, let
$\operatorname{fix}(G):=\min\\{\operatorname{fix}(\Gamma):\text{$\Gamma$ is a
straight-line drawing of $G$}\\}$. For a family $\mathcal{F}$ of planar
graphs, this defines a function
$\operatorname{fix}_{\mathcal{F}}(n):=\min\\{\operatorname{fix}(G):G\in\mathcal{F},\,|V(G)|=n\\}$.222Technically
$\operatorname{fix}_{\mathcal{F}}(n)$ is undefined if there are no $n$-vertex
graphs in the family $\mathcal{F}$. We will ignore this, since all the graph
families we consider are infinite and have at least one $n$-vertex member for
each $n\in\mathbb{N}$.

Determining the asymptotic growth of $\operatorname{fix}_{\mathcal{F}}(n)$
turns out to be a challenging problem, even for very simple classes
$\mathcal{F}$. In 1998, Mamoru Watanabe had already asked this problem for the
class $\mathcal{C}$ of cycles and we now know that
$\operatorname{fix}_{\mathcal{C}}(n)\in\Omega(n^{2/3})\cap O((n\log n)^{2/3})$
but neither the lower bound, due to Pach and Tardos [46], nor the upper bound,
due to Cibulka [23], is easy to prove. For the class $\mathcal{G}$ of all
planar graphs, it is only known that
$\operatorname{fix}_{\mathcal{G}}(n)\in\Omega(n^{1/4})\cap O(n^{0.4948})$ [17,
42, 38, 20], despite the problem being studied since Pach and Tardos [46]
asked for a polynomial lower bound over $20$ years ago.

In this survey, we study various kinds of vertex subsets of a planar graph
$G$: proper-good sets, collinear sets, free-collinear sets, and free sets.
Each of these definitions is, at first glance, more stringent than the one
that precedes it. Indeed, it follows immediately from definitions that every
free set is a free-collinear set, every free-collinear set is a collinear set,
and every collinear set is a proper-good set. The definition of a proper-good
set is the most relaxed, which makes it easy to find large proper-good sets,
even by hand using a pencil and a paper that contains a crossing-free drawing
of $G$. At the other extreme, free sets satisfy a very strong property that
says we can place the vertices of a free set on any given pointset and then
find locations for the other vertices of $G$ that results in a non-crossing
straight-line drawing of $G$. This makes free sets incredibly useful for many
applications, including untangling.

A key result in this area, discovered over a period of roughly 15 years, is
that all of these definitions are equivalent: A vertex subset in a planar
graph is proper-good if and only if it is collinear if and only if it is free-
collinear if and only if it is free. Meanwhile, proper-good sets, collinear
sets, free-collinear sets, and free sets were being used to resolve problems
in graph drawing and related areas. With the benefit of hindsight, we attempt
to organize and present two decades of results on free sets and their
applications in a way that makes them as easy to understand and as useful as
possible.

The rest of this survey is structured as follows: In Section 2 we present four
definitions of free sets and explain why these four definitions are
equivalent. In Section 3 we present upper and lower bounds on the size of free
sets in planar graphs and various subclasses of planar graphs. In Section 4 we
describe applications of free sets to a variety of graph drawing problems.
Section 6 concludes with a list of open problems and directions for further
research.

##  2 Four Definitions of Free Sets

For definitions of standard graph theoretic terms and notations used in this
survey (such a treewidth, $k$-trees, independent set, etc.) the reader is
referred to the textbook by Diestel [26].

A _drawing_ of a graph is representation of the graph in which each vertex $v$
is represented by a distinct point in the plane and each edge $vw$ is
represented by a simple open curve in the plane the closure of which has $v$
and $w$ as endpoints. When discussing a particular drawing, we do not
distinguish between a vertex and the point that represents it, or an edge and
the curve that represents it. A drawing is a _straight-line_ drawing if each
edge is an open line segment. In a drawing, two edges may have a non-empty
intersection, and an edge may contain a vertex that is not one of its
endpoints. A drawing is a _crossing-free drawing_ if this does not occur: any
two distinct edges are disjoint and no vertex is contained in any edge.333What
we call a crossing-free drawing is sometimes called a _plane_ drawing or an
embedding (in the plane). What we call a straight-line crossing-free drawing
is sometimes called a _geometric embedding_ or _Fáry embedding_.

Recall that for any $n$-vertex planar graph $G_{0}$, on at least $3$ vertices,
it is possible to add edges to $G_{0}$ to obtain a planar graph $G$ with
$3(n-2)$ edges. The resulting graph $G$ is a _triangulation_ : in any
crossing-free drawing of this graph, each of the faces has exactly three edges
on its boundary. A _near-triangulation_ is a biconnected embedded graph whose
inner faces are all _triangles_ , i.e., bounded by three edges. The _dual_
$G^{*}$ of an embedded graph $G$ is a graph whose vertices are the faces of
$G$ that contains an edge between two vertices $f$ and $g$ if the
corresponding faces of $G$ have a common edge on their boundary. For a planar
graph $G$ with outer face $f_{0}$, the _weak dual_ $G^{+}$ of $G$ is defined
as $G+:=G^{*}-f_{0}$, the graph obtained from the dual $G^{+}$ by removing the
vertex corresponds to the outer face $f_{0}$ of $G$. A graph is _outerplanar_
if it has a crossing-free drawing with all its vertices on the outer face. A
graph equipped with such a crossing-free drawing is an _outerplane_ graph. A
_chord_ of a cycle $C$ is an edge that is not part of $C$ but both of its
endpoints are vertices of $C$.

Under our definitions, a _planar_ graph is a graph that has a crossing-free
drawing. _Fáry’s Theorem_ [58, 35, 53] asserts that a graph is planar if and
only if it has a straight-line crossing-free drawing. Today, we use Fáry’s
Theorem without thinking about it, but it is worthwhile spending a moment
reflecting on what would happen if Fáry’s Theorem were not true. There would
be two kinds of planar graphs, topological and straight-line, with the latter
being a special case of the former. Any result proven for straight-line planar
graphs would need a separate proof for topological planar graphs. Edge
contractions, commonly used in inductive proofs for planar graphs would be
off-limits for proofs about straight-line planar graphs. In order to establish
the existence of a straight-line planar graph with some property one would
need to find a topological planar graph with that property and then show that
it has a straight-line crossing-free drawing.

Let $\Gamma$ be a crossing-free drawing of a planar graph $G$. A simple closed
curve444A _simple closed curve_ $C$ is a continuous function
$C:[0,1]\to\mathbb{R}^{2}$ such that $C(0)=C(1)$ and $C(a)\neq C(b)$ for all
$0\leq a<b<1$. $C:[0,1]\to\mathbb{R}^{2}$ is _good_ with respect to $\Gamma$
if $C(0)$ is not contained in any edge or vertex of $\Gamma$. $C$ is _proper_
with respect to $\Gamma$ if, for each edge $e$ of $\Gamma$, the intersection
of $C$ and the closure of $e$ is either empty, consists of a single point
(possibly an endpoint of $e$), or consists of the entire edge $e$. In essence,
a curve that is proper-good with respect to $\Gamma$ behaves the way a line
would behave if $\Gamma$ were a straight-line crossing-free drawing.

Let $S:=(v_{1},\ldots,v_{s})$ be an ordered subset of vertices in a planar
graph $G$.

  1. 1.

$S$ is a _proper-good set_ [24] if there exists a crossing-free drawing
$\Gamma$ of $G$, a curve $C:[0,1)\to\mathbb{R}^{2}$ that is proper-good with
respect to $\Gamma$, and $0<x_{1}<\cdots<x_{s}<1$ such that $C(x_{i})$ is the
location of $v_{i}$ in $\Gamma$, for each $i\in\\{1,\ldots,s\\}$. In other
words, we encounter the vertices of $S$, in order, while traversing $C$.

  2. 2.

$S$ is a _collinear set_ [48] if there exists a straight-line crossing-free
drawing $\Gamma$ of $G$ and $x_{1}<\cdots<x_{s}$ such that $(x_{i},0)$ is the
location of $v_{i}$ in $\Gamma$, for each $i\in\\{1,\ldots,s\\}$.

  3. 3.

$S$ is a _free-collinear set_ [48] if, for any $x_{1}<\cdots<x_{s}$, _there
exists_ a straight-line crossing-free drawing $\Gamma$ of $G$ such that
$(x_{i},0)$ is the location of $v_{i}$ in $\Gamma$, for each
$i\in\\{1,\ldots,s\\}$.

  4. 4.

$S$ is a _free set_ if, for any $x_{1}<\cdots<x_{s}$ and _any_
$y_{1},\ldots,y_{s}$, there exists a straight-line crossing-free drawing
$\Gamma$ of $G$ such that $(x_{i},y_{i})$ is the location of $v_{i}$ in
$\Gamma$, for each $i\in\\{1,\ldots,s\\}$.

We note that our definitions deviate from much of the literature by treating
$S$ as an ordered set. Later, we may say that some (unordered) vertex subset
$S$ of $G$ is a proper-good, collinear, free-collinear, or free set. In these
cases, we mean that there is some permutation of $S$ that defines an ordered
set that satisfies the relevant definition. When we want to emphasize the
difference between these two we will say that (an ordered set) $S$ is an
_ordered free set_ or that (a set) $S$ is an _unordered free set_. This
distinction becomes important when discussing two or more graphs with the same
vertex set. A set $S$ of vertices may be an unordered free set in two graphs
$G_{1}$ and $G_{2}$ but there may be no permutation of $S$ that is an ordered
free set in $G_{1}$ and in $G_{2}$.

A few properties of free sets are immediate from the definition and we will
use them throughout. If $S$ is an ordered free set in a graph $G$ then:

  * •

the reversal of $S$ is an ordered free set in $G$;

  * •

$S$ is an ordered free set in any subgraph of $G$ that spans $S$; and

  * •

any subsequence of $S$ is an ordered free set in $G$.

Unordered collinear sets and unordered free-collinear sets were defined first
by Ravsky and Verbitsky [48] and were implicit in [17]. In fact, Ravsky and
Verbitsky [48] posed the equivalence between (unordered) collinear sets and
(unordered) free-collinear set as an open question, and conjectured a negative
answer. Thus 1 below disproves that conjecture. Proper-good sets (as unordered
sets) were introduced first by Da Lozzo et al. [24].

Before continuing, we make a remark about pointsets whose ${x}$-coordinates
are not all distinct, since the definition of (ordered) free set appears to
disallow these. However, we claim that for any unordered free set $S$ in a
planar graph $G$, and _any_ set $P$ of $|S|$ points in the plane, there exists
a straight-line crossing-free drawing of $G$ in which each vertex in $S$ is
mapped to some point in $P$. If all the points in $P$ have distinct
${x}$-coordinates then the claim follows immediately from the definition of
ordered free set. If this is not the case, then a slight rotation of $P$ gives
a pointset $P^{\prime}$ in which each point has a distinct ${x}$-coordinate.
Now $G$ has a straight-line crossing-free drawing $\Gamma^{\prime}$ in which
each vertex in $S$ maps to a point in $P^{\prime}$. Applying the inverse
rotation to $\Gamma^{\prime}$ gives a drawing $\Gamma$ in which each vertex in
$S$ maps to a point in $P$.

The proof of Lemma 1, below, gives one example of why definitions based on
ordered sets are useful. Another example, discussed in Section 4, is the
problem of simultaneous embedding with mapping.

######  Lemma 1.

Let $G$ be a planar graph that has a free set of size at least $k$. Then
$\operatorname{fix}(G)\geq\sqrt{k}$.

###### Proof.

Let $S$ be an ordered free set in $G$ of size $k$. Fix any straight-line
drawing $\Gamma$ of $G$ and, without loss of generality (by a slight rotation,
if necessary) assume that no two vertices of $\Gamma$ have the same
${x}$-coordinate. Let $(S,\prec)$ be the partial order in which $v\prec w$ if
and only if $v$ appears before $w$ in $S$ and the ${x}$-coordinate of $v$ in
$\Gamma$ is less than the ${x}$-coordinate of $w$ in $\Gamma$.

Suppose $(S,\prec)$ contains a chain $v_{1}\prec\cdots\prec v_{\ell}$ of
length $\ell\geq\sqrt{k}$. Then $(v_{1},\ldots,v_{\ell})$ is a free set since
it is a subsequence of $S$. For each $i\in\\{1,\ldots,\ell\\}$, let
$(x_{i},y_{i})$ be the coordinates given to $v_{i}$ in $\Gamma$. By the
definition of free set, $G$ has a straight-line crossing-free drawing in which
$v_{i}$ is mapped to $(x_{i},y_{i})$, for each $i\in\\{1,\ldots,\ell\\}$.
Therefore, $\operatorname{fix}(\Gamma)\geq\ell\geq\sqrt{k}$ for any straight-
line drawing $\Gamma$ of $G$. Therefore $\operatorname{fix}(G)\geq\sqrt{k}$.

To deal with the case in which $\prec$ contains no chain of length at least
$\sqrt{k}$ we use the fact that the ordered set  S obtained by reversing the
order of $S$ is also a free set. Let $(S,\prec^{\prime})$ be the partial order
on the elements of  S in which $v\prec w$ if and only if $v$ appears before
$w$ in  S and the ${x}$-coordinate of $v$ in $\Gamma$ is less than the
${x}$-coordinate of $w$ in $\Gamma$. By Dilworth’s Theorem, $(S,\prec)$
contains an antichain of length at least $\sqrt{k}$ and the elements of this
antichain form a chain in $(\reflectbox{S},\prec^{\prime})$. Now we proceed as
in the previous paragraph. ∎

For most classes $\mathcal{X}$ of planar graphs, including trees, outerplanar
graphs, and all planar graphs, the best known bounds (and for some classes
asymptotically optimal bounds) for $\operatorname{fix}_{\mathcal{X}}(n)$ can
be obtained by an application of Lemma 1, along with a result on free sets in
graphs in the class $\mathcal{X}$ [38, 24, 17, 48]. The sole exception is the
class $\mathcal{C}$ of cycles, for which Cibulka [23] uses repeated
applications of the Erdős-Szekeres Theorem to obtain a lower bound of
$\Omega(n^{2/3})$.

As discussed in the introduction, the following theorem provides the main
motivation for this survey.

######  Theorem 1.

Let $G$ be a planar graph and let $S$ be an ordered subset of $V(G)$. Then the
following statements are equivalent:

  1. 1.

$S$ is a (ordered) proper-good set.

  2. 2.

$S$ is a (ordered) collinear set.

  3. 3.

$S$ is a (ordered) free-collinear set.

  4. 4.

$S$ is a (ordered) free set.

Note that, unlike the other three definitions, the definition of proper-good
set is purely combinatorial/topological; it has no mention of straight lines
or vertex coordinates. In this respect, 1 plays a role similar to Fáry’s
Theorem. Using the proper-good set definition allows purely combinatorial
methods to be used in the search for free sets. For any proper-good set there
is a short easily-verifiable certificate (a crossing-free drawing of $G$ and a
description of the curve $C$) that $S$ is indeed a proper-good set. In
contrast, in order to show directly that $S$ is a free-collinear set (or a
free set) involves proving a fact that must hold for all choices of
$x_{1},\ldots,x_{k}$ (or $(x_{1},y_{1}),\ldots,(x_{k},y_{k})$, respectively).
Working with this definition directly would involve (at the very least) a
significant amount of linear algebra.

The proof of 1 is spread across a few different works [24, 29, 17], which we
describe below. First we remark that it is immediate from the definitions that
every free set is a free-collinear set and every free-collinear set is a free
set. It is also easy to see that every collinear set is a proper-good set by
taking a straight-line crossing-free drawing $\Gamma$ of $G$ with the vertices
of the (ordered) collinear set $S$ on the ${x}$-axis in increasing order of
${x}$-coordinate. Let $s$ be a line segment that is contained in the
${x}$-axis and that contains every intersection between $\Gamma$ and the
${x}$-axis in its interior. Then $s$ is proper and good with respect to
$\Gamma$. Finally, make $s$ into a closed curve by joining the endpoints of
$s$ with a curve $C$ that completely avoids $\Gamma$.

We now address the other directions.

##### Every proper-good set is a collinear set:

The proof that every proper-good set is a collinear set is due to Da Lozzo et
al. [24] and is illustrated in Fig. 1. For each edge of $G$ that crosses $C$,
the authors introduce a dummy vertex (white vertices in Fig. 1(a)) that splits
the edge into two edges with a common vertex on $C$. The resulting graph
$G^{\prime}$ then has three types of vertices: a set $X$ of inner vertices
(contained in the interior of $C$), a set $Y$ of boundary vertices (contained
in $C$) and a set $Z$ of outer vertices (the vertices in the exterior of $C$).
These steps are depicted in Fig. 1(a).

|  |
---|---|---
(a) | (b) | (c)
Figure 1: Showing that every proper-good set is a collinear set. Dummy
vertices are hollow circles and elements of $S$ are filled circles.

They then use Tutte’s Convex Embedding Theorem [57] twice: Once to find a
straight-line crossing-free drawing of $G^{\prime}[X\cup Y]$ with all vertices
of $X$ below the ${x}$-axis and all vertices of $Y$ on the ${x}$-axis, and a
second time to find a straight-line crossing-free drawing of $G^{\prime}[Y\cup
Z]$ with the vertices of $Z$ above the ${x}$-axis. This gives a straight-line
crossing-free drawing $\Gamma^{\prime}$ of $G^{\prime}$, as depicted in Fig.
1(b). The straight-line crossing-free drawing $\Gamma^{\prime}$ is almost a
straight-line crossing-free drawing of $G$ except that the edges that properly
intersect $C$ are represented by two line segments, one below and one above
the ${x}$-axis. The authors then apply a result of Pach and Tóth [47] that
shows the edges in this crossing-free drawing can be straightened without
changing the ${y}$-coordinate of any vertex, as depicted in Fig. 1(c). In
particular, in the resulting straight-line crossing-free drawing of $G$, the
vertices of $G$ intersected by $C$ remain on the ${x}$-axis, as required.

A few notes on the proof are in order. First, we recall that the proof of
Tutte’s Convex Embedding Theorem is mostly algebraic: it involves setting up a
system of linear equations whose solution determines the coordinates of the
vertices in the straight-line crossing-free drawing. Second, we note that the
preceding proof _almost_ proves that every proper-good set is a _free_
-collinear set. Tutte’s theorem allows us to choose the ${x}$-coordinates of
the vertices in $Y$, including the vertices in $S$. However, the straightening
step, which converts $\Gamma^{\prime}$ into $\Gamma$ by straightening the
edges that cross the ${x}$-axis, changes the ${x}$-coordinates of the
vertices.

##### Every collinear set is a free-collinear set:

The proof that every collinear set is a free-collinear set is due to Dujmović
et al. [29]. Prior to this, Da Lozzo et al. [24] had established the
equivalence of collinear and free-collinear sets for the class of planar
$3$-trees and asked again if this equivalence was true in general. In
subsequent years this repeatedly lead to the question (originally posed by
Ravsky and Verbitsky [48]) “is every collinear set free?”. The proof of
Dujmović et al. [29] has two main parts, which we outline below. If
$S:=(v_{1},\ldots,v_{s})$ is an ordered collinear set, then $G$ has a
straight-line crossing-free drawing $\Gamma$ in which the vertices of $S$
appear, in order, on the ${x}$-axis. The goal is to show that, for any
$x_{1}<\cdots<x_{s}$, the vertex $v_{i}$ can be moved to $(x_{i},0)$, for each
$i\in\\{1,\ldots,s\\}$, such that the resulting drawing is a straight-line
crossing-free drawing. By adding (straight-line) edges to $\Gamma$, we may
assume that $G$ is a triangulation. In the following, when we say that an edge
or a face _properly intersects_ the ${x}$-axis, we mean that the edge or the
face contains points that are strictly above and points that are strictly
below the ${x}$-axis.

The first part of the proof is combinatorial. In this part, a sequence of
modifications is done to $G$ with the end goal of obtaining a triangulation
$G^{\prime}$ that has an (no longer straight-line) crossing-free drawing
$\Gamma^{\prime}$ with following properties (see Fig. 2(c)):

  1. (P1)

Every vertex in $S$ is a vertex of $G^{\prime}$ and is mapped to the same
location (on the ${x}$-axis) in both $\Gamma$ and $\Gamma^{\prime}$.

  2. (P2)

The closure of each edge of $\Gamma^{\prime}$ intersects the ${x}$-axis in at
most one point.

  3. (P3)

For each vertex $v\in S$ there are exactly two faces of $G^{\prime}$ incident
on $v$ that properly intersect the ${x}$-axis.

  4. (P4)

If an edge $vw$ of $G^{\prime}$ has no endpoint in $S$ then $vw$ properly
crosses the ${x}$-axis or $vw$ is on the boundary of two faces $vwa$ and $vwb$
and the closure of each of these faces intersects the ${x}$-axis.

Note that Item 1 and Item 2 imply that no edge of $G^{\prime}$ has both
endpoints in $S$. For reasons discussed below, we may assume that $G$ has no
separating triangles and that no separating triangles are created during these
operations.

To obtained $G^{\prime}$ we apply three types of operations, two of which are
illustrated in Fig. 2.  (1) If some edge with no endpoint in $S$ is incident
on two faces, neither of which properly intersect the ${x}$-axis, then this
edge is contracted (the orange edge in Fig. 2(a) meets those conditions and
its contraction results in an embedded graph depicted in Fig. 2(b)). This
operation eliminates these two faces.  (2) If some edge with no endpoints in
$S$ is incident on one face whose closure is disjoint from the ${x}$-axis,
whose other incident face properly intersects the ${x}$-axis, and meets some
other technical conditions,555These technical conditions ensure that, after
drawing $G^{\prime}$ the union of the two faces incident on the flipped edge
is a convex quadrilateral. then this edge is flipped (the lilac edge in Fig.
2(b) meets the necessary conditions and its flipping results in an embedded
graph depicted in Fig. 2(c)). This edge flip replaces the two faces incident
to the original edge with two faces that each properly intersect the
${x}$-axis.  (3) Finally, any edge with both endpoints in $S$ is flipped.
After this flip, the flipped edge and the two faces incident to it properly
intersect the ${x}$-axis.  These operations (contractions and flips) are done
exhaustively, one by one, in any order. The operations maintain that $S$ is a
proper-good set in $G^{\prime}$. As discussed above, either of these
operations may introduce a separating triangle in $G^{\prime}$. How this is
handled is explained below. Once these operations are done exhaustively,
removing the edges of $G^{\prime}$ both of whose endpoints are either strictly
above or strictly below ${x}$-axis (see the green edges in Fig. 2(c)) yields a
structure, called an _A-graph_ (see Fig. 2(d)), in which every face is either
a quadrilateral whose four edges each intersect the ${x}$-axis or have an
endpoint on the ${x}$-axis or a triangle with vertices above, on, and below
the ${x}$-axis. The main task now is to find a straight-line crossing-free
drawing of this $A$-graph so that the vertices of $S$ are moved to the
specified locations on the ${x}$-axis. Once we achieve that, the edge-removal,
flipping, and contracting operations are easily undone without changing the
locations of vertices in $S$, resulting in straight-line crossing-free drawing
of $G$ with the vertices of $S$ at their specified locations on the
${x}$-axis.

|
---|---
(a) | (b)
|
(c) | (d)
Figure 2: Modifying a triangulation to obtain an $A$-graph.

Finding a straight-line crossing-free drawingof this $A$-graph so that the
vertices of $S$ are placed to the specified locations on the ${x}$-axis is the
goal of the second part of the proof, which involves a combination of linear
algebra and graph theory. The authors prove a very strong statement about the
A-graph $G^{\prime}$. They show that it is possible to obtain a straight-line
crossing-free drawing of $G^{\prime}$ in which the intersection point of the
closure of each edge with the ${x}$-axis is specified, subject to the ordering
constraints imposed by the crossing-free drawing of $G^{\prime}$. Note that
this implies that $S$ is a free-collinear set in $G^{\prime}$ since each
vertex in $S$ is incident to an edge of $G^{\prime}$ (recall that no edge
incident to a vertex of $S$ is flipped or contracted unless both of its
endpoints are on the ${x}$-axis). The vertex $v_{i}$ has at least three
incident edges in $G^{\prime}$. By specifying that the closure of each of
these edges must intersect the ${x}$-axis at $(x_{i},0)$ we ensure that
$v_{i}$ is mapped to $(x_{i},0)$.

In addition to specifying the location where each edge crosses the ${x}$-axis,
the locations of the three vertices $x,y,z$ on the convex hull of this
crossing-free drawing (the vertices marked with  in Fig. 2(d)) can be chosen,
provided that the choice agrees with the choice of intersection points chosen
for the edges induced by $x,y,z$ (the intersections marked with $\times$ in
Fig. 2(d)). This latter requirement justifies the assumption that the graph
does not contain separating triangles: The subgraph in the closure of the
exterior of a separating triangle $xyz$ can be drawn inductively. This
determines the locations of $x$, $y$, and $z$ which are then specified when
inductively drawn the graph in the closure of the interior of the separating
triangle.

The proof works by assigning slopes to the edges in $G^{\prime}$. To avoid
vertical edges, it is helpful to rotate the coordinate system by $90$ degrees
so that the roles of the x- and y-axes swap. To prove this stronger claim
about A-graphs, the authors set up a system $M$ of linear equations whose
variables are the slopes of the edges of $G^{\prime}$ and whose coefficients
are determined by the (given) intersection location of each edge with the
${y}$-axis. Most of the equations in $M$ correspond to the fact that three or
more edges incident to a common vertex $v$ must intersect in a single point
(the location of $v$).666Some additional constraints, call proportionality
constraints, are placed on the slopes of edges incident to vertices on the
${y}$-axis.

The hardest step in this proof is to show that the linear system $M$ has a
unique solution. Here, the authors leverage the fact that $S$ is a proper-good
set in $G^{\prime}$ and, therefore, a collinear set in $G^{\prime}$.
Therefore, $G^{\prime}$ has a straight-line crossing-free drawing $\Gamma_{0}$
in which the vertices of $S$ appear, in order, on the ${y}$-axis. From this
straight-line crossing-free drawing $\Gamma_{0}$, one can read off a system
$M_{0}$ of linear equations that has the same structure as $M$ but with
different coefficients (that are determined by the ${y}$-coordinates of
vertices in $S$ in $\Gamma_{0}$). The system $M_{0}$ has a solution, namely
the solution given by the slopes of the edges in $\Gamma_{0}$. The authors
first show that this solution to $M_{0}$ is unique. The final step involves
continuously modifying the coefficients in $M_{0}$ to obtain a continuum of
linear systems $M_{t}$, $0\leq t\leq 1$ where $M_{1}=M$. Using the fact that
$M_{0}$ has a unique solution as a starting point, they are then able to show
that $M_{t}$ has a unique solution for each $0\leq t\leq 1$. In particular,
$M_{1}=M$ has a solution, which determines the desired straight-line crossing-
free drawing of $G^{\prime}$

##### Every free-collinear set is a free set:

The equivalence between free-collinear sets and free sets has a
disappointingly easy proof. The following argument appears in Bose et al.
[17], but similar “perturb and scale” arguments are fairly common.

Let $S:=(v_{1},\ldots,v_{s})$ be a free-collinear set in $G$ and let
$x_{1}<\cdots<x_{s}$ and $y_{1},\ldots,y_{s}$ be real numbers. Since $S$ is a
free-collinear set in $G$, $G$ has a straight-line crossing-free drawing in
$\Gamma_{0}$ where $v_{i}$ is at $(x_{i},0)$ for each $i\in\\{1,\ldots,s\\}$.
It follows easily from the definition of straight-line crossing-free drawing
that there exists some $\epsilon>0$ such that perturbing each of the vertices
in $\Gamma_{0}$ by at most $\epsilon$ results in another straight-line
crossing-free drawing $\Gamma_{0}^{\prime}$. Let
$y:=\max\\{|y_{1}|,\ldots,|y_{s}|\\}$. Define $\Gamma_{0}^{\prime}$ by moving
$v_{i}$ to $(x_{i},\epsilon y_{i}/y)$, for each $i\in\\{1,\ldots,s\\}$ and
leaving the other vertices of $G$ fixed. Then each vertex in
$\Gamma_{0}^{\prime}$ has been moved a distance of at most $\epsilon$ from its
location in $\Gamma_{0}$, so $\Gamma_{0}^{\prime}$ is a straight-line
crossing-free drawing of $G$. Finally, multiply the ${y}$-coordinate of each
vertex by $y/\epsilon$ to obtain a final straight-line crossing-free drawing
$\Gamma$. This y-scaling is an affine transformation that does not introduce
any crossings, so $\Gamma$ is a straight-line crossing-free drawing of $G$
and, for each $i\in\\{1,\ldots,s\\}$, $\Gamma$ places $v_{i}$ at
$(x_{i},y_{i})$.

##  3 Graph Classes with Large Free Sets

What is the maximum size of a free set that is guaranteed to exist in any
$n$-vertex planar graph? Ravsky and Verbitsky [48] observed that upper bounds
on this value can be obtained from existing work on the circumference of cubic
triconnected planar graphs. They observe that if a triangulation $G$ has a
collinear set of size $\ell$ (and thus a large free set by 1), then its dual
graph $G^{*}$ (which is a cubic triconnected planar graph) has a cycle of
length $\Omega(\ell)$. The length $c(G^{*})$ of a longest cycle in $G^{*}$ is
called the _circumference_ of $G^{*}$. The circumference of cubic triconnected
planar graphs has a long and rich history dating back to at least 1884 when
Tait [55] conjectured that every such graph is Hamiltonian.

Tait’s Conjecture was famously disproved in 1946 by Tutte, who gave an example
of a non-Hamiltonian cubic triconnected planar graph having 46 vertices [56].
Repeatedly replacing vertices of Tutte’s graph with copies of itself gives a
family of graphs, $\langle G_{i}:i\in\mathbb{N}\rangle$ in which $G_{i}$ has
$46\cdot 45^{i}$ vertices and circumference at most $45\cdot 44^{i}$. Stated
another way, $n$-vertex members of the family have circumference
$O(n^{\sigma})$, for $\sigma=\log_{45}(44)<0.9941$. The current best upper
bound of this type is due to Grünbaum and Walther [40] who construct a family
of cubic triconnected planar graphs in which $n$-vertex members have
circumference $O(n^{\sigma})$ for $\sigma=\log_{23}(22)<0.9859$. The dual of
such a graph is a triangulation having $\Theta(n)$ vertices whose largest free
set has size $O(n^{\sigma})$.

Since not all planar graphs have free sets of linear size, it is natural to
ask which subclasses of planar graphs do. Two obvious candidates are planar
graphs of maximum degree $\Delta$ and planar graphs of treewidth at most $k$.
However, constructions like those described above can be used to rule out this
possibility except for $\Delta<7$ and $k<5$, as we now explain.

Owens [45] constructs a family of $n$-vertex cubic triconnected planar graphs
whose faces have size at most $7$, and that contain no cycle of length
$\Omega(n^{0.9976})$. The dual of such a graph is a triangulation having
$\Theta(n)$ vertices and maximum-degree $7$ whose largest free set has size
$O(n^{0.9976})$.

Ravsky and Verbitsky [48] show that a construction based on the Barnette-
Bosák-Lederberg graph produces triangulations of treewidth at most $8$ whose
largest free set has size $o(n)$. Da Lozzo et al. [24] observe that the
recursive construction based on Tutte’s counterexample to Tait’s Conjecture
[56] leads to a triangulation of treewidth at most $5$ whose largest free set
has size $O(n^{0.9941})$.

Cano et al. [20] also use upper bounds on the circumference of cubic
triconnected planar graphs, along with the Erdős-Szekeres Theorem to show that
$\operatorname{fix}_{\mathcal{G}}(n)\in O(n^{0.4948})$.

Since not all planar graphs have linear size free sets, we first consider the
subclasses of planar graphs that do admit such large free sets (in Section
3.1). We then study general planar graphs (in Section 3.2). The relationship
between these two key graph parameters (largest free set and circumference) is
then used to obtain strong bounds for bounded-degree planar graphs (in Section
3.3).

###  3.1 Subclasses of planar graphs with linear-sized free sets

A _level planar drawing_ of a graph is a straight-line crossing-free drawing
in the plane, such that the vertices are placed on a sequence of parallel
lines (called _levels_), where each edge joins vertices in two consecutive
levels. For example, a natural straight-line crossing-free drawing of a tree
$T$, with root $r$, places each vertex of $T$ that is at distance $i$ from $r$
on the line $y=-i$. Thus, trees have level planar drawings.

The following easy argument shows that $n$-vertex graphs that have level
planar drawings have free sets of size at least $n/2$. See Fig. 3. Starting
with a level planar drawing $\Gamma$, create a simple closed curve $C$ that
coincides with the drawing in some set of levels. If $C$ does not contain any
two consecutive levels of $\Gamma$, then $C$ intersects $\Gamma$ only in the
vertices of $G$ that form an independent set. Such a curve is thus a proper-
good curve, and by having it intersect every second level of $G$ one can
ensure that $\Gamma$ contains at least $\lceil n/2\rceil$ vertices of $G$.

|
---|---
Figure 3: Two proper-good curves in a level planar graph.

Note that the preceding argument holds even if the definition of level planar
drawings is relaxed to allow: consecutive vertices within a level to be
adjacent; edges between consecutive levels to be strictly $y$-monotone instead
of straight; and even edges to go between non-consecutive levels (as long as
they are not too far). This leads to the following definition: An _$s$ -span
weakly level planar_ drawing is a crossing-free drawing in the plane, such
that the vertices are placed on a sequence of parallel lines, where each edge
$e$ is either a straight-line segment between two consecutive vertices on the
same level (called, a _horizontal edge_ , or a strictly $y$-monotone curve
that intersects at most $s+1$ levels (called, a _vertical edge_). A graph is
_$s$ -span weakly level planar_ if it has an $s$-span weakly level planar
drawing. See [36] for example, for a similar definition. The following lemma
formalizes the usefulness of this notion for obtaining free sets. This
connection between $1$-span weakly level planar level planar drawings have
been observed by [48].

######  Lemma 2.

Every $n$-vertex $s$-span weakly level planar graph $G$ has a free set of size
at least $\lceil n/(s+1)\rceil$.

###### Proof.

Refer to Fig. 4. Number the levels in an $s$-span weakly level planar drawing
$\Gamma$ of $G$ by $0,1,2\dots$. Then for some $i\in\\{0,1,\dots,s\\}$, the
union of levels $j=i\mod(s+1)$ has at least $\lceil n/(s+1)\rceil$ vertices,
$S$ of $G$. Moreover $G[S]$ is a forest of paths (induced by the horizontal
edges and the vertices on these levels). As in the case of level planar
graphs, depict now a closed curve $C$ such that $C$ contains these levels of
$\Gamma$ (and thus the vertices of $S$) such that $C$ intersects each vertical
edge of $\Gamma$ at most once. This is possible since vertical edges are
$y$-monotone and their endpoints lie on the levels whose difference (the
absolute value) is at most $s$. Such a curve $C$ is a proper-good curve and
thus by 1, $S$ a proper-good set whose vertices are ordered by their
appearance on $C$. ∎

Figure 4: A $2$-span weakly level planar drawing and a proper-good curve that
contains every third level.

Exactly the same proof used to show Lemma 2 shows the following “hereditary”
variant:

######  Lemma 3.

For any $s$-span weakly level planar graph $G$ and any subset $X$ of vertices
in $G$, $G$ has a free set $S\subseteq X$ of size at least
$\lceil|X|/(s+1)\rceil$.

These lemmas have several immediate consequences. Firstly, as argued above,
breath-first-search leveling of trees can be easily turned into level planar
drawings (and thus, $1$-span weakly level planar drawings). Similarly, breath-
first-search leveling of outerplanar graphs can be turned into $1$-span weakly
level planar drawings of such graphs, as proved by Felsner et al. [32]. A
natural way to draw the $n\times n$ grid graph is a 1-level planar drawing.
More generally, Bannister et al. [7] show that squaregraphs are $1$-span
weakly level planar. A _squaregraph_ is a graph that has a crossing-free
drawing in which each bounded face is a $4$-cycle and each vertex either
belongs to the unbounded face or has four or more incident edges. The same
authors also show that Halin graphs are $1$-span weakly level planar. Giacomo
et al. [36] identified several classes of planar graphs that are $s$-span
weakly level planar, for some constant $s$.

######  Corollary 1.

Let $G$ be a $n$-vertex tree, outerplanar graph, Halin graph, or square graph
and let $X$ be any subset of vertices of $G$. The $G$ has a free set
$S\subseteq X$ of size at least $\lceil|X|/2\rceil$. In particular, $G$ has a
free set of size at least $\lceil n/2\rceil$.

The $\lceil n/2\rceil$ lower bound for trees appears in [17] in the context of
untangling. The extension to outerplanar graphs appears in [38], also in the
context of untangling. The proof for outerplanar graphs by Goaoc et al. [38]
produces a proper-good curve that is qualitatively different than the one in
1. See Fig. 5. In particular, the curve obtained there is contained in the
closure of the outer face of $G$ and contains $G$ in the closure of its
interior. This distinction turns out to be important when studying general
planar graphs. Goaoc et al. [38] prove the following result although it is not
stated in this form. We include a variant of their proof.

|  |
---|---|---
(a) | (b) | (c)
Figure 5: An edge-maximal outerplane graph $G$; (b) a proper good curve
guaranteed by Lemma 4; and (c) a proper good curve guaranteed by Lemma 2.

######  Lemma 4.

Let $G$ be an edge-maximal $n$-vertex outerplane graph for some $n\geq 4$.
Then there exists a proper-good curve $C$ that is contained in the closure of
the outer face and $C$, that contains $G$ in the closure of its interior, and
that contains at least $\frac{n}{2}+1$ vertices of $G$. Thus the vertices in
$C$ form a proper-good set of size at least $\frac{n}{2}+1$.

###### Proof.

Since $G$ is edge-maximal and $n\geq 4$, the boundary of the outer face is a
cycle, denoted by $O$. Consider a set $S\subseteq V(G)$ that has the following
two properties: $G[S]$ induces a forest of paths and all the edges of $G[S]$
lie on $O$. It is easy to see that every such set $S$ is a proper-good set of
$G$. Moreover, it is not hard to produce a proper-good curve that is contained
in the closure of the outer face of $G$ and contains the vertices and edges of
$G[S]$ by closely tracing the outer face of $G$.

We now prove that $G$ has such a set $S$ of claimed size. Let $T$ denote the
weak dual of $G$. $T$ is a tree on at least two vertices since $n\geq 4$. Each
vertex of $T$ has a degree $1$, $2$ or $3$, so $T$ is a binary tree. Let
$t_{1}$ and $t_{3}$ denote the number of degree $1$ and degree $3$ vertices in
$T$, respectively. It is well known that in every binary tree $t_{1}=t_{3}+2$.

Consider now the graph $G^{\prime}$ obtained from $G$ by removing the edges
with both endpoints on the outer face (in other words, $G$’ contains only the
chords of $O$). Every independent set in $G^{\prime}$ meets the two conditions
imposed on $S$ earlier. Thus it remains to prove that $G^{\prime}$ has
independent set $S$ of size $\frac{n}{2}+1$. Construct $S$ greedily in
$G^{\prime}$ as follows: put in $S$ the vertex of $G^{\prime}$ of minimum
degree; remove that vertex and its neighbors from $G^{\prime}$ to obtain a new
$G^{\prime}$; and, repeat. $S$ is clearly an independent set in $G^{\prime}$.
It remains to show that it has the claimed size. In the moment a vertex is
placed in $S$ its degree in current $G^{\prime}$ was 0, 1 or 2. Let $n_{i}$
denote the number of vertices that had degree $i$ when they were placed in
$S$. Thus $|S|=n_{0}+n_{1}+n_{2}$. From the description of the algorithm, it
follows that $n=n_{0}+2n_{1}+3n_{2}$. Finally, each leaf of $T$ contributes
$1$ to $n_{0}$. Thus $n_{0}\geq t_{1}$. Each vertex of $G^{\prime}$ that
contributes to $n_{2}$ corresponds to a unique face whose dual vertex has
degree $3$ in $T$. Thus $n_{2}\leq t_{3}$. Combining that inequality with the
earlier obtained equality, $t_{1}=t_{3}+2$, we get that $n_{0}\geq n_{2}+2$.
To summarize, we have the two equations and one inequality:

$|S|=n_{0}+n_{1}+n_{2}\qquad\qquad n=n_{0}+2n_{1}+3n_{2}\qquad n_{0}-n_{2}\geq
2\enspace.$

Replacing $n_{1}$ in the first equality with $n_{1}=(n-n_{0}-3n_{2})/2$
obtained from the second equality gives
$|S|=\frac{n}{2}+\frac{n_{0}-n_{2}}{2}$. Combined with the last inequality, we
obtain the claimed result. ∎

Ravsky and Verbitsky [48] extend this result even further to show that all
graphs of treewidth $2$ have free collinear sets of linear size. This
extension does not follow from the argument used to prove Lemma 2, since there
is a class of planar graphs of treewidth at most $2$ whose graphs do not have
$s$-span weakly level planar drawings for any fixed $s$ [11].

Having a weakly level planar drawing of small span is a too strong of a
condition to provide a general tool for finding large free sets in wider
classes of planar graphs. In addition to the example of $2$-trees, there are
planar graphs of bounded pathwidth, illustrated in Fig. 6 that do not have
$o(n)$-span weakly level planar drawings (a result that can be derived from
Biedl [11, Theorem 5]) and yet each graph in the class has an induced path of
length $(n-1)/2$ that can be covered by a proper-good curve and thus the
vertices on that path form a free set of size at least $(n-1)/2$, by 1.

|
---|---
Figure 6: A graph of pathwidth-$2$ with no $o(n)$-span weakly level planar
drawing that contains a free set of size $(n-1)/2$

Da Lozzo et al. [24] show that the linear bound for treewidth $2$ graphs [48]
extends to planar graphs of treewidth at most $3$:

######  Theorem 2 ([24]).

Every $n$-vertex planar graph of treewidth at most three has a free set of
size at least $\lceil\frac{n-3}{8}\rceil$.

As noted in the introduction to this section, 2 cannot be generalized to all
$n$-vertex planar graphs of treewidth at most $5$. This leaves open the
question of whether a linear bound is possible for planar graphs of treewidth
at most $4$.

For planar graphs of _large_ treewidth, Da Lozzo et al. [24] use the fact that
any planar graph of treewidth $k$ contains a $k\times k$ grid-minor to show
that planar graphs with large treewidth have large free sets:

######  Theorem 3 ([24]).

Every planar graph of treewidth $k$ has a free set of size $\Omega(k^{2})$.

3 implies that all $n$-vertex planar graphs of treewidth $\Omega(\sqrt{n})$
have free set of linear size (a vast generalization of the above observation
that square grids have linear size free sets).

Rather than consider planar graphs of small treewidth, one can also consider
planar graphs of small (maximum) degree. Da Lozzo et al. [24] prove the
following result in this vein:

######  Theorem 4 ([24]).

Every $n$-vertex planar triconnected cubic graph has a free set of size at
least $\lceil\frac{n}{4}\rceil$

Da Lozzo et al. [24] suggest the possibility of extending 4 to show the
existence of a linear-sized free set in any planar graph of maximum degree
$3$. As discussed in the introduction to this section, no such result is
possible for all planar graphs of maximum degree $7$. For
$\Delta\in\\{3,4,5,6\\}$ it is still open whether a linear bound is possible
for all planar graphs of maximum degree $\Delta$.

###  3.2 Free Sets in Planar Graphs

######  Theorem 5.

Every $n$-vertex planar graph $G$ has a free set of size at least
$\sqrt{n/2}$.

A version of 5 with an $\Omega(\sqrt{n})$ bound is attributed to Bose et al.
[17] though the authors at the time were working on the untangling problem
discussed in the introduction, so their result is never stated in terms of
free sets. They prove that
$\operatorname{fix}_{\mathcal{G}}(n)=\Omega(n^{1/4})$ by proving that a
triangulation $G$ either contains an induced outerplane graph of size
$\Omega(\sqrt{n})$ or a free-collinear set of size $\Omega(\sqrt{n})$. At the
time, the equivalence between proper-good sets, collinear sets, and free-
collinear sets was not known, so their proof includes both combinatorial and
geometric elements (including a proof that free-collinear and free sets are
equivalent). In the following, we extract these combinatorial elements from
[17] and use Lemma 4 (proven in [38]) to give a self-contained proof of 5 with
the best currently known bound of $\sqrt{n/2}$.

The _interior_ , $\operatorname{int}(G)$, of a near-triangulation $G$ is the
interior of the cycle that bounds the outer face of $G$.

######  Lemma 5.

Let $G$ be a near-triangulation, and let $v$ and $w$ be two points (possibly
vertices) on the boundary of the outer face of $G$ such that $vw$ is not an
edge of the outer face of $G$. Then there exists a simple open curve
$C:(0,1)\to\operatorname{int}(G)$ with endpoints $v$ and $w$ that is proper
with respect to $G$.

###### Proof.

(Da Lozzo et al. [24] give a 2-line proof of Lemma 5 using Tutte’s convex
embedding theorem.) If $vw$ if a (internal) edge of $E(G)$ then the curve $C$
consists of the edge $vw$. Then $C$ contains the edge $vw$, intersects each
other edge incident to $v$ or $w$ in one point, and does not intersect any
other edge of $G$, so $C$ is proper with respect to $G$.

|  |
---|---|---
Figure 7: The near-triangulation $G$, the curve $D$ from $f_{v}$ to $f_{w}$,
and the proper-good curve $C$ from $v$ to $w$.

Since $vw$ is not an internal edge of $G$ and since $G$ is a near-
triangulation, there is no internal face of $G$ that contains both $v$ and $w$
on its boundary. Refer to Fig. 7. Let $f_{v}$ be some internal face that
contains $v$ and $f_{w}$ some internal face that contains $w$. Let $G^{+}$ be
the weak dual of $G$. Let $D:[0,1]\to\operatorname{int}(G)$ be a simple open
curve with one endpoint in $f_{v}$ and one in $f_{w}$ such that $D$ does not
contain any vertices of $G$, as illustrated in Fig. 7(b). The sequence of
faces of $G$ intersected by $D$ defines a walk $W$ in $G^{+}$ with endpoints
$f_{v}$ and $f_{w}$. The walk $W$ contains a path $P$ in $G^{+}$ from $f_{v}$
to $f_{w}$. When traversing the path $P$ from $f_{v}$ to $f_{w}$, let
$f_{v}^{\prime}$ be the last face on $P$ that contains $v$ on its boundary;
and, let $f_{w}^{\prime}$ be the first face on $P$ that contains $w$ on its
boundary. Let the resulting sub-path between $f_{v}^{\prime}$ and
$f_{w}^{\prime}$ be denoted by $P^{\prime}$.

Let $e^{+}_{1},\ldots,e^{+}_{t}$ be the sequence of edges in $P^{\prime}$. For
each $i\in\\{1,\ldots,t\\}$, the edge $e_{i}^{+}$ in $G^{+}$ corresponds to
some inner edge $e_{i}$ of $G$. For each $i\in\\{1,\ldots,t\\}$, let $p_{i}$
be any point in the interior of $e_{i}$, let $p_{0}:=v$, and let $p_{t+1}=w$.
Then, for each $i\in\\{1,\ldots,t+1\\}$ there is an inner face $f_{i}$ of $G$
with the points $p_{i-1}$ and $p_{i}$ on the boundary of $f_{i}$. Construct an
open simple curve $C$ that visits $p_{0},\ldots,p_{t+1}$ in order in such a
way that the portion of $C$ between $p_{i-1}$ and $p_{i}$ is contained in the
interior of $f_{i}$, for each $i\in\\{1,\ldots,t+1\\}$. By the choice of
$f_{v}^{\prime}$, no edge incident to $v$ intersects $C$ other than in $v$.
Similarly, by the choice of $f_{w}^{\prime}$, no edge incident to $w$
intersects $C$ other than in $v$. Thus, the curve $C$ satisfies the
requirements of the lemma. ∎

###### Proof of 5.

If $G_{0}$ is a triangulation such that $G$ is a spanning subgraph of $G_{0}$,
then clearly, any free set in $G_{0}$ is also a free set in $G$. Thus we may
assume, without loss of generality, that $G$ is a triangulation.

The steps in this proof are illustrated in Fig. 8. Fix a crossing-free drawing
of $G$ and let $v_{1}$, $v_{2}$, and $v_{n}$ be the three vertices on the
outer face of $G$.

|
---|---
(a) | (b)
|
(c) | (d)
|
(e) | (f)
Figure 8: (a) and (b) A canonical ordering $v_{1},\ldots,v_{n}$ of a
triangulation $G$ and the resulting frame $F$.
(c) and (d): a chain of $(V(G),\prec)$ and the resulting proper-good curve $C$
(e) and (f): An antichain of $(V(G),\prec)$ and the resulting proper-good
curve $C$.

We use a _canonical ordering_ $v_{1},\ldots,v_{n}$ of $V(G)$, which has the
following property: For each $i\in\\{3,\ldots,n\\}$, the induced graph
$G_{i}:=G[\\{v_{1},\ldots,v_{i}\\}]$ is a near-triangulation that contains the
vertex $v_{i}$ and the edge $v_{1}v_{2}$ on its outer face. The existence of
this ordering is proven by, for example, de Fraysseix et al. [34]. In this
ordering, the introduction of $v_{i}$ introduces $d_{i}\geq 2$ new edges
$v_{i}w_{i,1},\ldots,v_{i}w_{i,d_{i}}$ to $G_{i}$ that do not appear in
$G_{i-1}$. The edges $e_{i}:=v_{i}w_{i,1}$ and
$e^{\prime}_{i}:=v_{i}w_{i,d_{i}}$ appear on the outer face of $G_{i}$ and the
vertices $w_{i,2},\ldots,w_{i,d_{i}-1}$ on the outer face of $G_{i-1}$ no
longer appear on the outer face of $G_{i}$, as illustrated in Fig. 8(a). This
defines a sequence of _frames_ $F_{1},\ldots,F_{n}$, where
$V(F_{i}):=\\{v_{1},\ldots,v_{i}\\}$ and
$E(F_{i}):=\bigcup_{j=1}^{i}\\{e_{i},e^{\prime}_{i}\\}$. We treat each frame
$F_{i}$ as a directed acyclic graph with a single source $v_{1}$ and a single
sink $v_{2}$ where the direction of edges $e_{i}$ and $e_{i}^{\prime}$ are the
same in each frame $F_{i},\ldots,F_{n}$ that includes these two edges.777For
readers familiar with Schnyder Woods [52], the final frame $F_{n}$ can be
obtained by taking the union of two trees $T_{1}$ and $T_{2}$ (rooted at
$v_{1}$ and $v_{2}$, respectively) in a Schnyder Woods, directing each edge of
$T_{1}$ away from its root and directing each edge of $T_{2}$ towards its
root, as illustrated in Fig. 8(b). Since the final frame $F:=F_{n}$ is a
directed acyclic graph, its transitive closure defines a partially ordered set
$(V(G),\prec)$ in which $v\prec w$ if and only if $F$ contains a directed path
from $v$ to $w$.

First, consider some maximal chain $x_{1}\prec\cdots\prec x_{k}$ in this
partial order. Since $F$ is maximal, $x_{i}x_{i+1}$ is an edge of $F$ for each
$i\in\\{1,\ldots,k-1\\}$. Since $F$ has a single source $v_{1}$ and a single
sink $v_{2}$, $x_{1}=v_{1}$ and $x_{k}=v_{2}$. Thus,
$C_{x}:=x_{1},\ldots,x_{k}$ is a cycle in $G$, as illustrated in Fig. 8(c).

Suppose that $G$ contains some edge $x_{i}x_{j}$ that is a chord of $C_{x}$.
We now argue that the edge $x_{i}x_{j}$ is embedded in the interior of the
cycle $C_{x}$. Without loss of generality, suppose $x_{i}$ appears after
$x_{j}$ in the canonical order, so $x_{i}=v_{a}$ and $x_{j}=v_{b}$ for some
$a>b$. Then the edge $x_{i}x_{j}=v_{a}v_{b}$ is in the graph
$G_{a}=G[\\{v_{1},\ldots,v_{a}\\}]$, so
$v_{b}\in\\{w_{a,1},\ldots,w_{a,d_{a}}\\}$. The two neighbours $x_{i-1}$ and
$x_{i+1}$ of $x_{i}$ in $C_{x}$ are not in the set
$w_{a,2},\ldots,w_{a,d_{a}-1}$, so the interior of the cycle $C_{x}$ contains
the interior of the cycle $v_{a},w_{a,1},\ldots,w_{a,d_{a}}$. Therefore the
edge $v_{a}v_{b}=x_{i}x_{j}$ is in the interior of $C_{x}$. (Indeed, the only
possibility is that $v_{b}\in\\{w_{a,1},w_{a,d_{a}}\\}$ )

Therefore, $G_{x}:=G[\\{x_{1},\ldots,x_{k}\\}]$ is an induced outerplane
subgraph of $G$ whose outer face is bounded by the cycle $C_{x}$. By Lemma 4,
there is simple closed curve $C$ (which closely follows $C_{x}$) that contains
a set $S$ of at least $k/2$ vertices of $G_{x}$, that is contained in the
closure of the outer face of $G_{x}$, that contains $G_{x}$ in the closure of
its interior, and that is proper and good with respect to $G_{x}$. Since each
edge of $G$ with two endpoints in $G_{x}$ is contained in the closure of the
interior of $C_{x}$, $C$ (if drawn sufficiently close to $C_{x}$) intersects
each edge in $E(G)\setminus E(G_{x})$ in at most one point, as illustrated in
Fig. 8(d). Thus $C$ is a proper-good curve for $G$ that contains the vertices
in $S$. By 1, $S$ is a free set in $G$ of size at least $k/2$.

Next, consider some maximal antichain
$S:=y_{1},\ldots,y_{k}:=v_{i_{1}},\ldots,v_{i_{k}}$ of $(V(G),\prec)$ of
length $k>1$ ordered by canonical ordering so that $i_{1}<\cdots<i_{k}$, as
illustrated in Fig. 8(e). Since $k>1$, $S$ does not contain $v_{1}$ or
$v_{2}$. Since $S$ is maximal and does not contain $v_{1}$ or $v_{2}$,
$y_{k}=v_{n}$. Consider the sequence of cycles $C_{1},\ldots,C_{k}$ where
$C_{j}$ is the cycle that bounds the outer face of $G_{i_{j}}$. By definition
of canonical ordering, the interior of $C_{j}$ contains the interior of
$C_{j-1}$ for each $j\in\\{2,\ldots,k\\}$. The nesting of these cycles is
illustrated in Fig. 8(e), where each new colour shows the interior of $C_{j}$
that is not contained in the interior of $C_{j-1}$. Furthermore, the interior
of $C_{j}$ must contain the vertex $y_{j-1}$ since, otherwise both $y_{j-1}$
and $y_{j}$ are on the outer face of $G_{i_{j}}$, which would mean that
$y_{j-1}$ and $y_{j}$ are comparable. Consider now the union of two cycles
$C_{j-1}$ and $C_{j}$ (or rather the union of the two closed curves that
represent these two cycles in the crossing-free drawing of $G$). This union
has one (bounded) faces, $f$, that contains both $y_{j-1}$ and $y_{j}$ on its
boundary. The boundary of $f$ is a cycle $D_{j}$ in $G$ comprised of two
paths: a path in $C_{j-1}$ containing $y_{j-1}$ and a path in $C_{j}$
containing $y_{j}$. Note that the union of all the cycles $D_{1},\dots D_{k}$,
(or rather the union of the $k$ closed curves that represent these $k$ cycles
in the crossing-free drawing of $G$) defines $k+1$ faces in the plane, the
weak dual of which is a path. These faces are illustrated in Fig. 8(f), where
the interior of each face is assigned its own colour.

We now construct a proper-good curve $C$ for $G$ that contains the vertices of
$S$. Let $y_{0}$ be a point in the interior of the edge $v_{1}v_{2}$. Let
$G_{1}^{\prime}:=G_{i_{1}}$ and, for each $j\in\\{2,\ldots,k\\}$, let
$G_{j}^{\prime}$ be the near-triangulation whose outer face is bounded by the
cycle $D_{j}$ described in the previous paragraph, and whose inner faces are
faces of $G$. Graphs $G_{j}^{\prime}$ are illustrated in Fig. 8(f) by having
their interiors shaded. Observe that $G^{\prime}_{1},\ldots,G^{\prime}_{k}$
have pairwise disjoint interiors. By Lemma 5, there is a simple open curve
$I_{j}$:$(0,1)\to\operatorname{int}(G^{\prime}_{j})$ with endpoints $y_{j-1}$
and $y_{j}$ that is proper with respect to $G^{\prime}_{j}$, for each
$j\in\\{1,\ldots,k\\}$. Since $G^{\prime}_{1},\ldots,G^{\prime}_{k}$ have
pairwise disjoint interiors, and since the union of the closures of
$\operatorname{int}(G^{\prime}_{1})\ldots,\operatorname{int}(G^{\prime}_{k})$
has a path for its week dual, the open curve obtained by taking the union of
the closures of $I_{1},\ldots,I_{k}$ is simple and it is proper with respect
to $G$. Finally, let $I_{k+1}$ be a simple open curve with endpoints $y_{0}$
and $y_{k}=v_{n}$ whose interior is contained in the outer face of $G$, as
illustrated in Fig. 8(f). Then the simple closed curve $C$ obtained from the
union of the closure of open curves $I_{1},\ldots,I_{k+1}$ is a proper-good
curve for $G$ that contains $S$. By 1, $S$ is a free set of size $k$.

To complete the proof we use Dilworth’s Theorem, which guarantees that the
poset $(V(G),\prec)$ contains a chain of size at least $\sqrt{2n}$ or an
antichain of size at least $\sqrt{n/2}$. In either case we obtain a free set
of size at least $\sqrt{n/2}$. ∎

The following generalization of 5, observed by Dujmović [27], has an almost
identical proof, except that one considers the induced poset $(X,\prec)$
rather than $(V(G),\prec)$:

######  Theorem 6.

For every planar graph $G$ and every $X\subseteq V(G)$, $X$ contains a free
set of size at least $\Omega(\sqrt{|X|})$.

###  3.3 Free Sets in Max-Degree-$\Delta$ Planar Graphs

Da Lozzo et al. [24] suggest the possibility that, since upper bounds on the
circumference of dual graphs can be used to obtain upper bounds on the size of
free sets, maybe lower bounds on circumference can be used to prove the
existence of large collinear sets. Dujmović and Morin [28] show that, for
planar graphs of bounded degree, this is indeed the case. In short, they show
that a triangulation $G$ of maximum-degree $\Delta$ and whose dual has
circumference $c(G^{*})$ has a free set of size $\Omega(c(G^{*})/\Delta^{4})$.
A series of results has steadily improved the lower bounds on the
circumference of $n$-vertex (not necessarily planar) cubic triconnected graphs
[10, 14, 41, 12, 44]. The current record is held by Liu et al. [44] who show
that, for any $n$-vertex cubic triconnected graph $G^{*}$,
$c(G^{*})\in\Omega(n^{0.8})$.

In the remainder of this subsection we describe some of the techniques used in
[28] to establish the $\Omega(c(G^{*})/\Delta^{4})$ result. Cycles in $G^{*}$
are relevant to free sets because every cycle in $G^{*}$ corresponds to a
proper-good curve in $G$. The resulting curve $C$ does not contain any
vertices of $G$, but it is natural to try reroute $C$ to obtain a new curve
$G$ that goes through some vertices of $G$. Fig. 9 (a) depicts a situation
where this rerouting fails because the resulting curve is no longer proper
because it intersects the red edge in Fig. 9(b) in two points. This leads to
the following definition that lays out conditions under which such rerouting
of curve $C$ is safe. We say that a vertex $v$ of $G$ is _caressed_ by $C$ if
the edges of $G$ that are incident to $v$ and intersected by $C$ appear
consecutively around $v$, as depicted in Fig. 9(c) (the thick grey edges
crossed by $C$ are consecutive around $v$ unlike in Fig. 9(a) where the set of
thick grey edges crossed by $c$ is not consecutive around $v$). If $C$
caresses $v$ and intersects the edges $vv_{1},\ldots,vv_{r}$ (see Fig. 9(c))
then there is a sequence of faces $f_{0},\ldots,f_{r}$ where $vv_{i}$ is the
edge shared between $f_{i-1}$ and $f_{i}$. Then the portion of $C$ that
intersects $f_{0},\ldots,f_{r}$ can be replaced with a curve $C^{\prime}$ that
enters $f_{0}$, proceeds directly to $v$, and immediate exits $f_{r}$ (see
Fig. 9(d)). Because the original curve $C$ does not intersect any other edges
incident to $v$, the modified curve $C^{\prime}$ is also a proper-good curve.
This operation can be repeated on any set of caressed vertices that form an
independent set:

|
---|---
(a) | (b)
|
(c) | (d)
Figure 9: Attempting to reroute a dual cycle (a proper-good curve $C$) into a
new proper-good curve $C^{\prime}$ so that it contains $v$.

######  Lemma 6.

Let $C$ be a proper-good curve in a triangulation $G$ and let $S$ be an
independent set of at least two vertices in $G$ that are each caressed by $C$.
Then $S$ is a free set in $G$.

###### Proof.

For each $v\in S$, reroute $C$ as described above so that $C$ contains $v$.
Since $v$ is caressed by $C$, the rerouting that takes place at $v\in S$
causes $C$ to intersect each edge incident to $v$ in exactly one point, namely
$v$, but does not change the intersection of $C$ with any edges not incident
to $v$. Since the vertices in $S$ form an independent set, all of these
rerouting operations do not cause $C$ to intersect any edge of $G$ in more
than one point. Thus $C$ is a proper-good curve that contains $S$ so, by 1 $S$
is a free set in $G$. (The condition that $S$ have at least two vertices
avoids the case in which $C$ crosses all the edges incident to a single vertex
$v$.) ∎

The requirement that a curve $C$ caresses a vertex $v$ of $G$ is equivalent to
requiring that the intersection of $C$ with the face $f_{v}$ of $G^{*}$ that
contains $v$ is a path. When this happens, we say that $C$ _caresses_ $f_{v}$.
Thus, finding a large collinear set in $G$ is equivalent to finding a cycle in
$G^{*}$ that caresses many faces of $G^{*}$.

######  Lemma 7.

Let $G$ be a triangulation and let $G^{*}$ be the dual of $G$. If some cycle
$C$ in $G^{*}$ caresses $k$ faces of $G^{*}$ then $G$ contains a free set of
size at least $k/4$.

###### Proof.

By the Four Colour Theorem [49], the faces of $G^{*}$ can be coloured with
four colours so that no two faces that share an edge are assigned the same
colour. One of the resulting colour classes contains at least $k/4$ faces of
$G^{*}$ that are caressed by $C$. These faces correspond to an independent set
$S$ of vertices of $G$ that are caressed by $C$. The lemma now follows from
Lemma 6. ∎

Unfortunately, there exists cubic triconnected planar graphs $G^{*}$ with no
large faces that have a Hamiltonian cycle that caresses only four faces of
$G^{*}$. One such graph is shown in Fig. 10. The main technical result of
Dujmović and Morin [28] is to show that such cycles can be modified to produce
cycles that caress many faces:

Figure 10: A Hamiltonian cycle in a cubic triconnected planar graph that
caresses only four faces.

######  Lemma 8 ([28]).

If $G^{*}$ is an $n$-vertex cubic triconnected planar graph with no faces of
size greater than $\Delta$, then there exists a cycle $C$ in $G^{*}$ that
caresses at least $\Omega(c(G^{*})/\Delta^{4})$ faces of $G^{*}$.

###### Proof Sketch.

Refer to Fig. 11. The proof of Lemma 8 is far too long to include here in any
detail, so we give a high level sketch. For the sake of simplicity, let
$\Delta$ be a fixed constant. Let $C$ be a cycle in $G^{*}$. Say that $C$
_touches_ a face of $G^{*}$ if $C$ and $f$ share at least one edge. Since each
face of $G^{*}$ has at most $\Delta$ edges and each edge of $C$ touches two
faces of $G^{*}$ (one inside $C$ and one outside of $C$), the number of faces
of $G^{*}$ that are touched by $C$ is at least $2|C|/\Delta$. At least
$|C|/\Delta$ of these faces are in the interior of $C$ and at least
$|C|/\Delta$ of these are in the exterior of $C$.

The authors define a subgraph $H$ of $G^{*}$ that includes all the edges of
$C$ and such that any cycle in the dual graph $H^{*}$ of $H$ contains faces
inside and outside of $C$. Removing the edges from $H^{*}$ that correspond to
edges of $C$ produces two trees $T_{0}$ and $T_{1}$, where $T_{0}$ contains
faces of $H$ in the interior of $C$ and $T_{1}$ contains faces of $H$ in the
exterior of $C$. For each $b\in\\{0,1\\}$, the tree $T_{b}$ has two important
properties:

  1. 1.

Each leaf of $T_{b}$ corresponds to a face $f$ of $H$ that contains at least
one face of $G^{*}$ that is caressed by $C$.

  2. 2.

Let $f\in V(T_{b})$ be a face of $H$ that has degree $\delta$ in $T_{b}$ and
that contains $\tau$ faces of $G^{*}$ touched by $C$, $\kappa$ of which are
caressed by $C$. Then $3\kappa+2\delta\geq\tau$.

The second of these properties says that any node of $T_{b}$ that contains
many faces touched by $C$ either caresses many of these faces or has high
degree in $T_{b}$. The number of leaves in $T_{b}$ is
$2+\sum_{x}(\deg_{T_{b}}(x)-2)$, where the sum is over all non-leaf nodes $x$
of $T_{b}$. Combining this with the first of these properties implies that $C$
caresses $\Omega(|C|)$ faces of $G^{*}$ or that $T_{b}$ has $\Omega(|C|)$
nodes but at most $\epsilon|C|$ leaves, for some small $\epsilon>0$. In the
former case we are done. In the latter case, we conclude that the vast
majority of nodes in $T_{b}$ have degree two.

|
---|---
Figure 11: Performing surgery on the trees $T_{0}$ (pink) and $T_{1}$ (green)
in order to increase the number of leaves.

Since $T_{0}$ and $T_{1}$ share the boundary $C$, this can be used to show
that $T_{0}$ contains a path $P_{0}$ of degree-$2$ nodes and $T_{1}$ contains
a path $P_{1}$ of degree-$2$ nodes, each of size bounded by a constant
(depending on $\Delta$) such that moving the nodes in $P_{0}$ from $T_{0}$ to
$T_{1}$ and moving the nodes in $P_{1}$ from $T_{1}$ to $T_{0}$ results in two
new subgraphs $T_{0}^{\prime\prime}$ and $T_{1}^{\prime\prime}$ of $H^{*}$
that contain at least one more leaf than $T_{0}$ and $T_{1}$. The graphs
$T_{0}^{\prime\prime}$ and $T_{1}^{\prime\prime}$ are not necessarily trees,
but the boundary they share defines a new cycle $C^{\prime}$ from which we can
define two trees $T_{0}^{\prime}$ and $T_{1}^{\prime}$ as before. These two
new trees differ from $T_{0}$ and $T_{1}$ only in a small neighbourhood of the
paths $P_{0}$ and $P_{1}$, which ensures that $T_{0}^{\prime}$ and
$T_{1}^{\prime}$ also have at least one more leaf than $T_{0}$ and $T_{1}$. At
this point, the procedure is repeated on $C^{\prime}$. Each application of
this procedure may decrease the length of the cycle of $C$ by at most a
constant (for a fixed $\Delta$), so this procedure can be repeated
$\Omega(|C|)$ times, which produces a cycle $\tilde{C}$ that defines two trees
$\tilde{T}_{0}$ and $\tilde{T}_{1}$ having a total of $\Omega(|C|)$ leaves,
each of which contains a face of $G^{*}$ caressed by $C$. ∎

If $G^{*}$ is the dual of a triangulation $G$ then the size of each face of
$G^{*}$ is the degree of the corresponding vertex in $G$. This gives the
following consequence of Lemma 8.

######  Corollary 2.

Let $G$ be an $n$-vertex triangulation of maximum-degree $\Delta$ and let
$G^{*}$ be the dual of $G$. Then $G$ has a free set of size
$\Omega(c(G^{*})/\Delta^{4})$

A result of Kant and Bodlaender [43] shows that one can add edges to any
planar graph $G_{0}$ of maximum degree $\Delta$ to obtain a triangulation $G$
of maximum degree at most $\lceil 3\Delta/2\rceil+11$. Combined with 4, this
establishes

######  Corollary 3.

Let $G$ be an $n$-vertex planar graph of maximum-degree $\Delta$ and let
$G^{*}$ be the dual of $G$. Then $G$ has a free set of size
$\Omega(c(G^{*})/\Delta^{4})$.

2 shows that, for the class of planar graphs of maximum-degree $\Delta=O(1)$,
the dual circumference and the size of the largest free set differ by only a
constant factor. Combined with the best known lower bounds on the
circumference of cubic triconnected graphs [44], 2 gives:

######  Corollary 4.

Let $G$ be an $n$-vertex triangulation of maximum-degree $\Delta$. Then $G$
has a free set of size $\Omega(n^{0.8}/\Delta^{4})$.

##  4 Applications

In this section we discuss applications of free sets. For each of these ($s$)
applications, and each of the ($t$) classes of planar graphs known to have
large free sets, the use of free sets gives a result. Rather than provide an
exhaustive list of $s\times t$ corollaries, we state the relationship between
free sets and the application and give the most general corollary; the one
about planar graphs obtained from 5.

###  4.1 Untangling

As discussed in the introduction, the original application of free sets was
untangling. By Lemma 1, each lower bound (on the size of the largest free set
in a graph family) obtained in Sections 3.1, 3.2 and 3.3, readily turns into
the square root of the same bound for the untangling problem on that family.
For example, 5 and 1 yield:

######  Corollary 5.

Let $\mathcal{G}$ be the class of all planar graphs. For every $n$-vertex
graph $G\in{\mathcal{G}}$, $\operatorname{fix}(G)\in\Omega(n^{1/4})$. In other
words, $\operatorname{fix}_{\mathcal{G}}(n)\geq(n/2)^{1/4}$.

We do not know if this bound is asymptotically optimal. Cano et al. [20]
proved that for the class of planar graphs $\mathcal{G}$,
$\operatorname{fix}_{\mathcal{G}}(n)\in O(n^{0.4965})$.

On the contrary, applying the known bounds on the largest free sets coupled
with Lemma 1 gives tight bounds for some graph families. Specifically, the
linear bounds on free sets in Section 3.1 and Lemma 1 imply $\Omega(n^{1/2})$
untangling bound for these families. Bose et al. [17] showed that there is a
class of trees, in fact forest of stars, ${\mathcal{T}}$, such that
$\operatorname{fix}_{\mathcal{T}}\in O(n^{1/2})$. Thus the $\Omega(n^{1/2})$
untangling bound is tight for all families in Section 3.1, except for the
class of cubic triconnected planar graphs. The stars in ${\mathcal{T}}$ have
unbounded degree. Thus a tight bound on untangling cubic triconnected planar
graph is unknown.

###  4.2 Universal point subsets

A set of points $P$ is _universal_ for a set of planar graphs if every graph
from the set has a straight-line crossing-free drawing where all of its
vertices map to distinct points in $P$. Arguably, the most famous open problem
in graph drawing, attributed to Bojan Mohar (1988), asks if there exist a
constant $c$ such that, for every $n$ there exists a pointset of size $c\cdot
n$ that is universal for the class of all $n$-vertex planar graphs. It is
known that for all, large enough $n$, no universal pointset of size $n$ exists
for the class of $n$-vertex planar graphs – as first proved by de Fraysseix et
al. [34]. The same authors also proved that the $O(n)\times O(n)$ integer grid
is universal for all $n$-vertex planar graphs and thus universal pointsets of
size $O(n^{2})$ exists. Currently the best known lower bound on the size of a
smallest universal pointset for $n$-vertex planar graphs is $1.239n-o(n)$ [50]
and the best known upper bound is $n^{2}/4-O(n)$ [6]. Closing the gap between
$\Omega(n)$ and $O(n^{2})$ is a major, and likely very difficult, graph
drawing problem, open since 1988 [33, 34].

Various related notions have been introduced and studied in the literature
with the aim of better understanding the universal pointset problem. A set $P$
of $k$ points in the plane is a _universal point subset_ for a family of
planar graphs, if for every graph $G$ in the family, there exists a straight-
line crossing-free drawing in which $k$ vertices of $G$ are placed at the $k$
points in $P$. Universal point subsets were introduced by Angelini et al. [2].
They proved that (a very flat convex chain of) $\lceil\sqrt{n}\rceil$ points
is a universal point subset for the class of all $n$-vertex planar graphs.
Giacomo et al. [37] then proved that every set of $\Omega(\log n)$ points, as
well as, every set of $\lceil n^{1/3}\rceil$ points in convex position is a
universal point subset for the class of $n$-vertex planar graphs.

The following lemma and its consequences, first observed by Dujmović [27], is
immediate from the definition of free sets.

######  Lemma 9.

Let $k$ be a positive integer and $\mathcal{F}$ a family of planar graphs such
that every graph in the family has a free set of size at least $k$. Then every
set of $k$ points in the plane is a universal point subset for $\mathcal{F}$.

Note that this lemma does not just prove that there exists a set of $k$ points
that is a universal point subset for $\mathcal{G}$, it proves that _every_ set
of $k$ points is a universal point subset for $\mathcal{G}$. This distinction
turns out to be useful in other applications. Combining Lemmata 9 and 5 gives:

######  Corollary 6.

Every set of $\lceil\sqrt{n/2}\rceil$ points is a universal point subset for
the class of $n$-vertex planar graphs.

It has been known for a long time that every set of $n$ points in general
position is a universal point (sub)set for the family of $n$-vertex
outerplanar graphs [39, 15, 22]. Lemma 9 implies that all the families studied
in Section 3.1, also admit universal point subsets of linear size. This
includes, for example, planar graphs of treewidth at most $3$ by 2, a strict
superclass of the class of outerplanar graphs.

###  4.3 Simultaneous Geometric Embeddings

Simultaneous geometric embeddings were introduced by Braß et al. [19]. Since
then there has been a plethora of work on the subject on many variants of the
problem– see, for example a survey by Bläsius et al. [13]. Common variants of
the problem include those in which the mapping between the vertices of the two
graphs is given and those in which the mapping is not given.

####  4.3.1 Without Mapping

A sequence of graphs $G_{1},G_{2},\dots,G_{r}$ where
$|V(G_{1})|\geq|V(G_{2})|\geq\dots|V(G_{r})|$ are said to have a _simultaneous
geometric embedding without mapping (SGE-nomap)_ if there exists a pointset
$P$ of size $|V(G_{1})|$ such that each of $G_{1},\ldots,G_{r}$ has a
straight-line crossing-free drawing where all of its vertices are mapped to
distinct points in $P$. The following well known and still wildly open problem
was asked by Braß et al. [19] in 2003, and is also listed among selected list
of graph drawing problems in [18] (see also Problem 12): Does every pair of
$n$-vertex planar graphs has SGE-nomap (for every positive integer $n$)? The
statement is known _not_ to be true when “pair” (that is, $r=2$) is replaced
by a bigger constant [21, 51], currently being $r=30$ [54]. More generally,
Steiner [54] showed that for every large enough $n$ there exists a sequence of
at most $(3+o(1))\log_{2}(n)$ $n$-vertex planar graphs that do not have a SGE-
nomap.

While the problem of Braß et al. [19] still seems to be out of reach, in a
different direction Angelini et al. [3] write: “What is the largest $k\leq n$
such that every $n$-vertex planar graph and every $k$-vertex planar graph
admit a geometric simultaneous embedding with no mapping? Surprisingly, we are
not aware of any super-constant lower bound for the value of $k$?” The
corollary below, noticed first by Dujmović [27], answered their question with
the help of free sets, as detailed in the next lemma.

######  Lemma 10.

Let $G_{1}$ be a planar graph with free set of size at least $k$. Let $G_{2}$
be a planar graph on at most $k$ vertices. Then $G_{1}$ and $G_{2}$ admit SGE-
nomap.

###### Proof.

By Fáry’s theorem, $G_{2}$ has a straight-line crossing-free drawing on some
set, $P_{2}$, of $|V(G_{2})|\leq k$ points. Since $G_{1}$ has a free set $S$
of size at least $k$, $G_{1}$ has a straight-line crossing-free drawing where
$|P_{2}|$ vertices of $G_{1}$ are mapped to distinct points in $P_{2}$.
Consider now the set of points, $P$, defined by the vertices in the drawing of
$G_{1}$. This set is our desired pointset as it is a set of $|V(G_{1})|$
points such that each of $G_{1}$ and $G_{2}$ has a straight-line crossing-free
drawing where all of its vertices are mapped to distinct points of $P$. ∎

Lemmata 10 and 5 immediately imply the following, aforementioned result.

######  Corollary 7.

For every $n$ and every $k\leq\sqrt{n/2}$, every $n$-vertex planar graph and
every $k$-vertex planar graph admit a SGE-nomap.

One can combine the many lower bounds (on the size of the largest free set in
a graph family) obtained in Sections 3.1, 3.2 and 3.3 to obtain results of
similar flavour to Corollary 7. One example is the following, for every $n$
and every $k\leq n/4$, every $n$-vertex planar graph and every $k$-vertex
triconnected cubic planar graph admit a SGE-nomap.

Note that universal point subsets of size $k$ do not imply results on SGE-
nomap, akin to 7. In particular, imagine that, as in the proof of Lemma 10,
one starts with a straight-line crossing-free drawing of the smaller graph
$G_{2}$. Even if the larger graph $G_{1}$ is in a class of graphs that have
universal point subsets of size $k$, there is no guarantee that $G_{1}$ can be
drawn on the specific pointset of size $k$ used by the drawing of $G_{2}$. To
be able to use universal point subsets for SGE-nomap problems, one needs the
stronger variant of “all pointsets of size $k$” to be subset
universal—something that is guaranteed by free sets of size $k$.

####  4.3.2 With Mapping

Two $n$-vertex planar graphs $G_{1}$ and $G_{2}$ on _the same vertex set_ ,
$V:=V(G_{1})=V(G_{2})$, are said to have a _$k$ -partial simultaneous
geometric embedding with mapping_ (_$k$ -PSGE-withmap_) if there exists a set
$V^{\prime}:=\\{v_{1},\ldots,v_{k}\\}\subseteq V$, and a set
$P:=\\{p_{1},\ldots,p_{k}\\}$ of points such that each of $G_{1}$ and $G_{2}$
has a straight-line crossing-free drawing in which $v_{i}$ is mapped to
$p_{i}$, for each $i\in\\{1,\ldots,k\\}$. PSGE-withmap on the whole vertex set
(i.e. $n$-PSGE-withmap) has been widely studied leading to mostly negative
results (thus giving another motivation to introduce this partial version).
For example, it is known that, for every large enough $n$, there are pairs of
$n$-vertex planar graphs that do not have $n$-PSGE-withmap [19]. In fact the
same is true for graphs from very simple families of planar graphs, for
example: for an $n$-vertex tree and an $n$-vertex path [5], for an $n$-vertex
planar graph and an $n$-vertex matching [5] and for three $n$-vertex paths
[19].

The $k$-PSGE-withmap problem was introduced888In [31], they use the
abbreviation $k$-PSGE for what we call $k$-PSGE-withmap. Also, the definition
of $k$-PSGE-withmap, as introduced in Evans et al. [31], has one additional
requirement, which states that if $v,w\in V$ are mapped to the same point in
$D_{i}$ and $D_{j}$, then $v=w$. However this additional requirement can
always be met by the fact that it is possible to perturb any subset of
vertices in a straight-line crossing-free drawing without introducing
crossings. (This fact is used for example in the proof that every free-
collinear set is free.) by Evans et al. [31] who proved that any two
$n$-vertex trees have an $11n/17$-PSGE-withmap. Their proof uses their column
planarity, which is the topic of the next section. Barba et al. [9] proved
that any two $n$-vertex outerplanar graphs have an $n/4$-PSGE-withmap. Evans
et al. [31] also observed that 5, the untangling result, implies that every
pair of $n$-vertex planar graphs has an $\Omega(n^{1/4})$-PSGE-withmap.
Namely, start with a straight-line crossing-free drawing of $G_{1}$. Since
$G_{1}$ and $G_{2}$ have the same vertex set, the drawing of $G_{1}$ (or
rather the positions of its vertices in the plane) defines a straight-line
drawing of $G_{2}$ (that almost certainly has crossings). Untangling $G_{2}$
while keeping $\Omega(n^{1/4})$ of its vertices fixed (which is possible by 5)
gives the result.

######  Theorem 7 ([31]).

Every pair of $n$-vertex planar graphs has an $\Omega(n^{1/4})$-PSGE-withmap.

However, the above untangling argument fails if we try to apply it one more
time. The following generalization of the $k$-PSGE problem (to more than two
graphs) illustrates this. Given any set $Q:=\\{G_{1},\ldots,G_{r}\\}$ of
planar graphs on _the same vertex set_ , $V$, we say that the graphs in $Q$
have a _$k$ -partial simultaneous geometric embedding with mapping_ ($k$-PSGE-
withmap) if there exists a set $V^{\prime}:=\\{v_{1},\ldots,v_{k}\\}\subseteq
V$, and a set $P:=\\{p_{1},\ldots,p_{k}\\}$ of points such that each graph in
$Q$ has a straight-line crossing-free drawing in which $v_{i}$ is mapped to
$p_{i}$, for each $i\in\\{1,\ldots,k\\}$.

If we try to mimic the earlier untangling argument that proves 7, it fails for
$r=3$ already since we need to be able to guarantee that when $G_{3}$ is
untangled the set of its vertices that stays fixed has a large intersection
with the set that remained fixed when untangling $G_{2}$. It is here that we
need the stronger version of 5, namely 6.

We start by presenting a lemma about PSGE-withmap for two graphs via free-
sets. Its proof uses the common trick of taking advantage of the fact that
points in the plane have two degrees of freedom, and thus one ordering can be
imposed on the ${x}$-coordinates and a different ordering on ${y}$-coordinates
(see for example [8]).

######  Lemma 11.

Let $G_{1}$ and $G_{2}$ be two planar graphs on the same vertex set
$V:=V(G_{1})=V(G_{2})$. Let $S\subseteq V$ be an (unordered) free set in
$G_{1}$ and an (unordered) free set in $G_{2}$, then $G_{1}$ and $G_{2}$ have
a $|S|$-PSGE-withmap.

###### Proof.

Let $S:=\\{v_{1},\ldots,v_{s}\\}$, let $S_{1}$ be a permutation of $S$ such
that $S_{1}$ is an ordered free set in $G_{1}$, and let $S_{2}$ be permutation
of $S$ such that $S_{2}$ is an ordered free set in $G_{2}$. Define the
pointset $P:=\\{p_{1},\ldots,p_{s}\\}$ in which $p_{i}$ has ${x}$-coordinate
equal to the position of $v_{i}$ in $S_{1}$ and ${y}$-coordinate equal to the
position of $v_{i}$ in $S_{2}$, for each $i\in\\{1,\ldots,s\\}$. By the
definition of free set, $G_{1}$ has straight-line crossing-free drawing
drawing with $v_{i}$ at $p_{i}$, for each $i\in\\{1,\ldots,s\\}$. By the
definition of free set—with the roles of ${x}$-coordinates and
${y}$-coordinates reversed—$G_{2}$ has a straight-line crossing-free drawing
with $v_{i}$ at $p_{i}$, for each $i\in\\{1,\ldots,s\\}$. Thus $G_{1}$ and
$G_{2}$ have a $|S|$-PSGE-withmap. ∎

6 and 11 gives another proof of 7. By 6 (applied to $G_{1}$ and $V$), there
exists $S_{1}\subseteq V$ of size at least $\sqrt{n/2}$ that is a free set in
$G_{1}$. By 6 (applied to $G_{2}$ and $S_{1}$), there exists $S\subseteq
S_{1}$ of size at least $\sqrt{|S_{1}|/2}\geq n^{1/4}/2^{3/4}$. Thus $S$ is a
free set in $G_{1}$ and in $G_{2}$. By Lemma 11, $G_{1}$ and $G_{2}$ have a
$\lceil n^{1/4}/2^{3/4}\rceil$-PSGE-withmap. In exactly the same way, Lemmata
3 and 11 give a proof that any two $n$-vertex graphs each of which is one of
the following: a tree, an outerplanar graph, Halin graph, or a square graph,
have a $(n/4)$-PSGE-withmap.

######  Lemma 12.

Let $Q:=\\{G_{1},\ldots,G_{r}\\}$ be a set of $r\geq 2$ planar graphs on the
same vertex set $V$. Let $S\subseteq V$ be an unordered free set in $G_{i}$,
for each $i\in\\{1,\ldots,r\\}$. Then the graphs in $Q$ have a
$|S|^{1/2^{(r-2)}}$-PSGE-withmap.

###### Proof.

For each $i\in\\{2,\ldots,r\\}$, let $S_{i}$ be a permutation of $S$ that is
an ordered free set in $G_{i}$. Suppose that, for some $i\in\\{3,\ldots,r\\}$,
$S_{i-1}^{\prime}$ is a subsequence of $S_{2}$ that defines an (ordered) free
set in each of $G_{2},\ldots,G_{i-1}$. Since $S_{i}$ and its reversal are both
free sets in $G_{i}$, Dilworth’s Theorem implies that there is a subsequence
$S_{i}^{\prime}$ of $S_{i-1}^{\prime}$ of size at least
$|S_{i-1}^{\prime}|^{1/2}$ that is a free set in $G_{i}$ and is therefore a
free set in each of $G_{1},\ldots,G_{i}$. By starting with
$S_{2}^{\prime}:=S_{2}$, it follows that there exists an ordered set
$S^{\prime}:=S_{r}^{\prime}$ of size $|S|^{1/2^{r-2}}$ that is a free set in
each of $G_{2},\ldots,G_{r}$.

Now apply Lemma 11 to the graphs $G_{1}$ and $G_{2}$ with the set $S$ to
obtain straight-line crossing-free drawing of both graphs in which each vertex
in $S$ (and therefore, the vertices in $S^{\prime}$) appear at the same
location in both drawings. In these drawings, the ${y}$-coordinates of the
vertices in $S^{\prime}$ are increasing. By the definition of free set
(exchanging the roles of ${x}$\- and ${y}$-coordinates), each of
$G_{3},\ldots,G_{k}$ has a straight-line crossing-free drawing in which each
vertex in $S^{\prime}$ has the same location in each drawing. ∎

Starting with $X:=V$ and using $r$ applications of 6 yields a set $S$ of size
at least $n^{1/2^{r}}/2$ that is a free set in each of $G_{1},\ldots,G_{r}$.
Applying Lemma 12 to $S$ and $G_{1},\ldots,G_{r}$ gives the following
corollary:

######  Corollary 8.

Let $Q:=\\{G_{1},\ldots,G_{r}\\}$ be a set of $r\geq 2$ planar graphs on the
same vertex set $V$. Then the graphs in $Q$ have a $(n^{1/4^{r-1}}/2)$-PSGE-
withmap.

If the graphs in $Q$ each come from one of the classes covered by 1, then
repeated applications of 1 gives a set $S$ of size at least $n/2^{r}$ that is
free in each of $G_{1},\ldots,G_{r}$, in which case the bound in 8 becomes
$n^{1/2^{r-2}}/4$.

###  4.4 Column planarity

Given a planar graph $G$, a set $R\subseteq V(G)$ is _column planar_ in $G$ if
the vertices of $R$ can be assigned distinct ${x}$-coordinates such that for
any arbitrary assignment of ${y}$-coordinates to the vertices in $R$ (under
the condition that the resulting $|R|$ points have no three on a line), there
exists a straight-line crossing-free drawing of $G$ in which each vertex $v\in
R$ is placed to its assigned coordinates. $R$ is _strongly column planar_ if
the “no three on a line condition” is removed from the definition. The
following lemma is immediate from the definition of free sets and strongly
column planar sets.

######  Lemma 13.

A (sub)set of vertices of a planar graph is strongly column planar set if and
only if it is an unordered free set.

Being strongly column planar implies being column planar, thus all the bounds
from Sections 3.1, 3.2 and 3.3 apply to column planarity. For example, 5
implies that every $n$-vertex planar graph has a column planar set of size
$\Omega(\sqrt{n})$. 3 implies that every $n$-vertex bounded-degree planar
graph has a column planar set of size $\Omega(n^{0.8})$; and so on.

Column planar sets were introduced by Evans et al. [31] motivated by
applications to partial simultaneous geometric embeddings. Notions similar to
column planarity were studied by Estrella-Balderrama et al. [30] and Di
Giacomo et al. [25]. Barba et al. [8] proved that $n$-vertex trees have column
planar sets of size $14n/17$. Note that that does not imply that trees have
free sets of that size, since being column planar does not imply being
strongly column planar. In particular, if $G$ is a 3-cycles, then $V(G)$ is
column planar set for any assignment of ${x}$-coordinates to $V(G)$. However,
no ${x}$-coordinate assignment can be turned into a straight-line crossing-
free drawing with all the vertices having the same ${y}$-coordinate. Thus
$V(G)$ is not strongly column planar.

##  5 A One-Bend Variant

A _$k$ -bend crossing-free drawing_ of a planar graph $G$ is a crossing-free
drawing of $G$ in which each edge is represented by a polygonal chain
consisting of at most $k$ line segments. Thus, a $0$-bend crossing-free
drawing is a straight-line crossing-free drawing. This leads naturally to a
definition of a $k$-bend free set introduced by Bose et al. [16]. An ordered
set $S:=(v_{1},\ldots,v_{s})$ of vertices in a planar graph $G$ is a _$k$
-bend free set_ if, for any $x_{1}<\cdots<x_{s}$ and any $y_{1},\ldots,y_{s}$,
there exists a $k$-bend crossing-free drawing $\Gamma$ of $G$ such that
$(x_{i},y_{i})$ is the location of $v_{i}$ in $\Gamma$, for each
$i\in\\{1,\ldots,s\\}$. As an application of 9, below, Bose et al. [16] prove
the following result:

######  Theorem 8 ([16]).

Every $n$-vertex planar graph has a $1$-bend free set of size at least
$11n/21$.

They prove 8 by proving the following result, which the main result in [16]:

######  Theorem 9 ([16]).

Every $n$-vertex triangulation has a spanning tree with at least $11n/21$
leaves.

9 improves a longstanding bound of $n/2$ that has at least two different
proofs [1, 4]. The proof of 9 is well outside the scope of this survey.
Instead, we prove the following lemma that, along with 9, immediately implies
8.

######  Lemma 14.

Let $G$ be a planar graph and let $T$ be a spanning tree of $G$. Then the
leaves of $T$ are a one-bend collinear set in $G$.

###### Proof.

Refer to Fig. 12. Fix some straight-line crossing-free drawing of $G$, which
also fixes a straight-line crossing-free drawing of $T$. Fatten the drawing of
$T$ by some arbitrarily small value $\epsilon>0$ by taking the Minkowsky sum
of $T$ with a disc of radius $\epsilon$. The boundary of this fattened tree is
a simple closed curve $C_{0}$. Construct a curve $C$ by deforming $C_{0}$ in
an $\epsilon$-neighbourhood of each leaf $v$ of $T$ so that it contains $v$.
If $\epsilon$ is sufficiently small, then $C$ is a simple closed curve that
intersects each edge $vw$ of $G$ in at most $2$ points: one point within
distance $\epsilon$ of $v$ and one point within distance $\epsilon$ of $w$.
Let $S:=(v_{1},\ldots,v_{s})$ be the leaves of $T$ in the order they are
encountered while traversing $C$. Subdivide each edge of $G$ by placing a
vertex in the center of the edge and call the resulting graph $G^{\prime}$.
Then $C$ is a proper-good curve for $G^{\prime}$ that contains $S$. Therefore
$S$ is a free set in $G^{\prime}$. Therefore, for any $x_{1}<\cdots<x_{s}$ and
any $y_{1},\ldots,y_{s}$, $G^{\prime}$ has a straight-line crossing-free
drawing in which $v_{i}$ is placed at $(x_{i},y_{i})$ for each
$i\in\\{1,\ldots,s\\}$. Any such drawing of $G^{\prime}$ gives a $1$-bend
crossing-free drawing of $G$ in which $v_{i}$ is placed at $(x_{i},y_{i})$ for
each $i\in\\{1,\ldots,s\\}$. Thus, $S$ is a $1$-bend collinear set in $G$. ∎

Figure 12: The leaves of a spanning tree of $G$ are a $1$-bend collinear set
of $G$.

The obvious question is whether the bound in 8 is of the correct form. Perhaps
planar graphs have $1$-bend collinear sets of size $n-o(n)$. We can rule this
possibility out with the following construction.

######  Theorem 10.

For infinitely many values of $n$, there exists an $n$-vertex planar graph
that has no $1$-bend collinear set of size greater than $10n/11$.

###### Proof.

The Goldner–Harary graph, $G_{0}$ is an $11$-vertex triangulation that is not
Hamiltonian. We claim that any $1$-bend free set in $G_{0}$ has size at most
$10$. Suppose, for the sake of contradiction, that $S:=V(G_{0})$ is a $1$-bend
free set in $G_{0}$. Then $G$ has a $1$-bend crossing-free drawing with all
vertices of $S$ placed on the ${x}$-axis. Since this is a $1$-bend crossing-
free drawing and all vertices of $G_{0}$ are on the ${x}$-axis, no edge
properly crosses the ${x}$-axis. Therefore, this is a $2$-page book embedding
of $G_{0}$. This is impossible because any triangulation with a $2$-page book
embedding is Hamiltonian.

For any positive integer $k$, let $G$ to be a graph consisting of $k$ disjoint
copies of $G_{0}$. Then $G$ has $n=11k$ vertices. Any $1$-bend free set in $G$
must exclude one vertex from each copy of $G_{0}$ and therefore has size at
most $10k=10n/11$. ∎

##  6 Open Problems

We conclude with a list of open problems:

  1. 1.

What is the largest value $\alpha$ such that every $n$-vertex planar graph has
a free set of size $\Omega(n^{\alpha})$? Currently, we know that
$1/2\leq\alpha\leq 0.9859$. Is $\alpha$ equal to the shortness exponent
$\sigma$ for cubic triconnected planar graphs? In other words, does every
triangulation $G$ contain a free set of size $\Omega(c(G^{*}))$?

  2. 2.

Does every $n$-vertex planar graph of maximum degree $3$, $4$, $5$, or $6$
contain a free set of size $\Omega(n)$

  3. 3.

Does every $n$-vertex planar graph of treewidth $4$ contain a free set of size
$\Omega(n)$?

  4. 4.

What is the largest value of $\beta$ such that every $n$-vertex planar graph
has a $1$-bend free set of size $\beta n-o(n)$?

  5. 5.

Say that a subset $S$ of vertices in a planar graph $G$ is _mostly free_ if,
for every set $P$ of $|S|$ points _in general position_ , there exists a
straight-line crossing-free drawing of $G$ in which each vertex in $S$ is
drawn at a distinct point in $P$. Is there a constant $\gamma>0$ such that
every mostly free set $S$ contains a free subset of size at least $\gamma|S|$?
The class of outerplanar graphs shows that $\gamma\leq 2/3$ since any set of
$n$ points in general position is universal for the class of $n$-vertex
outerplanar graphs [39, 15, 22] so the entire vertex set of every outerplanar
graph is mostly free, but there exists $n$-vertex outerplanar graphs with no
free set of size greater than $\lceil 2n\rceil$.

  6. 6.

6 and 1 allow us to choose any set $X$ of vertices in $G$ and find a large
subset of $X$ that is a free set of $G$, and this turns out to be useful in a
number of applications. 3 and 4, which currently give the strongest lower
bounds for planar graphs of bounded degree and triconnected cubic planar
graphs, do not have this flexibility.

    1. (a)

Is the following strengthening of 3 true: For any planar graph $G$ of bounded
degree and any subset $X$ of vertices of $G$, there exists a set $S\subseteq
X$ of size $\Omega(|X|^{0.8})$ that is a free set of $G$?

    2. (b)

Is the following strengthening of 4 true: For any triconnected cubic planar
graph $G$ and any subset $X$ of vertices of $G$, there exists a set
$S\subseteq X$ of size $\Omega(|X|)$ that is a free set of $G$?

In some of the applications discussed in Section 4, free sets are a convenient
tool but may be more powerful than necessary, and better bounds may be
possible using more direct methods. Here are two examples:

  1. 5.

Do universal point subset of size $\Omega(n^{1/2+\epsilon})$ for some
$\epsilon>0$ exist for the class of $n$-vertex planar graphs. Currently, there
is nothing that rules out a bound of $\Omega(n)$.

  2. 6.

Although free sets and an application of Dilworth’s Theorem currently give the
best bounds for untangling planar graphs and several other graph classes,
better bounds may be possible using more direct techniques. The
$\Omega(n^{2/3})$ bound on $\operatorname{fix}_{\mathcal{C}}(G)$ for
untangling cycles [23] gives one example in which free sets are not the best
approach.

## References

  * Albertson et al. [1990] Michael O. Albertson, David M. Berman, Joan P. Hutchinson, and Carsten Thomassen.  Graphs with homeomorphically irreducible spanning trees.  _J. Graph Theory_ , 14(2):247–258, 1990.  doi:10.1002/JGT.3190140212.
  * Angelini et al. [2012a] Patrizio Angelini, Carla Binucci, William S. Evans, Ferran Hurtado, Giuseppe Liotta, Tamara Mchedlidze, Henk Meijer, and Yoshio Okamoto.  Universal point subsets for planar graphs.  In _Algorithms and Computation - 23rd International Symposium, ISAAC 2012_ , volume 7676 of _LNCS_ , pages 423–432. Springer, 2012a.  doi:10.1007/978-3-642-35261-4_45.
  * Angelini et al. [2015] Patrizio Angelini, William S. Evans, Fabrizio Frati, and Joachim Gudmundsson.  SEFE without mapping via large induced outerplane graphs in plane graphs.  _Journal of Graph Theory_ , 2015.  Also in, Proc. 24th Int. Symp. on Algorithms and Computation, (ISAAC), page 185–195. (2013).
  * Angelini et al. [2016] Patrizio Angelini, William S. Evans, Fabrizio Frati, and Joachim Gudmundsson.  SEFE without mapping via large induced outerplane graphs in plane graphs.  _J. Graph Theory_ , 82(1):45–64, 2016.  doi:10.1002/JGT.21884.
  * Angelini et al. [2012b] Patrizio Angelini, Markus Geyer, Michael Kaufmann, and Daniel Neuwirth.  On a tree and a path with no geometric simultaneous embedding.  _J. Graph Algorithms Appl._ , 16(1):37–83, 2012b.  doi:10.7155/JGAA.00250.
  * Bannister et al. [2014] Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, and David Eppstein.  Superpatterns and universal point sets.  _J. Graph Algorithms Appl._ , 18(2):177–209, 2014.  doi:10.7155/JGAA.00318.
  * Bannister et al. [2019] Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood.  Track layouts, layered path decompositions, and leveled planarity.  _Algorithmica_ , 81(4):1561–1583, 2019.  doi:10.1007/S00453-018-0487-5.
  * Barba et al. [2017] Luis Barba, William Evans, Michael Hoffmann, Vincent Kusters, Maria Saumell, and Bettina Speckmann.  Column planarity and partially-simultaneous geometric embedding.  _J. Graph Algorithms Appl._ , 21(6):983–1002, 2017.  doi:10.7155/JGAA.00446.
  * Barba et al. [2015] Luís Barba, Michael Hoffmann, and Vincent Kusters.  Column planarity and partial simultaneous geometric embedding for outerplanar graphs.  In _Abstracts of the 31st European Workshop on Computational Geometry (EuroCG)_ , pages 53–56. 2015.
  * Barnette [1966] David Barnette.  Trees in polyhedral graphs.  _Canadian Journal of Mathematics_ , 18:731–736, 1966.
  * Biedl [2011] Therese Biedl.  Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs.  _Discret. Comput. Geom._ , 45(1):141–160, 2011.  doi:10.1007/S00454-010-9310-Z.
  * Bilinski et al. [2011] Mark Bilinski, Bill Jackson, Jie Ma, and Xingxing Yu.  Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge connected graphs.  _J. Combin. Theory Ser. B_ , 101:214–236, 2011.
  * Bläsius et al. [2013] Thomas Bläsius, Stephen G. Kobourov, and Ignaz Rutter.  Simultaneous embedding of planar graphs.  In _In Roberto Tamassia (editor), Handbook of Graph Drawing and Visualization_ , pages 349–381. 2013.
  * Bondy and Simonovit [1980] J. Adrian Bondy and Miklós Simonovit.  Longest cycles in 3-connected 3-regular graphs.  _Canadian Journal of Mathematics_ , 32:987–992, 1980.
  * Bose [1997] Prosenjit Bose.  On embedding an outer-planar graph in a point set.  In _Graph Drawing, 5th International Symposium, GD ’97_ , volume 1353 of _LNCS_ , pages 25–36. Springer, 1997.  doi:10.1007/3-540-63938-1_47.
  * Bose et al. [2023] Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Pat Morin, and Saeed Odak.  Connected dominating sets in triangulations.  _CoRR_ , abs/2312.03399, 2023.  doi:10.48550/ARXIV.2312.03399.  doi:10.48550/arXiv.2312.03399.
  * Bose et al. [2009] Prosenjit Bose, Vida Dujmović, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood.  A polynomial bound for untangling geometric planar graphs.  _Discret. Comput. Geom._ , 42(4):570–585, 2009.  doi:10.1007/S00454-008-9125-3.
  * Brandenburg et al. [2003] Franz-Josef Brandenburg, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Giuseppe Liotta, and Petra Mutzel.  Selected open problems in graph drawing.  In _Graph Drawing_ , volume 2912 of _LNCS_ , pages 515–539. Springer, 2003.
  * Braß et al. [2007] Peter Braß, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan Ismailescu, Stephen G. Kobourov, Anna Lubiw, and Joseph S. B. Mitchell.  On simultaneous planar graph embeddings.  _Comput. Geom._ , 36(2):117–130, 2007.  Also in, 8th Int. Workshop on Algorithms and Data Structures (WADS), pages 243–255. (2003).
  * Cano et al. [2014] Javier Cano, Csaba D. Tóth, and Jorge Urrutia.  Upper bound constructions for untangling planar geometric graphs.  _SIAM J. Discret. Math._ , 28(4):1935–1943, 2014.  doi:10.1137/130924172.
  * Cardinal et al. [2012] Jean Cardinal, Michael Hoffmann, and Vincent Kusters.  On universal point sets for planar graphs.  In _Computational Geometry and Graphs - Thailand-Japan Joint Conference, (TJJCCGG)_ , pages 30–41. 2012.
  * Castañeda and Urrutia [1996] Netzahualcoyotl Castañeda and Jorge Urrutia.  Straight line embeddings of planar graphs on point sets.  In _Proceedings of the 8th Canadian Conference on Computational Geometry, CCCG 1996_ , pages 312–318. 1996.
  * Cibulka [2010] Josef Cibulka.  Untangling polygons and graphs.  _Discret. Comput. Geom._ , 43(2):402–411, 2010.  doi:10.1007/S00454-009-9150-X.
  * Da Lozzo et al. [2018] Giordano Da Lozzo, Vida Dujmović, Fabrizio Frati, Tamara Mchedlidze, and Vincenzo Roselli.  Drawing planar graphs with many collinear vertices.  _J. Comput. Geom._ , 9(1):94–130, 2018.  doi:10.20382/JOCG.V9I1A4.
  * Di Giacomo et al. [2009] Emilio Di Giacomo, Walter Didimo, Marc J. van Kreveld, Giuseppe Liotta, and Bettina Speckmann.  Matched drawings of planar graphs.  _J. Graph Algorithms Appl._ , 13(3):423–445, 2009.
  * Diestel [2018] Reinhard Diestel.  _Graph theory_ , volume 173 of _Graduate Texts in Mathematics_.  Springer, 5th edition, 2018.
  * Dujmović [2017] Vida Dujmović.  The utility of untangling.  _J. Graph Algorithms Appl._ , 21(1):121–134, 2017.  doi:10.7155/JGAA.00407.  Also in, Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015.
  * Dujmović and Morin [2023] Vida Dujmović and Pat Morin.  Dual circumference and collinear sets.  _Discret. Comput. Geom._ , 69(1):26–50, 2023.  doi:10.1007/S00454-022-00418-4.
  * Dujmović et al. [2021] Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote.  Every collinear set in a planar graph is free.  _Discret. Comput. Geom._ , 65(4):999–1027, 2021.  doi:10.1007/S00454-019-00167-X.
  * Estrella-Balderrama et al. [2009] Alejandro Estrella-Balderrama, J. Joseph Fowler, and Stephen G. Kobourov.  Characterization of unlabeled level planar trees.  _Comput. Geom._ , 42(6-7):704–721, 2009.
  * Evans et al. [2014] William Evans, Vincent Kusters, Maria Saumell, and Bettina Speckmann.  Column planarity and partial simultaneous geometric embedding.  In _Graph Drawing - 22nd International Symposium, GD 2014_ , volume 8871 of _LNCS_ , pages 259–271. Springer, 2014.  doi:10.1007/978-3-662-45803-7_22.
  * Felsner et al. [2003] Stefan Felsner, Giuseppe Liotta, and Stephen Wismath.  Straight-line drawings on restricted integer grids in two and three dimensions.  _Journal of Graph Algorithms and Applications_ , 7(4):363–398, 2003\.  doi:10.7155/jgaa.00075.
  * de Fraysseix et al. [1988] Hubert de Fraysseix, János Pach, and Richard Pollack.  Small sets supporting fáry embeddings of planar graphs.  In Janos Simon, editor, _Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA_ , pages 426–433. ACM, 1988.  doi:10.1145/62212.62254.
  * de Fraysseix et al. [1990] Hubert de Fraysseix, János Pach, and Richard Pollack.  How to draw a planar graph on a grid.  _Comb._ , 10(1):41–51, 1990.  doi:10.1007/BF02122694.
  * Fáry [1948] István Fáry.  On straight-line representation of planar graphs.  _Acta Sci. Math. (Szeged)_ , 11:229–233, 1948.
  * Giacomo et al. [2023] Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani, and Stephen K. Wismath.  New bounds on the local and global edge-length ratio of planar graphs.  _CoRR_ , abs/2311.14634, 2023.  doi:10.48550/ARXIV.2311.14634.  doi:10.48550/arXiv.2311.14634.
  * Giacomo et al. [2012] Emilio Di Giacomo, Giuseppe Liotta, and Tamara Mchedlidze.  How many vertex locations can be arbitrarily chosen when drawing planar graphs?  _CoRR_ , abs/1212.0804, 2012.  doi:10.48550/arXiv.1212.0804.
  * Goaoc et al. [2009] Xavier Goaoc, Jan Kratochvíl, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, and Alexander Wolff.  Untangling a planar graph.  _Discret. Comput. Geom._ , 42(4):542–569, 2009.  doi:10.1007/S00454-008-9130-6.
  * Gritzmann et al. [1991] Peter Gritzmann, Bojan Mohar, Janos Pách, and Richard Pollack.  Embedding a planar triangulation with vertices at specified points (solution to problem e3341).  _Amer. Math. Monthly_ , 98:165–166, 1991.
  * Grünbaum and Walther [1973] Branko Grünbaum and Hansjoachim Walther.  Shortness exponents of families of graphs.  _Journal of Combinatorial Theory, Series A_ , 14(3):364–385, 1973\.  doi:https://doi.org/10.1016/0097-3165(73)90012-5.
  * Jackson [1986] Bill Jackson.  Longest cycles in 3-connected cubic graphs.  _J. Combin. Theory Ser. B_ , 41:17–26, 1986.
  * Kang et al. [2011] Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, and Oleg Verbitsky.  Untangling planar graphs from a specified vertex position - hard cases.  _Discret. Appl. Math._ , 159(8):789–799, 2011.  doi:10.1016/J.DAM.2011.01.011.
  * Kant and Bodlaender [1997] Goos Kant and Hans L. Bodlaender.  Triangulating planar graphs while minimizing the maximum degree.  _Inf. Comput._ , 135(1):1–14, 1997.  doi:10.1006/inco.1997.2635.
  * Liu et al. [2018] Qinghai Liu, Xingxing Yu, and Zhao Zhang.  Circumference of 3-connected cubic graphs.  _J. Comb. Theory, Ser. B_ , 128:134–159, 2018.  doi:10.1016/j.jctb.2017.08.008.
  * Owens [1984] Peter J. Owens.  Regular planar graphs with faces of only two types and shortness parameters.  _J. Graph Theory_ , 8(2):253–275, 1984.  doi:10.1002/JGT.3190080207.
  * Pach and Tardos [2002] János Pach and Gábor Tardos.  Untangling a polygon.  _Discret. Comput. Geom._ , 28(4):585–592, 2002.  doi:10.1007/S00454-002-2889-Y.  Also in, Graph Drawing, 9th International Symposium, GD 2001.
  * Pach and Tóth [2004] János Pach and Géza Tóth.  Monotone drawings of planar graphs.  _J. Graph Theory_ , 46(1):39–47, 2004.  doi:10.1002/JGT.10168.
  * Ravsky and Verbitsky [2011] Alexander Ravsky and Oleg Verbitsky.  On collinear sets in straight-line drawings.  In _Proc. 37th International Workshop on Graph-Theoretic Concepts in Computer Science, (WG)_ , pages 295–306. 2011.
  * Robertson et al. [1997] Neil Robertson, Daniel P. Sanders, Paul D. Seymour, and Robin Thomas.  The four-colour theorem.  _J. Comb. Theory, Ser. B_ , 70(1):2–44, 1997.  doi:10.1006/jctb.1997.1750.
  * Scheucher et al. [2020a] Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner.  A note on universal point sets for planar graphs.  _J. Graph Algorithms Appl._ , 24(3):247–267, 2020a.  doi:10.7155/JGAA.00529.
  * Scheucher et al. [2020b] Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner.  A note on universal point sets for planar graphs.  _J. Graph Algorithms Appl._ , 24(3):247–267, 2020b.  doi:10.7155/JGAA.00529.
  * Schnyder [1990] Walter Schnyder.  Embedding planar graphs on the grid.  In David S. Johnson, editor, _Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA_ , pages 138–148. SIAM, 1990.
  * Stein [1951] Sherman K. Stein.  Convex maps.  _Proceedings of the American Mathematical Society_ , 2(3):464–466, 1951.  doi:10.2307/2031777.
  * Steiner [2023] Raphael Steiner.  A logarithmic bound for simultaneous embeddings of planar graphs.  In _Graph Drawing and Network Visualization - 31st International Symposium, GD 2023_ , volume 14466 of _LNCS_ , pages 133–140. Springer, 2023\.  doi:10.1007/978-3-031-49275-4_9.
  * Tait [1880] Peter Guthrie Tait.  Remarks on the colouring of maps.  _Proc. Roy. Soc. Edinburgh Sect. A_ , 10:729, 1880.
  * Tutte [1946] William T. Tutte.  On Hamilton circuits.  _J. Lond. Math. Soc._ , 21:98–101, 1946.
  * Tutte [1963] William T. Tutte.  How to draw a graph.  _Proceedings of The London Mathematical Society_ , 13:743–767, 1963\.
  * Wagner [1936] Klaus Wagner.  Bemerkungen zum vierfarbenproblem.  _Jahresbericht der Deutschen Mathematiker-Vereinigung_ , 46:26–32, 1936.