Drawing Planar Graphs with Many Collinear Vertices

Abstract

Given a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every n-vertex planar graph has a planar straight-line drawing with $\varOmega (\sqrt{n})$ collinear vertices; for every n, there is an n-vertex planar graph whose every planar straight-line drawinghas $O(n^{0.986})$ collinear vertices; every n-vertex planar graph of treewidth at most two has a planar straight-line drawingwith $\varTheta (n)$ collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A set S of vertices in a planar graph G is collinear if G has a planar straight-line drawing where all the vertices in S are collinear. Ravsky and Verbitsky [20] considered the problem of determining the maximum cardinality of collinear sets in planar graphs. A collinear set S is free if a total order $<_S$ of S exists such that, for any |S| points on a straight line $\ell$, G has a planar straight-line drawing where the vertices in S are mapped to the |S| points and their order on $\ell$ matches $<_S$. Free collinear sets were first used (but not named) by Bose et al. [3] and then formally introduced by Ravsky and Verbitsky [20]. Collinear and free collinear sets relate to several graph drawings problems, as will be discussed later.

By exploiting the results in [3], Dujmović [9] showed that every n-vertex planar graph has a free collinear set with size $\sqrt{n/2}$. Ravsky and Verbitsky [20] negatively answered the question whether this bound can be improved to linear. Namely, they noted that if a planar triangulation has a collinear set S, then its dual has a cycle of length $\varOmega (|S|)$. Since there are m-vertex triconnected cubic planar graphs whose longest cycle has length $O(m^\sigma )$ [14], then there are n-vertex planar graphs in which every collinear set has size $O(n^\sigma )$. Here $\sigma$ is a graph-theoretic constant called shortness exponent; it is known that $\sigma <0.986$.

Which classes of planar graphs have (free) collinear sets with linear size? Goaoc et al. [12] proved (implicitly) that n-vertex outerplanar graphs have free collinear sets with size $(n+1)/2$. Ravsky and Verbitsky [20] proved that n-vertex planar graphs of treewidth at most two have free collinear sets with size n / 30; they also asked for other classes of graphs with (free) collinear sets with linear size, calling special attention to planar graphs of bounded treewidth and to planar graphs of bounded degree. In this paper we prove the following results.

Theorem 1

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

Theorem 2

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

Theorem 3

Every planar graph of treewidth k has a collinear set with size $\varOmega (k^2)$.

Theorem 1 generalizes the result on planar graphs of treewidth 2 [20]. Ravsky and Verbitsky [21, Corollary 3.5] constructed n-vertex planar graphs of treewidth 8 whose largest collinear set has size o(n); by using the dual of Tutte’s graph rather than the dual of the Barnette-Bosák-Lederberg’s graph in that construction, it is readily seen that the sub-linear bound holds true for planar graphs of treewidth at most 5. Thus, the question whether planar graphs of treewidth k admit (free) collinear sets with linear size remains open only for $k=4$. Theorem 2 provides the first linear lower bound on the size of collinear sets for a wide class of bounded-degree planar graphs. The result cannot be extended to planar graphs of degree at most 7, since there are n-vertex planar triangulations of maximum degree 7 whose dual graph has a longest cycle of length o(n) [17]. Finally, Theorem 3 improves the $\varOmega (\sqrt{n})$ bound on the size of collinear sets in general planar graphs for all planar graphs with treewidth $\omega (\root 4 \of {n})$. We now discuss implications of Theorems 1–3 for other graph drawing problems.

A column planar set in a graph G is a set $Q\subseteq V(G)$ satisfying the following property: there is a function $\gamma : Q \rightarrow \mathbb {R}$ such that, for any function $\lambda : Q \rightarrow \mathbb {R}$, there is a planar straight-line drawing of G where each vertex $v\in Q$ lies at point $(\gamma (v),\lambda (v))$. Column planar sets were defined by Evans et al. [11] motivated by applications to partial simultaneous geometric embeddings. They proved that n-vertex trees have column planar sets of size 14n / 17. The bounds in Theorems 1–3 carry over to the size of column planar sets for the corresponding graph classes.

A universal point subset for the family $\mathcal{G}_n$ of n-vertex planar graphs is a set P of points in the plane such that, for every $G\in \mathcal{G}_n$, there is a planar straight-line drawing of G in which |P| vertices lie at the points in P. Universal point subsets were introduced by Angelini et al. [1]. Every n points in general position form a universal point subset for the n-vertex outerplanar graphs [2, 5, 13] and every $\sqrt{n/2}$ points in the plane form a universal point subset for $\mathcal{G}_n$ [9]. By Theorem 1, we obtain that every $\lceil \frac{n-3}{8}\rceil$ points in the plane form a universal point subset for the n-vertex planar graphs of treewidth at most three.

Given a straight-line drawing of a planar graph, possibly with crossings, to untangle it means to assign new locations to some vertices so that the resulting straight-line drawing is planar. The goal is to do so while keeping as many vertices as possible fixed [3, 4, 7, 12, 15, 18, 20]. General n-vertex planar graphs can be untangled while keeping $\varOmega (n^{0.25})$ vertices fixed [3]; this bound cannot be improved above $O(n^{0.4948})$ [4]. Asymptotically tight bounds are known for paths [7], trees [12], outerplanar graphs [12], and planar graphs of treewidth 2 [20]. By Theorem 1, we obtain that every n-vertex planar graph of treewidth at most 3 can be untangled while keeping $\varOmega (\sqrt{n})$ vertices fixed. This bound is the best possible [3] and generalizes most of the mentioned previous results [12, 20].

