Drawing Graphs on Few Lines and Few Planes

It is well known that any graph admits a straight-line drawing in 3-space. Suppose that we are allowed to draw edges only on a limited number of planes. How many planes do we need for a given graph G? For example, \(K_6\) needs four planes; see Fig. 1. Note that this question is different from the well-known concept of a book embedding where all vertices lie on one line (the spine) and edges lie on a limited number of adjacent half-planes (the pages). In contrast, we put no restriction on the mutual position of planes, the vertices can be located in the planes arbitrarily, and the edges must be straight-line.

In a weaker setting, we require only the vertices to be located on a limited number of planes (or lines). For example, the graph in Fig. 2 can be drawn in 2D such that its vertices are contained in three lines; we conjecture that it is the smallest planar graph that needs more than two lines even in 3D. This version of our problem is related to the well-studied problem of drawing a graph straight-line in a 3D grid of bounded volume [16, 37]: If a graph can be drawn with all vertices on a grid of volume v, then \(v^{1/3}\) planes and \(v^{2/3}\) lines suffice. We now formalize the problem.

Definition 1

Let \(1 \le l < d\), and let G be a graph. We define the l-dimensional affine cover number of G in \(\mathbb {R}^d\), denoted by \(\rho ^l_d(G)\), as the minimum number of l-dimensional planes in \(\mathbb R^d\) such that G has a drawing that is contained in the union of these planes. We define \(\pi ^l_d(G)\), the weak l-dimensional affine cover number of G in \(\mathbb {R}^d\), similarly to \(\rho ^l_d(G)\), but under the weaker restriction that the vertices (and not necessarily the edges) of G are contained in the union of the planes. Finally, the parallel affine cover number, \(\bar{\pi }^l_d(G)\), is a restricted version of \(\pi ^l_d(G)\), in which we insist that the planes are parallel. We consider only straight-line and crossing-free drawings. Note: \(\rho ^l_d(G)\), \(\pi ^l_d(G)\), and \(\bar{\pi }^l_d(G)\) are only undefined when \(d=2\) and G is non-planar.

Clearly, for any combination of l and d, it holds that \(\pi ^l_d(G)\le \bar{\pi }^l_d(G)\) and \(\pi ^l_d(G)\le \rho ^l_d(G)\). Larger values of l and d give us more freedom for drawing graphs and, therefore, smaller \(\pi \)- and \(\rho \)-values. Formally, for any graph G, if \(l'\le l\) and \(d'\le d\) then \(\pi ^l_d(G)\le \pi ^{l'}_{d'}(G)\), \(\rho ^l_d(G)\le \rho ^{l'}_{d'}(G)\), and \(\bar{\pi }^l_d(G)\le \bar{\pi }^{l'}_{d'}(G)\). But in most cases this freedom is not essential. For example, it suffices to consider \(l\le 2\) because otherwise \(\rho ^l_d(G)=1\). More interestingly, we can actually focus on \(d\le 3\) because every graph can be drawn in 3-space as effectively as in high dimensional spaces, i.e., for any integers \(1 \le l \le d\), \(d\ge 3\), and for any graph G, it holds that \(\pi ^l_d(G)=\pi ^l_3(G)\), \(\bar{\pi }^l_d(G)=\bar{\pi }^l_3(G)\), and \(\rho ^l_d(G)=\rho ^l_3(G)\). We prove this important fact in Appendix A. Thus, our task is to investigate the cases \(1\le l<d\le 3\). We call \(\rho ^1_2(G)\) and \(\rho ^1_3(G)\) the line cover numbers in 2D and 3D, \(\rho ^2_3(G)\) the plane cover number, and analogously for the weak versions.

Related Work. We have already briefly mentioned 3D graph drawing on the grid, which has been surveyed by Wood [37] and by Dujmović and Whitesides [16]. For example, Dujmović [13], improving on a result of Di Battista et al. [4], showed that any planar graph can be drawn into a 3D-grid of volume \(O(n \log n)\). It is well-known that, in 2D, any planar graph admits a plane straight-line drawing on an \(O(n) \times O(n)\) grid [20, 33] and that the nested-triangles graph \(T_k = K_3 \times P_k\) (see Fig. 4) with 3k vertices needs \(\varOmega (k^2)\) area [20].

An interesting variant of our problem is to study drawings whose edge sets are represented (or covered) by as few objects as possible. The type of objects that have been used are straight-line segments [14, 17] and circular arcs [34]. The idea behind this objective is to keep the visual complexity of a drawing low for the observer. For example, Schulz [34] showed how to draw the dodecahedron by using 10 arcs, which is optimal.

Our Contribution. Our research goes into three directions.

First, we show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes such as graphs of bounded degree or subclasses of planar graphs. The most natural graph families to start with are the complete graphs and the complete bipartite graphs. Most versions of the affine cover numbers of these graphs can be determined easily. Two cases are much more subtle: We determine \(\rho ^2_3(K_n)\) and \(\rho ^1_3(K_{n,n})\) only asymptotically, up to a factor of 2 (see Theorem 12 and Example 10). Some efforts are made to compute the exact values of \(\rho ^2_3(K_n)\) for small n (see Theorem 15). As another result in this direction, we prove that \(\rho ^1_3(G)>n/5\) for almost all cubic graphs on n vertices (Theorem 9(b)).