Complete proofs can be found in the full version of the paper [8].

2 Preliminaries

A k-tree is either $K_{k+1}$ or can be obtained from a smaller k-tree G by the insertion of a vertex adjacent to all the vertices in a k-clique of G. The treewidth of a graph G is the minimum k such that G is a subgraph of a k-tree.

A connected plane graph G is a connected planar graph with a plane embedding – an equivalence class of planar drawings of G, where two drawings are equivalent if each vertex has the same clockwise order of its incident edges and the outer faces are delimited by the same walk. We think about any plane graph G as drawn according to its plane embedding; also, when we talk about a planar drawing of G, we mean that it respects its plane embedding. The interior of G is the closure of the union of its internal faces. A subgraph H of G has the plane embedding obtained from the one of G by deleting vertices and edges not in H.

We denote the degree of a vertex v in a graph G by $\delta _G(v)$. A graph is cubic (subcubic) if every vertex has degree 3 (resp. at most 3). If $U\subseteq V(G)$, we denote by $G-U$ the graph $(V(G)-U,\{(u,v)\in E(G)|u,v\notin U\})$; the subgraph of G induced by U is $(U,\{(u,v)\in E(G)|u,v\in U\})$. If H is a subgraph of G and $v\in V(G)-V(H)$, we let $H\cup \{v\}$ be the graph $(V(H)\cup \{v\},E(H))$. An H-bridge B is either trivial – it is an edge of G not in H with both end-vertices in H – or non-trivial – it is a connected component of $G-V(H)$ together with the edges from that component to H. The vertices in $V(H)\cap V(B)$ are called attachments.

Let G be a connected graph. If G has no cut-vertex – a vertex whose removal disconnects G – and it is not an edge, then it is biconnected. A biconnected component of G is a maximal biconnected subgraph of G. If G is biconnected, then a separation pair is a pair of vertices $\{a,b\}$ whose removal disconnects G; also, an $\{a,b\}$ -component is either trivial – it is edge (a, b) – or non-trivial – it is the subgraph of G induced by a, b, and the vertices of a connected component of $G-\{a,b\}$. If G has no separation pair, then it is triconnected.

3 From a Geometric to a Topological Problem

In this section we show that the problem of determining a large collinear set in a planar graph, which is geometric by definition, can be turned into a purely topological problem. This may be useful to obtain bounds for the size of collinear sets in classes of planar graphs different from the ones we studied in this paper.

An open simple curve $\lambda$ is good for a planar drawing $\varGamma$ of a plane graph G if each edge e of G is either contained in $\lambda$ or has at most one point in common with $\lambda$ (if $\lambda$ passes through an end-vertex of e, that counts as a common point). Clearly, the existence of a good curve passing through a certain sequence of vertices, edges, and faces of G does not depend on the actual drawing $\varGamma$, but only on the plane embedding of G. Hence, we often talk about the existence of good curves in plane graphs, rather than in their planar drawings. We denote by $R_{G,\lambda }$ the only unbounded region of the plane defined by G and $\lambda$. Curve $\lambda$ is proper if both its end-points are incident to $R_{G,\lambda }$. We have the following.

Theorem 4

A plane graph G has a planar straight-line drawing with x collinear vertices if and only if G has a proper good curve that passes through x vertices.

Fig. 1.

(a) A proper good curve for a plane graph G. (b) Augmentation of G. (c) A planar straight-line drawing of the augmented graph G. (d) Planar polyline (top) and straight-line (bottom) drawings of the original G.

Proof Sketch

The necessity is readily proved. For the sufficiency, let $\lambda$ be a proper good curve through x vertices of G; refer to Fig. 1. Add dummy vertices at two points $d_1$ and $d_2$ in $R_{G,\lambda }$, at the end-points a and b of $\lambda$, and at each crossing between an edge and $\lambda$; also, add dummy edges $(d_1,a)$, $(d_1,b)$, $(d_2,a)$, $(d_2,b)$ and between any two consecutive vertices along $\lambda$ (the latter edges form a path $P_{\lambda }$); finally, triangulate the internal faces of G with dummy vertices and edges that do not connect non-consecutive vertices on $\lambda$. Let $C_1$ ($C_2$) be the cycle composed of $P_{\lambda }$ and of the edges $(d_1,a)$ and $(d_1,b)$ (resp. $(d_2,a)$ and $(d_2,b)$). Represent $C_1$ ($C_2$) as a convex polygon $Q_1$ (resp. $Q_2$), with $P_{\lambda }$ on a horizontal line $\ell$; since the subgraphs of G inside $C_1$ and $C_2$ are triconnected, they have planar straight-line drawings with $C_1$ and $C_2$ represented by $Q_1$ and $Q_2$, respectively [22]. Removing the dummy vertices and edges results in a planar drawing $\varGamma$ of the original graph G where each edge is y-monotone. A planar straight-line drawing $\varGamma '$ of G in which the y-coordinate of each vertex is the same as in $\varGamma$ always exists [10, 19]. Then the x vertices of G curve $\lambda$ passes through lie on $\ell$ in $\varGamma '$.    $\square$

4 Planar Graphs with Treewidth at Most Three