Second, we relate the affine cover numbers to standard combinatorial characteristics of graphs and to parameters that have been studied in graph drawing. In Sect. 2.1, we characterize \(\pi ^1_3(G)\) and \(\pi ^2_3(G)\) in terms of the linear vertex arboricity and the vertex thickness, respectively. This characterization implies that both \(\pi ^1_3(G)\) and \(\pi ^2_3(G)\) are linearly related to the chromatic number of the graph G. Along the way, we refine a result of Pach et al. [28] concerning the volume of 3D grid drawings (Theorem 2). We also prove that any graph G has balanced separators of size at most \(\rho ^1_3(G)\) and conclude from this that \(\rho ^1_3(G)\ge {{\mathrm{tw}}}(G)/3\), where \({{\mathrm{tw}}}(G)\) denotes the treewidth of G (Theorem 9). In Sect. 3.2, we analyze the relationship between \(\rho ^1_2(G)\) and the segment number \({{\mathrm{segm}}}(G)\) of a graph, which was introduced by Dujmović et al. [14]. We prove that \({{\mathrm{segm}}}(G)=O(\rho ^1_2(G)^2)\) for any connected G and show that this bound is optimal (see Theorem 23 and Example 22).

Third, we pay special attention to planar graphs (Sect. 3). Among other results, we show examples of planar graphs with a large gap between the parameters \(\rho ^1_3(G)\) and \(\rho ^1_2(G)\) (see Theorem 24).

We also investigate the parallel affine cover numbers \(\bar{\pi }^1_2\) and \(\bar{\pi }^1_3\). Observe that for any graph G, \(\bar{\pi }^1_3(G)\) equals the improper track number of G, which was introduced by Dujmović et al. [15].

Due to lack of space, our results for the parallel affine cover numbers (along with a survey of known related results) appear in Appendix B. We defer some other proofs to Appendices C and D and list some open problems in Appendix E.

Remark on the Computational Complexity. In a follow-up paper [9], we investigate the computational complexity of computing the \(\rho \)- and \(\pi \)-numbers. We argue that it is NP-hard to decide whether a given graph has a \(\pi ^1_3\)- or \(\pi ^2_3\)-value of 2 and that both values are even hard to approximate. This result is based on Theorems 2 and 4 and Corollaries 3 and 5 in the present paper. While the graphs with \(\rho _3^2\)-value 1 are exactly the planar graphs (and hence, can be recognized in linear time), it turns out that recognizing graphs with a \(\rho _3^2\)-value of 2 is already NP-hard. In contrast to this, the problems of deciding whether \(\rho ^1_3(G)\le k\) or \(\rho ^1_2(G)\le k\) are solvable in polynomial time for any fixed k. However, the versions of these problems with k being part of the input are complete for the complexity class \(\exists \mathbb {R}\) which is based on the existential theory of the reals and that plays an important role in computational geometry [32].

Notation. For a graph \(G=(V,E)\), we use n and m to denote the numbers of vertices and edges of G, respectively. Let \(\varDelta (G)=\max _{v \in V} \deg (v)\) denote the maximum degree of G. Furthermore, we will use the standard notation \(\chi (G)\) for the chromatic number, \({{\mathrm{tw}}}(G)\) for the treewidth, and \({{\mathrm{diam}}}(G)\) for the diameter of G. The Cartesian product of graphs G and H is denoted by \(G\times H\).

2.1 Placing Vertices on Few Lines or Planes (\(\pi ^{1}_{3}\) and \(\pi ^{2}_{3}\))

A linear forest is a forest whose connected components are paths. The linear vertex arboricity \({{\mathrm{lva}}}(G)\) of a graph G equals the smallest size r of a partition \(V(G)=V_1\cup \dots \cup V_r\) such that every \(V_i\) induces a linear forest. This notion, which is an induced version of the fruitful concept of linear arboricity (see Remark 8 below), appears very relevant to our topic. The following result is based on a construction of Pach et al. [28]; see Appendix C for the proof.

Theorem 2

For any graph G, it holds that \(\pi ^1_3(G)={{\mathrm{lva}}}(G)\). Moreover, any graph G can be drawn with vertices on r lines in the 3D integer grid of size \(r\times 4rn\times 4r^2n\), where \(r={{\mathrm{lva}}}(G)\).

Corollary 3

\(\chi (G)/2 \le \pi ^1_3(G) \le \chi (G)\).

Corollary 3 readily implies that \(\pi ^1_3(G) \le \varDelta (G)+1\) [7]. This can be considerably improved using a relationship between the linear vertex arboricity and the maximum degree that is established by Matsumoto [27]. Matsumoto’s result implies that \(\pi ^1_3(G) \le \varDelta (G)/2+1\) for any connected graph G. Moreover, if \(\varDelta (G)=2d\), then \(\pi ^1_3(G)=d+1\) if and only if G is a cycle or the complete graph \(K_{2d+1}\).

We now turn to the weak plane cover numbers. The vertex thickness \({{\mathrm{vt}}}(G)\) of a graph G is the smallest size r of a partition \(V(G)=V_1\cup \dots \cup V_r\) such that \(G[V_1],\dots ,G[V_r]\) are all planar. We prove the following theorem in Appendix C.

Theorem 4

For any graph G, it holds that \(\pi ^2_3(G)=\bar{\pi }^2_3(G)={{\mathrm{vt}}}(G)\) and that G can be drawn such that all vertices lie on a 3D integer grid of size \({{\mathrm{vt}}}(G)\times O(m^2)\times O(m^2)\), where m is the number of edges of G. Note that this drawing occupies \({{\mathrm{vt}}}(G)\) planes.

Corollary 5

\(\chi (G)/4 \le \pi ^2_3(G) \le \chi (G)\).

Example 6.

1. (a)

   \(\pi ^1_3(K_n)=\lceil n/2\rceil \).

2. (b)

   \(\pi ^1_3(K_{p,q})=2\) for any \(1 \le p \le q\); except for \(\pi ^1_3(K_{1,1})=\pi ^1_3(K_{1,2})=1\).

3. (c)

   \(\pi ^2_3(K_n)=\lceil n/4\rceil \); therefore, \(\pi ^2_3(G)\le \lceil n/4\rceil \) for every graph G.

2.2 Placing Edges on Few Lines or Planes (\(\rho ^1_3\) and \(\rho ^2_3\))

Clearly, \(\varDelta (G)/2\le \rho ^1_3(G)\le m\) for any graph G. Call a vertex v of a graph G essential if \(\deg v\ge 3\) or if v belongs to a \(K_3\) subgraph of G. Denote the number of essential vertices in G by \({{\mathrm{es}}}(G)\).

Lemma 7.

1. (a)

   \(\rho ^1_3(G) > (1+\sqrt{1+8{{\mathrm{es}}}(G)})/2\).

2. (b)

   \(\rho ^1_3(G)>\sqrt{m^2/n-m}\) for any graph G with \(m\ge n\ge 1\).

Proof.

1. (a)

   In any drawing of a graph G, any essential vertex is shared by two edges not lying on the same line. Therefore, each such vertex is an intersection point of at least two lines, which implies that \({{\mathrm{es}}}(G)\le \left( {\begin{array}{c}\rho ^1_3(G)\\ 2\end{array}}\right) \). Hence, \(\rho ^1_3(G) \ge \big (1+\sqrt{1+8{{\mathrm{es}}}(G)}\,\big )/2>\sqrt{2{{\mathrm{es}}}(G)}\).

2. (b)

   Taking into account multiplicity of intersection points (that is, each vertex v requires at least \(\lceil \deg v/2\rceil (\lceil \deg v/2\rceil -1)/2\) intersecting line pairs), we obtain

   $$\begin{aligned} \left( {\begin{array}{c}\rho ^1_3(G)\\ 2\end{array}}\right)\ge & {} \frac{1}{2} \sum _{v\in V(G)} \left\lceil \frac{\deg v}{2} \right\rceil \left( \left\lceil \frac{\deg v}{2}\right\rceil -1\right) \ge \sum \frac{\deg v(\deg v-2)}{8} = \\= & {} \frac{1}{8}\sum (\deg v)^2-\frac{1}{4}\sum \deg v\ge \frac{1}{8n}\left( \sum \deg v\right) ^2-\frac{1}{4} 2m =\frac{m^2}{2n}-\frac{m}{2}. \end{aligned}$$

   The last inequality follows by the inequality between arithmetic and quadratic means. Hence, \(\rho ^1_3(G) > \sqrt{m^2/n-m}\).    \(\square \)

Part (a) of Lemma 7 implies that \(\rho ^1_3(G)>\sqrt{2n}\) if a graph G has no vertices of degree 1 and 2, while Part (b) yields \(\rho ^1_3(G)>\sqrt{m/2}\) for all such G. Note that a disjoint union of k cycles can have no essential vertices, but each cycle will need 3 intersection points of lines, i.e., such a graph has \(\rho ^1_3 \in \varOmega (\sqrt{k})\). Thus, \(\rho ^1_3\) cannot be bounded from above by a function of essential vertices.

Remark 8

The linear arboricity \({{\mathrm{la}}}(G)\) of a graph G is the minimum number of linear forests which partition the edge set of G; see [24]. Clearly, we have \(\rho ^1_3(G)\ge {{\mathrm{la}}}(G)\). There is no function of \({{\mathrm{la}}}(G)\) that is an upper bound for \(\rho ^1_3(G)\). Indeed, let G be an arbitrary cubic graph. Akiyama et al. [2] showed that \({{\mathrm{la}}}(G)=2\). On the other hand, any vertex of G is essential, so \(\rho ^1_3(G)>\sqrt{2n}\) by Lemma 7(a). Theorem 9 below shows an even larger gap.