In this section we prove Theorem 1. We regard a plane 3-cycle as a plane 3-tree; then every plane graph G with $n\ge 3$ vertices and treewidth at most 3 can be augmented with dummy edges to a plane 3-tree $G'$ [16] and every free collinear set in $G'$ is also a free collinear set in G. Thus, in the following, we assume that G is a plane 3-tree. We first prove that G has a collinear set with size $\lceil \frac{n-3}{8}\rceil$; by Theorem 4 it suffices to prove that G has a proper good curve through $\lceil \frac{n-3}{8}\rceil$ vertices. Let u, v, and z be the external vertices of G. If $n=3$, then G is empty. Otherwise, the central vertex of G is the unique internal vertex w adjacent to u, v, and z. The plane 3-trees $G_1$, $G_2$, and $G_3$ which are the subgraphs of G inside cycles (u, v, w), (u, z, w), and (v, z, w) are the children of G and of w. We associate to each internal vertex x of G a plane 3-tree G(x) as follows. We associate G to w and we use recursion on the children of G; then x is the central vertex of G(x). An internal vertex x of G is of type A, B, C, or D if, respectively, 3, 2, 1, or 0 of the children of G(x) are empty (see Fig. 2(a)). Let a(G), b(G), c(G), and d(G) be the number of internal vertices of G of type A, B, C, and D, respectively, and let $m=n-3$ be the number of internal vertices of G.

Fig. 2.

(a) A vertex x of type A (top-left), B (top-right), C (bottom-left), and D (bottom-right). (b) $\lambda _{u}(G)$ (solid), $\lambda _{v}(G)$ (dotted), and $\lambda _{z}(G)$ (dashed) if $m=0$ (top) and $m=1$ (bottom). (c) $\lambda _{u}(G)$, $\lambda _{v}(G)$, and $\lambda _{z}(G)$ if w is of type C or D.

In the following we present an algorithm that computes three proper good curves $\lambda _{u}(G)$, $\lambda _v(G)$, and $\lambda _z(G)$ lying in the interior of G. For every edge (x, y) of G, let $p_{xy}$ be an arbitrary internal point of (x, y). The end-points of $\lambda _u(G)$ are $p_{uv}$ and $p_{uz}$, those of $\lambda _v(G)$ are $p_{uv}$ and $p_{vz}$, and those of $\lambda _z(G)$ are $p_{uz}$ and $p_{vz}$. Although each of $\lambda _{u}(G)$, $\lambda _v(G)$, and $\lambda _z(G)$ is a good curve, any two of these curves might cross each other and pass through the same vertices of G. Each of these curves passes through all the internal vertices of type A, through no vertex of type C or D, and through “some” vertices of type B. We will prove that the total number of internal vertices of G these curves pass through is at least 3m / 8, hence one of them passes through at least $\lceil m/8 \rceil$ internal vertices.

The curves $\lambda _{u}(G)$, $\lambda _v(G)$, and $\lambda _z(G)$ are constructed by induction on m. If $m=0$, then $\lambda _{u}(G)$ traverses the internal face (u, v, z) from $p_{uv}$ to $p_{uz}$, while if $m=1$, then $\lambda _{u}(G)$ traverses the internal face (u, v, w) from $p_{uv}$ to the central vertex w of G and the internal face (u, z, w) from w to $p_{uz}$ (see Fig. 2(b)). Curves $\lambda _{v}(G)$ and $\lambda _{z}(G)$ are defined analogously.

If $m>1$, then we distinguish the case in which w is of type C or D from the one in which w is of type B. In the former case (see Fig. 2(c)), the curves are constructed by composing the curves inductively constructed for the children of G. In the latter case (see Fig. 3), a sequence of vertices of type B, called B-chain, is recovered; its arrangement in G is exploited in order to ensure that $\lambda _{u}(G)$, $\lambda _v(G)$, and $\lambda _z(G)$ pass through many vertices of type B.

Assume first that w is of type C or D. Inductively construct curves $\lambda _{u}(G_1)$, $\lambda _v(G_1)$, and $\lambda _w(G_1)$ for $G_1$, curves $\lambda _{u}(G_2)$, $\lambda _z(G_2)$, and $\lambda _w(G_2)$ for $G_2$, and curves $\lambda _{v}(G_3)$, $\lambda _z(G_3)$, and $\lambda _w(G_3)$ for $G_3$. Let $\lambda _{u}(G)=\lambda _v(G_1)\cup \lambda _w(G_3)\cup \lambda _z(G_2)$, $\lambda _{v}(G)=\lambda _u(G_1)\cup \lambda _w(G_2)\cup \lambda _z(G_3)$, and $\lambda _{z}(G)=\lambda _u(G_2)\cup \lambda _w(G_1)\cup \lambda _v(G_3)$.

Assume next that w is of type B. Let $H_0=G$, let $w_1=w$, and let $H_1$ be the only non-empty child of G. If cycle (v, w, z) delimits the outer face of $H_1$, define three paths $P_u=(u,w)$, $P_v=(v)$, and $P_z=(z)$; analogously, if cycle (u, w, z) delimits the outer face of $H_1$, let $P_u=(u)$, $P_v=(v,w)$, and $P_z=(z)$; finally, if cycle (u, v, w) delimits the outer face of $H_1$, let $P_u=(u)$, $P_v=(v)$, and $P_z=(z,w)$.