We now prove a general lower bound for \(\rho ^1_3(G)\) in terms of the treewidth of G. Note for comparison that \(\pi ^1_3(G) \le \chi (G) \le {{\mathrm{tw}}}(G)+1\) (the last inequality holds because the graphs of treewidth at most k are exactly partial k-trees and the construction of a k-tree easily implies that it is \(k+1\)-vertex-chromatic). The relationship between \(\rho ^1_3(G)\) and \({{\mathrm{tw}}}(G)\) follows from the fact that graphs with low parameter \(\rho ^1_3(G)\) have small separators. This fact is interesting by itself and has yet another consequence: Graphs with bounded vertex degree can have linearly large value of \(\rho ^1_3(G)\) (hence, the factor of n in the trivial bound \(\rho ^1_3(G)\le m\le \frac{1}{2}\,n\,\varDelta (G)\) is best possible).

We need the following definitions. Let \(W\subseteq V(G)\). A set of vertices \(S\subset V(G)\) is a balanced \(W\)-separator of the graph G if \(|W\cap C|\le |W|/2\) for every connected component C of \(G{\setminus }S\). Moreover, S is a strongly balanced \(W\)-separator if there is a partition \(W{\setminus } S=W_1\cup W_2\) such that \(|W_i|\le |W|/2\) for both \(i=1,2\) and there is no path between \(W_1\) and \(W_2\) avoiding S. Let \({{\mathrm{sep}}}_W(G)\) (resp. \({{\mathrm{sep}}}^*_W(G)\)) denote the minimum k such that G has a (resp. strongly) balanced \(W\)-separator S with \(|S|=k\). Furthermore, let \({{\mathrm{sep}}}(G)={{\mathrm{sep}}}_{V(G)}(G)\) and \({{\mathrm{sep}}}^*(G)={{\mathrm{sep}}}^*_{V(G)}(G)\). Note that \({{\mathrm{sep}}}_W(G)\le {{\mathrm{sep}}}^*_W(G)\) for any W and, in particular, \({{\mathrm{sep}}}(G)\le {{\mathrm{sep}}}^*(G)\).

It is known [19, Theorem 11.17] that \({{\mathrm{sep}}}_W(G)\le {{\mathrm{tw}}}(G)+1\) for every \(W\subseteq V(G)\). On the other hand, if \({{\mathrm{sep}}}_W(G)\le k\) for all W with \(|W|=2k+1\), then \({{\mathrm{tw}}}(G)\le 3k\).

The bisection width \({{\mathrm{bw}}}(G)\) of a graph G is the minimum possible number of edges between two sets of vertices \(W_1\) and \(W_2\) with \(|W_1| = \lceil n/2 \rceil \) and \(|W_2| = \lfloor n/2 \rfloor \) partitioning V(G). Note that \({{\mathrm{sep}}}^*(G)\le {{\mathrm{bw}}}(G)+1\).

Theorem 9.

1. (a)

   \(\rho ^1_3(G)\ge {{\mathrm{bw}}}(G)\).

2. (b)

   \(\rho ^1_3(G)>n/5\) for almost all cubic graphs with n vertices.

3. (c)

   \(\rho ^1_3(G)\ge {{\mathrm{sep}}}^*_W(G)\) for every \(W\subseteq V(G)\).

4. (d)

   \(\rho ^1_3(G) \ge {{\mathrm{tw}}}(G)/3\).

Proof.

1. (a)

   Fix a drawing of the graph G on \(r=\rho ^1_3(G)\) lines in \(\mathbb R^3\). Choose a plane L that is not parallel to any of the at most \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) lines passing through two vertices of the drawing. Let us move L along the orthogonal direction until it separates the vertex set of G into two almost equal parts \(W_1\) and \(W_2\). The plane L can intersect at most r edges of G, which implies that \({{\mathrm{bw}}}(G)\le r\).

2. (b)

   follows from Part (a) and the fact that a random cubic graph on n vertices has bisection width at least n / 4.95 with probability \(1-o(1)\) (Kostochka and Melnikov [25]).

3. (c)

   Given \(W\subseteq V(G)\), we have to prove that \({{\mathrm{sep}}}^*_W(G)\le \rho ^1_3(G)\). Choose a plane L as in the proof of Part (a) and move it until it separates W into two equal parts \(W'_1\) and \(W'_2\); if |W| is odd, then L should contain one vertex w of W. If |W| is even, we can ensure that L does not contain any vertex of G. We now construct a set S as follows. If L contains a vertex \(w\in W\), i.e., |W| is odd, we put w in S. Let E be the set of those edges which are intersected by L but are not incident to the vertex w (if it exists). Note that \(|E|<r\) if |W| is odd and \(|E|\le r\) if |W| is even. Each of the edges in E contributes one of its incident vertices into S. Note that \(|S|\le r\). Set \(W_1=W'_1{\setminus }S\) and \(W_2=W'_2{\setminus } S\) and note that there is no edge between these sets of vertices. Thus, S is a strongly balanced \(W\)-separator.

4. (d)

   follows from (c) by the relationship between treewidth and balanced separators.     \(\square \)

On the other hand, note that \(\rho ^1_3(G)\) cannot be bounded from above by any function of \({{\mathrm{tw}}}(G)\). Indeed, by Lemma 7(a) we have \(\rho ^1_3(T)=\varOmega (\sqrt{n})\) for every caterpillar T with linearly many vertices of degree 3. The best possible relation in this direction is \(\rho ^1_3(G) \le m < n {{\mathrm{tw}}}(G)\). The factor n cannot be improved here (take \(G=K_n\)).

Example 10.

1. (a)

   \(\rho ^1_3(K_n)=\left( {\begin{array}{c}n\\ 2\end{array}}\right) \) for any \(n\ge 2\).

2. (b)

   \(pq/2 \le \rho ^1_3(K_{p,q}) \le pq\) for any \(1 \le p \le q\).

We now turn to the plane cover number.

Example 11

For any integers \(1 \le p \le q\), it holds that \(\rho ^2_3(K_{p,q}) = \lceil p/2 \rceil \).

Determining the parameter \(\rho ^2_3(G)\) for complete graphs \(G=K_n\) is a much more subtle issue. We are able to determine the asymptotics of \(\rho ^2_3(K_n)\) up to a factor of 2.

By a combinatorial cover of a graph G we mean a set of subgraphs \(\{G_i\}\) such that every edge of G belongs to \(G_i\) for some i. A geometric cover of a crossing-free drawing \(d :V(K_n)\rightarrow \mathbb R^3\) of a complete graph \(K_n\) is a set \(\mathcal L\) of planes in \(\mathbb R^3\) so that for each pair of vertices \(v_i, v_j \in V(K_n)\) there is a plane \(\ell \in \mathcal L\) containing both points \(d(v_i)\) and \(d(v_j)\). This geometric cover \(\mathcal L\) induces a combinatorial cover \(\mathcal K_{\mathcal L} = \{G_\ell \mid \ell \in \mathcal L\}\) of the graph \(K_n\), where \(G_\ell \) is the subgraph of \(K_n\) induced by the set \(d^{-1}(\ell )\). Note that each \(G_\ell \) is a \(K_s\) subgraph with \(s\le 4\) (because \(K_5\) is not planar).

Let \(c(K_n,K_s)\) denote the minimum size of a combinatorial cover of \(K_n\) by \(K_s\) subgraphs (\(c(K_n,K_s)=0\) if \(s>n\)). The asymptotics of the numbers \(c(K_n,K_s)\) for \(s=3,4\) can be determined via the results about Steiner systems by Kirkman and Hanani [5, 23]. This yields the following bounds for \(\rho ^2_3(K_n)\) (see Appendix C).

Theorem 12

For all \(n\ge 3\),

Note that we cannot always realize a combinatorial cover of \(K_n\) by copies of \(K_4\) geometrically. For example, \(c(K_6,K_4)=3 < 4=\rho ^2_3(K_6)\) (see Theorem 15).

In order to determine \(\rho ^2_3(K_n)\) for particular values of n, we need some properties of geometric and combinatorial covers of \(K_n\).

Lemma 13

Let \(d :V(K_n)\rightarrow \mathbb R^3\) be a crossing-free drawing of \(K_n\) and \(\mathcal L\) a geometric cover of d. For each 4-vertex graph \(G_\ell \in \mathcal K_{\mathcal L}\), the set \(d(G_\ell )\) not only belongs to a plane \(\ell \), but also defines a triangle with an additional vertex in its interior.

Lemma 14