Now suppose that, for $i\ge 1$, a sequence $w_1,\dots ,w_i$ of vertices of type B, a sequence $H_0,\dots ,H_i$ of plane 3-trees, and paths $P_u$, $P_v$, and $P_z$ have been defined satisfying the following properties: (1) for $1\le j\le i$, $w_j$ is the central vertex of $H_{j-1}$ and $H_j$ is the only non-empty child of $H_{j-1}$; (2) $P_u$, $P_v$, and $P_z$ are vertex-disjoint and each of them is induced in G; and (3) $P_u$, $P_v$, and $P_z$ connect u, v, and z with the three external vertices $u'$, $v'$, and $z'$ of $H_i$, where $u'\in P_u$, $v'\in P_v$, and $z'\in P_z$. Properties (1)–(3) are indeed satisfied with $i=1$. Consider the central vertex $w_{i+1}$ of $H_i$.

If $w_{i+1}$ is of type B, then let $H_{i+1}$ be the unique non-empty child of $H_{i}$. If cycle $(v',z',w_{i+1})$ delimits the outer face of $H_{i+1}$, add edge $(u',w_{i+1})$ to $P_u$ and leave $P_v$ and $P_z$ unaltered; the other cases are analogous. Properties (1)–(3) are clearly satisfied by this construction.

If $w_{i+1}$ is not of type B, then we call the sequence $w_1,\dots ,w_i$ a B-chain of G. Let $H=H_i$, let $P_u=(u=u_1,\dots ,u_U=u')$, let $P_v=(v=v_1,\dots ,v_V=v')$, and let $P_z=(z=z_1,\dots ,z_Z=z')$; also, define cycles $C_{uv}=P_u \cup (u,v) \cup P_v \cup (u',v')$, $C_{uz}=P_u \cup (u,z) \cup P_z \cup (u',z')$, and $C_{vz}=P_v \cup (v,z) \cup P_z \cup (v',z')$. Each of these cycles has no vertex of G inside, and every edge of G inside one of them connects two vertices on distinct paths among $P_u$, $P_v$, and $P_z$, by Property (2). We are going to use the following (a similar lemma can be stated for $C_{uz}$ and $C_{vz}$).

Lemma 1

Let $p_1$ and $p_2$ be points on $C_{uv}$, possibly coinciding with vertices of $C_{uv}$, and not both on the same edge of G. A good curve exists that connects $p_1$ and $p_2$, that lies inside $C_{uv}$, except at $p_1$ and $p_2$, and that intersects each edge of G inside $C_{uv}$ at most once.

We now construct $\lambda _{u}(G)$, $\lambda _v(G)$, and $\lambda _z(G)$. Inductively construct curves $\lambda _{u'}(H)$, $\lambda _{v'}(H)$, and $\lambda _{z'}(H)$ for H. We distinguish three cases based on how many among $P_u$, $P_v$, and $P_z$ are single vertices (not all of them are, since $w_1\ne u,v,z$). We discuss here the case in which none of them is a single vertex, as in Fig. 3(a); the other cases, which are illustrated in Figs. 3(b)–(c), are similar. We show how to construct $\lambda _{u}(G)$; the construction of $\lambda _{v}(G)$ and $\lambda _{z}(G)$ is analogous.

Fig. 3.

$\lambda _{u}(G)$, $\lambda _{v}(G)$, and $\lambda _{z}(G)$ if w is of type B. (a) None of $P_u$, $P_v$, and $P_z$ is a single vertex. (b) Only $P_z$ is a single vertex. (c) $P_u$ and $P_v$ are single vertices.

If $Z>2$, then $\lambda _{u}(G)$ consists of curves $\lambda ^0_{u},\dots ,\lambda ^4_{u}$; curve $\lambda ^0_{u}$ lies inside $C_{uz}$ and connects $p_{uz}$ with $z_2$, which is internal to $P_z$ since $Z>2$; $\lambda ^1_{u}$ coincides with path $(z_2,\dots ,z_{Z-1})$ (which is a single vertex if $Z=3$); $\lambda ^2_{u}$ lies inside $C_{vz}$ and connects $z_{Z-1}$ with $p_{v'z'}$; $\lambda ^3_{u}$ coincides with $\lambda _{v'}(H)$; finally, $\lambda ^4_{u}$ lies inside $C_{uv}$ and connects $p_{u'v'}$ with $p_{uv}$. Curves $\lambda ^0_{u}$, $\lambda ^2_{u}$, and $\lambda ^4_{u}$ are constructed as in Lemma 1. If $Z=2$, then $\lambda _{u}(G)$ consists of curves $\lambda ^1_{u},\dots ,\lambda ^4_{u}$; curve $\lambda ^1_{u}$ lies inside $C_{uz}$ and connects $p_{uz}$ with $p_{zz'}$; $\lambda ^2_{u}$ lies inside $C_{vz}$ and connects $p_{zz'}$ with $p_{v'z'}$; $\lambda ^3_{u}$ and $\lambda ^4_{u}$ are defined as in the case $Z>2$. Curves $\lambda ^1_{u}$, $\lambda ^2_{u}$, and $\lambda ^4_{u}$ are constructed as in Lemma 1. This completes the construction of $\lambda _{u}(G)$, $\lambda _{v}(G)$, and $\lambda _{z}(G)$.

The curves $\lambda _{u}(G)$, $\lambda _{v}(G)$, and $\lambda _{z}(G)$ are clearly proper. Lemmas 2 and 3 prove that they are good and pass through many vertices. We introduce three parameters for the latter proof: s(G) is the number of vertices the curves pass through (counting each vertex with a multiplicity equal to the number of curves that pass through it), x(G) is the number of internal vertices of type B none of the curves passes through, and h(G) is the number of B-chains of G.

Lemma 2

Curves $\lambda _{u}(G)$, $\lambda _{v}(G)$, and $\lambda _{z}(G)$ are good.

Lemma 3

The following hold true if $m\ge 1$: (1) $a(G)+b(G)+c(G)+d(G)=m$; (2) $a(G)=c(G)+2 d(G)+1$; (3) $h(G)\le 2c(G)+3 d(G)+1$; (4) $x(G)\le b(G)$; (5) $x(G)\le 3h(G)$; and (6) $s(G)\ge 3a(G)+b(G)-x(G)$.

Proof Sketch

(1) is true since every internal vertex is of one of types A–D. (4) follows by definition of x(G). (5) is true since every internal vertex of type B is in a B-chain, and for every B-chain the three curves pass through all but at most three of its vertices. (2), (3), and (6) can be proved by induction on m, by distinguishing four cases based on the type of w. In particular, (6) exploits the fact that, in each case, the three curves contain all the inductively constructed curves and pass through all but at most three vertices of a B-chain.    $\square$

We use Lemma 3 as follows. Let $k=1/8$. If $a(G)\ge km$, then by (4) and (6) we get $s(G)\ge 3a(G)\ge 3km$. If $a(G)< km$, by (1) and (6) we get $s(G)\ge 3a(G) + (m -a(G)- c(G) - d(G)) - x(G)$, which by (5) becomes $s(G)\ge m + 2a(G) - c(G) - d(G) - 3h(G)$. Using (2) and (3) we get $s(G)\ge m + 2 (c(G)+2d(G)+1) -c(G)-d(G)-3(2c(G)+3d(G)+1)= m - 5c(G)-6d(G)-1$. Again by (2) and by hypothesis we get $c(G)+2d(G)+1<km$, thus $5c(G)+6d(G)+1<5c(G)+10d(G)+5<5km$. Hence, $s(G)\ge m-5km$. Since $k=1/8$, we have $s(G)\ge 3m/8$ both if $a(G)\ge m/8$ and if $a(G)< m/8$. Thus one of $\lambda _u(G)$, $\lambda _v(G)$, and $\lambda _z(G)$ is a proper good curve passing through $\lceil \frac{n-3}{8}\rceil$ internal vertices of G. This concludes the proof that G has a collinear set with size $\lceil \frac{n-3}{8}\rceil$.

We now strengthen this result by proving that G has a free collinear set with the same size. This is accomplished by means of the following lemma, which concludes the proof of Theorem 1.

Theorem 5

Every collinear set in a plane 3-tree is also a free collinear set.

Proof Sketch

Let G be a plane 3-tree and $\varPsi$ be a planar straight-line drawing of G with a set S of vertices on a straight line $\ell$. Let $<_{\varPsi }$ be the order of the vertices in S along $\ell$ in $\varPsi$. Our proof shows that, for any set $X_S$ of |S| points on $\ell$, there is a planar straight-line drawing $\varGamma$ of G such that: (1) every vertex is above, below, or on $\ell$ in $\varGamma$ if and only the same holds in $\varPsi$; and (2) the i-th vertex in $<_{\varPsi }$ is at the i-th point in $X_S$ in left-to-right order along $\ell$. This is proved by assuming an arbitrary drawing $\varDelta$ of (u, v, z), by drawing w so as to split $\varDelta$ into three triangles with a suitable number of points of $X_S$ in their interior, and by then using recursion on the children of G.    $\square$

5 Triconnected Cubic Planar Graphs

In this section we prove Theorem 2. By Theorem 4 it suffices to prove that every n-vertex triconnected cubic plane graph has a proper good curve $\lambda$ through $\lceil \frac{n}{4}\rceil$ vertices. The proof is by induction on n; Lemma 4 below states our inductive hypothesis. In order to split the graph into subgraphs on which induction can be applied, we use a structural decomposition that is derived from a paper by Chen and Yu [6] and that applies to a class of graphs, called strong circuit graphs in [6], wider than triconnected cubic plane graphs. We introduce the concept of well-formed quadruple in order to point out some properties of the graphs in this class. In particular, the inductive hypothesis handles carefully the set X of degree-2 vertices of the graph, which have neighbors that are not in the graph at the current level of the induction; since $\lambda$ might pass through these neighbors, it has to avoid the vertices in X, in order to be good. Special conditions are ensured for two vertices u and v which work as link to the rest of the graph.

We introduce some definitions. Given two external vertices u and v of a biconnected plane graph G, let $\tau _{uv}(G)$ and $\beta _{uv}(G)$ be the paths delimiting the outer face of G in clockwise and counter-clockwise direction from u to v, respectively. Let $\pi$ be one of $\tau _{uv}(G)$ and $\beta _{uv}(G)$. An intersection point (a proper intersection point) between an open curve $\lambda$ and $\pi$ is a point p belonging to both $\lambda$ and $\pi$ such that, for every $\epsilon >0$, the part of $\lambda$ in the disk centered at p with radius $\epsilon$ contains points not in $\pi$ (resp. points in the outer face of G); if the end-vertices of $\lambda$ are in $\pi$, then we regard them as intersection points.

A quadruple (G, u, v, X) is well-formed if: (a) G is a biconnected subcubic plane graph; (b) u and v are two external vertices of G; (c) $\delta _G(u)=\delta _G(v)=2$; (d) if edge (u, v) exists, it coincides with $\tau _{uv}(G)$; (e) for every separation pair $\{a,b\}$ of G, a and b are external vertices of G and at least one of them is internal to $\beta _{uv}(G)$; further, every non-trivial $\{a,b\}$-component of G contains an external vertex of G different from a and b; and (f) $X=(x_1,\dots ,x_m)$ is a (possibly empty) sequence of degree-2 vertices of G in $\beta _{uv}(G)$, different from u and v, and in this order along $\beta _{uv}(G)$ from u to v. We have the following main lemma.

Lemma 4

Let (G, u, v, X) be a well-formed quadruple. There exists a proper good curve $\lambda$ such that (see Fig. 4(a)):

• (1) $\lambda$ starts at u, does not pass through v, and ends at a point z of $\beta _{uv}(G)$;

• (2) z is between $x_m$ and v on $\beta _{uv}(G)$ (if $X=\emptyset$, this condition is vacuous);

• (3) the intersection points between $\lambda$ and $\beta _{uv}(G)$ occur along $\lambda$ from u to z and occur along $\beta _{uv}(G)$ from u to v in the same order $u=p_1,\dots ,p_\ell =z$;

• (4) the vertices in X are incident to $R_{G,\lambda }$ and are not on $\lambda$; if $p_i$, $x_j$ and $p_{i+1}$ are in this order along $\beta _{uv}(G)$, then the part of $\lambda$ between $p_i$ and $p_{i+1}$ is in the interior of G;

• (5) $\lambda$ and $\tau _{uv}(G)$ have no proper intersection point; and

• (6) let $L_{\lambda }$ ($N_{\lambda }$) be the subset of vertices in $V(G)-X$ that are (resp. are not) on $\lambda$; each vertex in $N_{\lambda }$ can be charged to a vertex in $L_{\lambda }$ so that each vertex in $L_{\lambda }$ is charged with at most 3 vertices and u is charged with at most 1 vertex.

Fig. 4.

(a) Illustration for Lemma 4. The gray region is the interior of G. The vertices in X are squares, the intersection points between $\lambda$ and $\beta _{uv}(G)$ are circles, and u and v are disks. (b) Illustration for Lemma 5 with $k=3$.

Before proving Lemma 4 we state the following (see Fig. 4(b)).

Lemma 5

Let (G, u, v, X) be a well-formed quadruple and $\{a,b\}$ be a separation pair of G with $a,b\in \beta _{uv}(G)$. The $\{a,b\}$-component $G_{ab}$ of G containing $\beta _{ab}(G)$ either coincides with $\beta _{ab}(G)$ or consists of: (i) a path $P_0=(a,\dots ,u_1)$ (possibly a single vertex); (ii) for $i=1,\dots ,k$ with $k\ge 1$, a biconnected component $G_i$ of $G_{ab}$ containing vertices $u_i$ and $v_i$, where $(G_i,u_i,v_i,X_i)$ is a well-formed quadruple with $X_i=X\cap V(G_i)$; (iii) for $i=1,\dots ,k-1$, a path $P_i=(v_i,\dots ,u_{i+1})$, where $u_{i+1}\ne v_i$; and (iv) a path $P_{k}=(v_{k},\dots ,b)$ (possibly a single vertex).

We outline the proof of Lemma 4, which is by induction on the size of G.

Base Case: G is a cycle; see Fig. 5(a). By Property (e) of (G, u, v, X), $\{u,v\}$ is not a separation pair of G, hence edge (u, v) exists and coincides with $\tau _{uv}(G)$. Curve $\lambda$ starts at u; it then passes through the vertices in $V(G)-(X\cup \{v\})$ in the order as they appear along $\beta _{uv}(G)$ from u to v; if two vertices in $V(G)-(X\cup \{v\})$ are consecutive in $\beta _{uv}(G)$, then $\lambda$ contains the edge between them. If the neighbor $v'$ of v in $\beta _{uv}(G)$ is not in X, then $\lambda$ ends at $v'$, otherwise $\lambda$ ends at a point z in the interior of edge $(v,v')$. Finally, charge v to u.

Next we describe the inductive cases. In the description of each case, we implicitly assume that none of the previously described cases applies.

Fig. 5.

Base case (a) and Case 1 with $k=3$ (b) for the proof of Lemma 4.

Case 1: edge (u, v) exists; see Fig. 5(b). By Property (d) of (G, u, v, X), edge (u, v) coincides with $\tau _{uv}(G)$. By Property (c), v has a unique neighbor $v'\ne u$, hence $\{u,v'\}$ is a separation pair to which Lemma 5 applies. For $i=1,\dots k$, use induction to construct a proper good curve $\lambda _i$ satisfying the properties of Lemma 4 for the well-formed quadruple $(G_i,u_i,v_i,X_i)$, defined as in Lemma 5.

Curve $\lambda$ starts at u and passes through the vertices in $V(P_0)\setminus X$ until reaching $u_1$; this part of $\lambda$ lies in the internal face of G incident to edge (u, v) and is constructed similarly to the base case. Curve $\lambda$ continues with $\lambda _1$, which ends at a point $z_1$. Then $\lambda$ traverses the outer face of G to reach the neighbor $v'_1$ of $v_1$ in $P_1$ (if $v'_1\notin X$) or a point in the interior of edge $(v_1,v'_1)$ (if $v'_1\in X$); this part of $\lambda$ can be drawn without causing self-intersections since $\lambda _1$ satisfies Properties (2), (3), and (5) of Lemma 4 – these properties ensure that $z_1$ and $v'_1$ are both incident to $R_{G,\lambda _1}$. Curve $\lambda$ continues similarly until a point $z_k$ in $\beta _{u_k v_k} (G_k)$ is reached. If the neighbor $v'_k$ of $v_k$ in $P_k$ is v, then $\lambda$ stops at $z=z_k$; otherwise, it traverses the outer face of G from $z_k$ to a point on edge $(v_k,v'_k)$ – this point is $v'_k$ if $v'_k\notin X$ – and it ends by passing through the vertices in $V(P_k)\setminus (X\cup \{v\})$, similarly to the base case. Inductively compute a charge of the vertices in $(N_{\lambda }\cap V(G_i))$ to the vertices in $L_{\lambda }\cap V(G_i)$; finally, charge v to u.

If Case 1 does not apply, by Property (e) of (G, u, v, X), $\{u,v\}$ is not a separation pair of G, hence u is not a cut-vertex of graph $G-\{v\}$. Let H be the biconnected component of $G-\{v\}$ containing u. Graph G is composed of H, of a trivial $H\cup \{v\}$-bridge $B_1=(y_1,v)$, which is an edge in $\tau _{uv}(G)$, and of an $H\cup \{v\}$-bridge $B_2$ with attachments v and $y_2$, where $y_1$ and $y_2$ are in H. Let $X'=\{y_2\}\cup (X\cap V(H))$. Then $(H,u,y_1,X')$ is a well-formed quadruple.

Case 2: $B_2$ contains a vertex not in $X\cup \{v,y_2\}$. Refer to Fig. 6(a). Curve $\lambda$ is composed of curves $\lambda _1$, $\lambda _2$, and $\lambda _3$. Curve $\lambda _1$ is inductively constructed for $(H,u,y_1,X')$. Since $y_2\in X'$, $\lambda _1$ ends at a point $z_0$ in $\beta _{y_2y_1}(H)$. Curve $\lambda _2$ lies in the internal face of G incident to edge $(y_1,v)$ and connects $z_0$ with the first vertex $u'\ne y_2$ not in X encountered when traversing $\beta _{y_2v}(G)$ from $y_2$ to v; $u'$ exists by the hypothesis of Case 2 and by Property (f) of (G, u, v, X). Properties (3)–(5) of $\lambda _1$ ensure that $y_2$ is not on $\lambda _1$ and is incident to $R_{G,\lambda _1}$. Thus, even if $u'$ is adjacent to $y_2$, still $\lambda$ intersects $(y_2,u')$ only once. Finally, $\lambda _3$ connects $u'$ with a point $z\ne y_2,v$ on $\beta _{y_2 v}(G)$; since $\{y_2,v\}$ is a separation pair of G, Lemma 5 applies and curve $\lambda _3$ is constructed as in Case 1. Inductively determine the charge of the vertices in $(N_{\lambda }\cap V(H))-\{y_2\}$ to the vertices in $L_{\lambda }\cap V(H)$, and the charge of the vertices in $N_{\lambda }$ in each biconnected component $G_i$ of $B_2$ to the vertices in $L_{\lambda }\cap V(G_i)$. Finally, charge $y_2$ and v to $u'$.

Fig. 6.

(a) Case 2, (b) Case 3, (c) Case 4, and (d) Case 5 of the proof of Lemma 4.

If Case 2 does not apply, $B_2$ is a path $\beta _{y_2 v}$ whose internal vertices are in X.

Case 3: edge $(u,y_1)$ exists. By Property (d) of $(H,u,y_1,X')$, edge $(u,y_1)$ coincides with $\tau _{uy_1}(H)$. Let $y'$ be the neighbor of $y_1$ in $\beta _{uy_1}(H)$. If H has a vertex not in $X'\cup \{u,y_1\}$ as in Fig. 6(b) – otherwise $\lambda$ is easily constructed – then $\{u,y'\}$ is a separation pair of H and Lemma 5 applies. Construct a curve $\lambda _1$ between u and a point $z_k\ne y_1$ on $\beta _{y_2y_1}(H)$ as in Case 1. Curve $\lambda$ consists of $\lambda _1$ and of a curve $\lambda _2$ in the internal face of G incident to edge $(v,y_1)$ between $z_k$ and a point z on edge $(v,v')$. Inductively charge the vertices in the biconnected components on which induction is applied. Charge v to u, and $y_1$ and $y_2$ to the first vertex $u'\ne u$ not in $X'$ encountered when traversing $\beta _{uy_1}(H)$ from u to $y_1$.

If Case 3 does not apply, then u is not a cut-vertex of graph $H-\{y_1\}$, since $\{u,y_1\}$ is not a separation pair of H. Graph H is composed of the biconnected component K of $H-\{y_1\}$ containing u, of a trivial $K\cup \{y_1\}$-bridge $D_1=(w_1,y_1)$, and of a $K\cup \{y_1\}$-bridge $D_2$ with attachments $y_1$ and $w_2$, where $w_1,w_2\in V(K)$.

Case 4: $y_2 \in K$. Refer to Fig. 6(c). Since $\delta _G(y_2)\le 3$, $y_2$ and $w_2$ are distinct. Also, $w_2$ is an internal vertex of G; hence, $D_2$ is a trivial $K\cup \{y_1\}$-bridge. Let $X''=(X\cap V(K))\cup \{y_2,w_2\}$; inductively construct a curve $\lambda _1$ connecting u with a point $z_0\ne w_1$ in $\beta _{w_2w_1}(K)$ for the well-formed quadruple $(K,u,w_1,X'')$. Curve $\lambda$ consists of $\lambda _1$ and of a curve $\lambda _2$ from $z_0$ to a point z on edge $(v,v')$ passing through $y_1$. Curve $\lambda _2$ lies in the internal faces of G incident to edges $(w_1,y_1)$ and $(y_1,v)$. Inductively charge the vertices in $(N_{\lambda }\cap V(K))-\{y_2,w_2\}$ to the vertices in $L_{\lambda }\cap V(K)$; charge v, $y_2$, and $w_2$ to $y_1$.

Case 5: $y_2 \notin K$. Let $X''=\{w_2\}\cup (X\cap V(K))$. Curve $\lambda$ consists of four curves $\lambda _1,\dots ,\lambda _4$. Inductively construct $\lambda _1$ for the well-formed quadruple $(K,u,w_1,X'')$ between u and a point $z_0\ne w_1$ in $\beta _{w_2w_1}(K)$. If $D_2$ has a vertex not in $X'\cup \{y_1,w_2\}$, as in Fig. 6(d) – otherwise $\lambda$ is constructed similarly to Case 4 – then $\lambda _2$ connects $z_0$ with the first vertex $u'\ne w_2$ not in $X'$ encountered while traversing $\beta _{w_2 y_1}(H)$ from $w_2$ to $y_1$; $\lambda _2$ is in the internal face of G incident to edge $(w_1,y_1)$. Curve $\lambda _3$ connects $u'$ with a point $z'$ in $\beta _{y_2y_1}(H)$; $\{w_2,y_1\}$ is a separation pair of H, hence Lemma 5 applies and curve $\lambda _3$ is constructed as in Case 1. Finally, $\lambda _4$ connects $z'$ with a point z on edge $(v,v')$ passing through $y_1$. Inductively charge the vertices in the biconnected components on which induction is applied. Charge v, $y_2$, and $w_2$ to $y_1$. This concludes the proof of Lemma 4.

We now prove Theorem 2. Let G be an n-vertex triconnected cubic plane graph. Let H be the plane graph obtained from G by removing any edge (u, v) incident to the outer face of G. Then $(H,u,v,\emptyset )$ is a well-formed quadruple and H has a proper good curve $\lambda$ as in Lemma 4. Insert (u, v) in the outer face of H, restoring the plane embedding of G. By Properties (1)–(5) of $\lambda$ edge (u, v) does not intersect $\lambda$ other than at u, hence $\lambda$ remains proper and good. By Property (6) with $X=\emptyset$, $\lambda$ passes through $\lceil \frac{n}{4}\rceil$ vertices of G. This concludes the proof.

6 Implications for Other Graph Drawing Problems

In this section we present corollaries of our results to other graph drawing problems. The key tool to establish these connections is a lemma that appeared in [3, Lemma 1], which we explicitly state here in two more readily applicable versions.

Lemma 6

[3] Let G be a planar graph that has a planar straight-line drawing $\varGamma$ with a set S of vertices on the x-axis. For any assignment of y-coordinates to the vertices in S, there exists a planar straight-line drawing of G such that each vertex in S has the same x-coordinate as in $\varGamma$ and has the assigned y-coordinate.

Lemma 7

[3] Let G be a planar graph, S be a free collinear set, and $<_S$ be the total order associated with S. Consider any assignment of x- and y-coordinates to the vertices in S such that the assigned x-coordinates are distinct and the order of the vertices in S by increasing or decreasing x-coordinates is $<_S$. There exists a planar straight-line drawing of G such that each vertex in S has the assigned x- and y-coordinates.

Lemma 7 and the fact that planar graphs of treewidth at most 3 have free collinear sets with linear size, established in Theorem 1, imply the following.

Corollary 1

Every set of at most $\lceil \frac{n-3}{8}\rceil$ points in the plane is a universal point subset for all n-vertex plane graphs of treewidth at most three.

As noted in [3, 20], Lemmas 6 and 7 imply that every straight-line drawing of a planar graph G with a free collinear set of size x can be untangled while keeping $\sqrt{x}$ vertices fixed. Together with Theorem 1 this implies the following.

Corollary 2

Any straight-line drawing of an n-vertex planar graph of treewidth at most three can be untangled while keeping at least $\sqrt{\lceil (n-3)/8 \rceil }$ vertices fixed.

Finally, Lemma 6 implies that every collinear set is a column planar set. That and our three main results imply our final corollary.

Corollary 3

Triconnected cubic planar graphs and planar graphs of treewidth at most three have column planar sets of linear size. Further, planar graphs of treewidth at least k have column planar sets of size $\varOmega (k^2)$.

7 Conclusions

We studied the problems of determining the maximum cardinality of collinear sets and free collinear sets in planar graphs; it would be interesting to close the gap between the best bounds of $\varOmega (n^{0.5})$ and $O(n^{0.986})$ known for these problems.

We proved that triconnected cubic plane graphs have collinear sets with linear size. Generalizing the bound to subcubic plane graphs seems like a plausible goal.

We proved that plane graphs with treewidth at most 3 have free collinear sets with linear size. In order to do that, we proved that every collinear set is free in a plane 3-tree, which brings us to a question posed in [20]: is every collinear set free, and if not, how close are the sizes of these two sets in a planar graph?

Finally, the maximum number of collinear vertices in any planar straight-line drawing of a plane 3-tree can be determined by dynamic programming. An implementation of the algorithm has shown that, for $m\le 50$ and for every plane 3-tree G with m internal vertices, the maximum number of collinear internal vertices in any planar straight-line drawing of G is at least $\lceil \frac{m+2}{3} \rceil$ (this bound is the best possible for every $m\le 50$). Is this the case for every $m\ge 1$?