Let \(d :V(K_n)\rightarrow \mathbb R^3\) be a crossing-free drawing of \(K_n\) and \(\mathcal L\) a geometric cover of d. No two different 4-vertex graphs \(G_\ell ,G_{\ell '}\in \mathcal K_{\mathcal L}\) can have three common vertices.

Theorem 15

For \(n \le 9\), the value of \(\rho ^2_3(K_n)\) is bounded by the numbers in Table 1.

Proof

Here, we show only the bounds for \(n=6\). For the remaining proofs, see Appendix C. Figure 1 shows that \(\rho ^2_3(K_6)\le 4\). Now we show that \(\rho ^2_3(K_6)\ge 4\). Assume that \(\rho ^2_3(K_6)<4\). Consider a combinatorial cover \(\mathcal K_{\mathcal L}\) of \(K_6\) by its complete planar subgraphs corresponding to a geometric cover \(\mathcal L\) of its drawing by 3 planes. Graph \(K_6\) has 15 edges, so to cover it by complete planar graphs we have to use at least two copies of \(K_4\) and, additionally, a copy of \(K_k\) for \(3 \le k \le 4\). But, since each two copies of \(K_4\) in \(K_6\) have a common edge (and by Lemma 14 this edge is unique), the cover \(\mathcal K_{\mathcal L}\) consists of three copies of \(K_4\). Denote these copies by \(K_4^1\), \(K_4^2\), and \(K_4^3\). By Lemma 13, for each i, \(d(K_4^i)\) is a triangle with an additional vertex \(d(v_i)\) in its interior. Let \(V_0=\{v_1,v_2,v_3\}\). By the Krein–Milman theorem [26, 36], the convex hull \({{\mathrm{Conv}}}(d(K_6))\) is the convex hull \({{\mathrm{Conv}}}(d(V(K_6)){\setminus }d(V_0))\). If all the vertices \(v_i\) are mutually distinct then the set \(d(V(K_6)){\setminus } d(V_0)\) is a triangle, so the drawing d is planar, a contradiction. Hence, \(v_i=v_j\) for some \(i\ne j\). Let k be the third index that is distinct from both i and j. Since graphs \(K_4^i\) and \(K_4^j\) have exactly one common edge, this is an edge \((v_i,v)\) for some vertex v of \(K_6\) (see Fig. 1 with \(u_4\) for \(v_i\) and \(u_1\) for v). Let \(V(K_4^i)=\{v,v_i,v_i^1,v_i^2\}\) and \(V(K_4^j)=\{v,v_j,v_j^1,v_j^2\}\). Since the union \(K_4^1\cup K_4^2\cup K_4^3\) covers all edges of \(K_6\), all edges \((v_i^1,v_j^1)\), \((v_i^1,v_j^2)\), \((v_i^2,v_j^1)\), and \((v_i^2,v_j^2)\) belong to \(K_4^k\). Thus \(V(K_4^k)=\{v_i^1,v_i^2,v_j^1,v_j^2\}\). But vertices \(v_i^1\), \(v_i^2\), \(v_j^1\), and \(v_j^2\) are in convex position (see Fig. 1), a contradiction to Lemma 13.     \(\square \)

3.1 Placing Vertices on Few Lines (\(\pi ^1_2\) and \(\pi ^1_3\))

Combining Corollary 3 with the 4-color theorem yields \(\pi ^1_3(G) \le 4\) for planar graphs. Given that outerplanar graphs are 3-colorable (they are partial 2-trees), we obtain \(\pi ^1_3(G) \le 3\) for these graphs. These bounds can be improved using the equality \(\pi ^1_3(G)={{\mathrm{lva}}}(G)\) of Theorem 2 and known results on the linear vertex arboricity:

1. (a)

   For any planar graph G, it holds that \(\pi ^1_3(G) \le 3\) [21, 29].

2. (b)

   There is a planar graph G with \(\pi ^1_3(G)=3\) [11].

3. (c)

   For any outerplanar graph G, \(\pi ^1_3(G) \le 2\) [1, 6, 35].

According to Chen and He [12], the upper bound \({{\mathrm{lva}}}(G)\le 3\) for planar graphs by Poh [29] is constructive and yields a polynomial-time algorithm for partitioning the vertex set of a given planar graph into three parts, each inducing a linear forest. By combining this with the construction given in Theorem 2, we obtain a polynomial-time algorithm that draws a given planar graph such that the vertex set “sits” on three lines.

The example of Chartrand and Kronk [11] is a 21-vertex planar graph whose vertex arboricity is 3, which means that the vertex set of this graph cannot even be split into two parts both inducing (not necessarily linear) forests. Raspaud and Wang [30] showed that all 20-vertex planar graphs have vertex arboricity at most 2. We now observe that a smaller example of a planar graph attaining the extremal value \(\pi ^1_3(G)=3\) can be found by examining the linear vertex arboricity.

Example 16

The planar 9-vertex graph G in Fig. 2 has \(\pi ^1_3(G)={{\mathrm{lva}}}(G)=3\). (See a proof in Appendix D.)

Now we show lower bounds for the parameter \(\pi ^1_2(G)\).

Recall that the circumference of a graph G, denoted by c(G), is the length of a longest cycle in G. For a planar graph G, let \(\bar{v}(G)\) denote the maximum k such that G has a straight-line plane drawing with k collinear vertices.

Lemma 17

Let G be a planar graph. Then \(\pi ^1_2(G)\ge n/\bar{v}(G)\). If G is a triangulation then \(\pi ^1_2(G)\ge (2n-4)/c(G^*)\).

Proof

Since the first claim is obvious, we prove only the second. Let \(\gamma (G)\) denote the minimum number of cycles in the dual graph \(G^*\) sharing a common vertex and covering every vertex of \(G^*\) at least twice. Note that, as G is a triangulation, \(\gamma (G)\ge (4n-8)/c(G^*)\), where \(2n-4\) is the number of vertices in \(G^*\) (as a consequence of Euler’s formula). We now show \(\pi ^1_2(G)\ge \gamma (G)/2\), which implies the claimed result.

Given a drawing realizing \(\pi ^1_2(G)\) with line set \(\mathcal L\), for every line \(\ell \in \mathcal L\), draw two parallel lines \(\ell ',\ell ''\) sufficiently close to \(\ell \) such that they together intersect the interiors of all faces touched by \(\ell \) and do not go through any vertex of the drawing. Note that \(\ell '\) and \(\ell ''\) cross boundaries of faces only via inner points of edges. Each such crossing corresponds to a transition from one vertex to another along an edge in the dual graph \(G^*\). Since all the faces of G are triangles, each of them is visited by each of \(\ell '\) and \(\ell ''\) at most once. Therefore, the faces crossed along \(\ell '\) and the faces crossed along \(\ell ''\), among them the outer face of G, each form a cycle in \(G^*\). It remains to note that every face f of the graph G is crossed at least twice, because f is intersected by at least two different lines from \(\mathcal L\) and each of these two lines has a parallel copy that crosses f.     \(\square \)

An infinite family of triangulations G with \(\bar{v}(G)\le n^{0.99}\) is constructed in [31]. By the first part Lemma 17 this implies that there are infinitely many triangulations G with \(\pi ^1_2(G)\ge n^{0.01}\). The second part of Lemma 17 along with an estimate of Grünbaum and Walther [22] (that was used also in [31]) yields a stronger result.

Theorem 18

There are infinitely many triangulations G with \(\varDelta (G)\le 12\) and \(\pi ^1_2(G)\ge n^{0.01}\).

Proof

The shortness exponent \(\sigma _{\mathcal G}\) of a class \(\mathcal G\) of graphs is the infimum of the set of the reals \(\liminf _{i\rightarrow \infty }{\log c(H_i)}/{\log |V(H_i)|}\) for all sequences of \(H_i\in \mathcal G\) such that \(|V(H_i)|<|V(H_{i+1})|\). Thus, for each \(\epsilon >0\), there are infinitely many graphs \(H\in \mathcal G\) with \(c(H)<|V(H)|^{\sigma _{\mathcal G}+\epsilon }\). The dual graphs of triangulations with maximum vertex degree at most 12 are exactly the cubic 3-connected planar graphs with each face incident to at most 12 edges (this parameter is well defined by the Whitney theorem). Let \(\sigma \) denote the shortness exponent for this class of graphs. It is known [22] that \(\sigma \le \frac{\log 26}{\log 27}=0.988\ldots \). The theorem follows from this bound by the second part of Lemma 17.     \(\square \)

Problem 19

Does \(\pi ^1_2(G)=o(n)\) hold for all planar graphs G?

A track drawing [18] of a graph is a plane drawing for which there are parallel lines, called tracks, such that every edge either lies on a track or its endpoints lie on two consecutive tracks. We call a graph track drawable if it has a track drawing. Let \({{\mathrm{tn}}}(G)\) be the minimum number of tracks of a track drawing of G. Note that \(\pi ^1_2(G)\le \bar{\pi }^1_2(G)\le {{\mathrm{tn}}}(G)\).

The following proposition is similar to a lemma of Bannister et al. [3, Lemma 1] who say it is implicit in the earlier work of Felsner et al. [18].

Theorem 20

(cf. [3, 18]). Let G be a track drawable graph. Then \(\pi ^1_2(G)\le 2\).

Proof

Consider a track drawing of G, which we now transform to a drawing on two intersecting lines. Put the tracks consecutively along a spiral so that they correspond to disjoint intervals on the half-lines as depicted on the right. Tracks whose indices are equal modulo 4 are placed on the same half-line; for more details see Fig. 8 in Appendix D on page 26. (Bannister et al. [3, Fig. 1] use three half-lines meeting in a point.)    \(\square \)

Observe that any tree is track drawable: two vertices are aligned on the same track iff they are at the same distance from an arbitrarily assigned root. Moreover, any outerplanar graph is track drawable [18]. This yields an improvement over the bound \(\pi ^1_3(G) \le 2\) for outerplanar graphs stated in the beginning of this section.

Corollary 21

For any outerplanar graph G, it holds that \(\pi ^1_2(G)\le 2\).

3.2 Placing Edges on Few Lines (\(\rho ^1_2\) and \(\rho ^1_3\))

The parameter \(\rho ^1_2(G)\) is related to two parameters introduced by Dujmović et al. [14]. They define a segment in a straight-line drawing of a graph G as an inclusion-maximal (connected) path of edges of G lying on a line. A slope is an inclusion-maximal set of parallel segments. The segment number (resp., slope number) of a planar graph G is the minimum possible number of segments (resp., slopes) in a straight-line drawing of G. We denote these parameters by \({{\mathrm{segm}}}(G)\) (resp., \({{\mathrm{slop}}}(G)\)). Note that \({{\mathrm{slop}}}(G)\le \rho ^1_2(G)\le {{\mathrm{segm}}}(G)\).

These parameters can be far away from each other. Figure 4 shows a graph with \({{\mathrm{slop}}}(G)=O(1)\) and \(\rho ^1_2(G)=\varOmega (n)\) (see the proof of Theorem 24). On the other hand, note that \(\rho ^1_2(mK_2)=1\) while \({{\mathrm{segm}}}(mK_2)=m\) where \(mK_2\) denotes the graph consisting of m isolated edges. The gap between \(\rho ^1_2(G)\) and \({{\mathrm{segm}}}(G)\) can be large even for connected graphs. It is not hard to see that \({{\mathrm{segm}}}(G)\) is bounded from below by half the number of odd degree vertices (see [14] for details). Therefore, if we take a caterpillar G with k vertices of degree 3 and \(k+2\) leaves, then \({{\mathrm{segm}}}(G)\ge n/2\), while \(\rho ^1_2(G)=O(\sqrt{n})\) because G can easily be drawn in a square grid of area O(n). Note that, for the same G, the gap between \({{\mathrm{slop}}}(G)\) and \(\rho ^1_2(G)\) is also large. Indeed, \({{\mathrm{slop}}}(G)=2\) while \(\rho ^1_2(G)>\sqrt{n-2}\) by Lemma 7(a).

It turns out that a large gap between \(\rho ^1_2(G)\) and \({{\mathrm{segm}}}(G)\) can be shown also for 3-connected planar graphs and even for triangulations.

Example 22

There are triangulations with \(\rho ^1_2(G)=O(\sqrt{n})\) and \({{\mathrm{segm}}}(G)=\varOmega (n)\).^{Footnote 1} Note that this gap is the best possible because any 3-connected graph G has minimum vertex degree 3 and, hence, \(\rho ^1_2(G)\ge \rho ^1_3(G)>\sqrt{2n}\) by Lemma 7(a). Consider the graph shown in Fig. 3. Its vertices are placed on the standard orthogonal grid and two slanted grids, which implies that at most \(O(\sqrt{n})\) lines are involved. The pattern can be completed to a triangulation by adding three vertices around it and connecting them to the vertices on the pattern boundary. Since the pattern boundary contains \(O(\sqrt{n})\) vertices, \(O(\sqrt{n})\) new lines suffice for this. Thus, we have \(\rho ^1_2(G)=O(\sqrt{n})\) for the resulting triangulation G. Note that the vertices drawn fat in Fig. 3 have degree 5, and there are linearly many of them. This implies that \({{\mathrm{segm}}}(G)=\varOmega (n)\).

Somewhat surprisingly, the parameter \({{\mathrm{segm}}}(G)\) can be bounded from above by a function of \(\rho ^1_2(G)\) for all connected graphs.

Theorem 23

For any connected planar graph G, \({{\mathrm{segm}}}(G)=O(\rho ^1_2(G)^2)\).

Note that \(\varDelta (G)/2 \le \rho ^1_3(G) \le \rho ^1_2(G) \le {{\mathrm{segm}}}(G) \le m\) for any planar graph G. For all inequalities here except the second one, we already know that the gap between the respective pair of parameters can be very large (by considering a caterpillar with linearly many degree 3 vertices and applying Lemma 7(a), by Example 22, and by considering the path graph \(P_n\), for which \({{\mathrm{segm}}}(P_n)=1\)). Part (b) of the following theorem shows a large gap also between the parameters \(\rho ^1_3(G)\) and \(\rho ^1_2(G)\), that is, some planar graphs can be drawn much more efficiently, with respect to the line cover number, in 3-space than in the plane.

Theorem 24.

1. (a)

   There are infinitely many planar graphs with constant maximum degree, constant treewidth, and linear \(\rho ^1_2\)-value.

2. (b)

   For infinitely many n there is a planar graph G on n vertices with \(\rho ^1_2(G)=\varOmega (n)\) and \(\rho ^1_3(G)=O(n^{2/3})\).

Proof Consider the nested-triangles graph \(T_k=C_3\times P_k\) shown in Fig. 4. To prove statements (a) and (b), it suffices to establish the following bounds:

1. (i)

   \(\rho ^1_2(T_k) \ge n/2\) and

2. (ii)

   \(\rho ^1_3(T_k)=O(n^{2/3})\).

To see the linear lower bound (i), note that \(T_k\) is 3-connected. Hence, Whitney’s theorem implies that, in any plane drawing of \(T_k\), there is a sequence of nested triangles of length at least k / 2. The sides of the triangles in this sequence must belong to pairwise different lines. Therefore, \(\rho ^1_2(T_k) \ge 3k/2=n/2\).

For the sublinear upper bound (ii), first consider the graph \(C_4\times P_k\). We build wireframe rectangular prisms that are stacks of \(O(\root 3 \of {n})\) squares each. These prisms are placed onto the base plane in an \(O(\root 3 \of {n}) \times O(\root 3 \of {n})\) grid; see Fig. 5. So far we can place the edges on the \(O(n^{2/3})\) lines of the 3D cubic grid of volume O(n). Next, we construct a path that traverses all squares by passing through the prisms from top to bottom (resp., vice versa) and connecting neighboring prims. We rotate and move some of the squares at the top (resp., bottom) of the prisms to be able to draw the edges between neighboring prisms according to this path. For this “bending” we need \(O(n^{2/3})\) additional lines. In Appendix D we provide a drawing; see Fig. 11 on page 30. The same approach works for the graph \(T_k = C_3\times P_k\). In addition to the standard 3D grid, here we need also its slanted, diagonal version (and, again, additional lines for bending in the cubic box of volume O(n)). The number of lines increases just by a constant factor.     \(\square \)

We are able to determine the exact values of \(\rho ^1_2(G)\) for complete bipartite graphs \(K_{p,q}\) that are planar.

Example 25

\(\rho ^1_2(K_{1,q})=\lceil m/2\rceil \) and \(\rho ^1_2(K_{2,q})=\lceil (3n-7)/2\rceil =\lceil (3m-2)/4\rceil \). See Appendix D for details.

Motivated by Example 25, we ask:

Problem 26

What is the smallest c such that \(\rho ^1_2(G)\le (c+o(1)) m\) for any planar graph G? Example 25 shows that \(c\ge 3/4\). Durocher and Mondal [17], improving on an earlier bound of Dujmović et al. [14], showed that \({{\mathrm{segm}}}(G)<\frac{7}{3}n\) for any planar graph G. This implies that \(c\le 7/9\).

For any binary tree T, it holds that \(\rho ^1_2(T)=O(\sqrt{n\log n})\). This follows from the known fact [8] that T has an orthogonal drawing on a grid of size \(O(\sqrt{n\log n}) \times O(\sqrt{n\log n})\). For complete binary trees lower and upper bounds are described in Example 37 in Appendix D.