Packing Trees into 1-Planar Graphs

Abstract

We introduce and study the 1-planar packing problem: Given k graphs with n vertices $G_1, \dots , G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$. We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with $n \ge 12$ vertices admits a 1-planar packing, while such a packing does not exist if $n \le 10$.

This work started at the Bertinoro Workshop on Graph Drawing 2019 and it is partially supported by: (i) MIUR grant 20174LF3T8, (ii) Dipartimento di Ingegneria - Università degli Studi di Perugia grants RICBASE2017WD and RICBA18WD, (iii) NFS grants CCF-1740858, CCF-1712119, DMS-1839274, DMS-1839307.

1 Introduction

In the graph packing problem we are given a collection of n-vertex graphs $G_1,\dots ,G_k$ and we are requested to find a graph G that contains the given graphs as edge-disjoint spanning subgraphs. Various settings of the problem can be defined depending on the type of graphs that have to be packed and on the restrictions put on the packing graph G. The most general case is when G is the complete graph on n vertices and there is no restriction on the input graphs. Sauer and Spencer [17] prove that any two graphs with at most $n-2$ edges can be packed into $K_n$; Woźniak and Wojda [19] give sufficient conditions for the existence of a packing of three graphs. The setting when G is $K_n$ and each $G_i$ is a tree ($i=1,2,\dots ,k$) has been intensively studied. Hedetniemi et al. [10] show that two non-star trees can always be packed into $K_n$. Notice that, the hypothesis that the trees are not stars is necessary for the existence of the packing because each vertex must have degree at least one in each tree, which is not possible if a vertex is adjacent to every other vertex as it is the case for a star. Wang and Sauer [18] give sufficient conditions for the existence of a packing of three trees into $K_n$, while Mahéo et al. [13] characterize the triples of trees that admit such a packing.

García et al. [7] consider the planar packing problem, that is the case when the graph G is required to be planar. They conjecture that the result of Hedetniemi et al. extends to this setting, i.e., that every pair of non-star trees can be packed into a planar graph. Notice that, when G is required to be planar, two is the maximum number of trees that can be packed (because three trees have more than $3n-6$ edges). García et al. prove their conjecture for some restricted cases, namely when one of the trees is a path and when the two trees are isomorphic. In a series of subsequent papers the conjecture has been proved true for other pairs of trees. Oda and Ota [14] prove it when one tree is a caterpillar or it is a spider of diameter four. Frati et al. [6] extend the last result to any spider, while Frati [5] considers the case when both trees have diameter four. Geyer et al. show that a planar packing always exists for a pair of binary trees [8] and for a pair of non-star trees [9], thus finally settling the conjecture.

In the present paper we initiate the study of the 1-planar packing problem, i.e., the problem of packing a set of graphs into a 1-planar graph. A 1-planar graph is a graph that can be drawn so that each edge has at most one crossing. 1-planar graphs have been introduced by Ringel [16] and have received increasing attention in the last years in the research area called beyond planarity (see, e.g., [4, 11]). Since any two non-star trees admit a planar packing, a natural question is whether we can pack more than two trees into a 1-planar graph. On the other hand, since each 1-planar graph has at most $4n-8$ edges edges [15], it is not possible to pack more than three trees into a 1-planar graph. Thus, our main question is whether any three trees with maximum vertex degree $n-3$ admit a 1-planar packing. The restriction to trees of degree at most $n-3$ is necessary because a vertex of degree larger than $n-3$ in one tree cannot have degree at least one in the other two trees. Our results can be listed as follows.

• We show that there exist triples of structurally simple trees that do not admit a 1-planar packing (Sect. 3). These triples consist of three caterpillars with at least 10 vertices and of two caterpillars and a path with 7 vertices.

• Motivated by the above results, we study triples consisting of two paths and a caterpillar (Sect. 4). We characterize the triples consisting of two paths and a 5-legged caterpillar (a caterpillar where each vertex of the spine has no leaves attached or it has at least five) that admit such a packing. We also characterize the triples that admit a 1-planar packing and that consist of two paths and a caterpillar whose spine has exactly two vertices.

• The packing technique of the results above is constructive and it gives rise to 1-plane graphs (i.e., 1-planar embedded graphs) with a linear number of crossings. This naturally raises the question about the number of edge crossings required by a 1-planar packing. We show that any three paths with at least six vertices can be packed into a 1-plane graph with seven edge crossings in total (Sect. 5). We also extend this technique to three cycles obtaining 1-plane graphs with fourteen crossings in total.

• We finally consider the 1-planar packing problem for quadruples of acyclic graphs (Sect. 6). Since, as already observed, four paths cannot be packed into a 1-planar graph, we consider three paths and a perfect matching. We show that when $n\ge 12$ such a quadruple admits a 1-planar packing and that when $n \le 10$ a 1-planar packing does not exist.

Preliminary definitions are given in Sect. 2 and open problems are listed in Sect. 7. Some proofs are sketched or removed and can be found in [3].

2 Preliminaries

Given a graph G and a vertex v of G, $\deg _{G}(v)$ denotes the vertex degree of v in G. Let $G_1, \dots , G_k$ be k graphs with n vertices; a packing of $G_1, \dots , G_k$ is an n-vertex graph G that has $G_1,\dots , G_k$ as edge-disjoint spanning subgraphs. We consider the case when G is a 1-planar graph; in this case we say that G is a 1-planar packing of $G_1,\dots , G_k$. If $G_1,\dots , G_k$ admit a (1-planar) packing G, we also say that $G_1,\dots , G_k$ can be packed into G. We mainly concentrate on the case when each $G_i$ is a tree ($1\le i\le k$). In this case (and generally when each $G_i$ is connected), we have restrictions on the values of k and n for which a packing exists.

Property 1

A 1-planar packing of k connected n-vertex graphs $G_1,\dots , G_k$ exists only if $k \le 3$ and $n \ge 2k$. Moreover, $\deg _{G_i}(v) \le n-k$ for each vertex v.

A caterpillar T is a tree such that removing all the leaves results in a path called the spine. A backbone of T is a path $v_0,v_1,v_2,\dots ,v_k,v_{k+1}$ of T where $v_1,v_2,\dots ,v_k$ is the spine of T and $v_0$ and $v_{k+1}$ are two leaves adjacent in T to $v_1$ and $v_k$, respectively. T is h-legged if every vertex of its spine has degree either 2 or at least $h+2$ in T.

3 Trees that Do Not Admit 1-Planar Packings

In this section we describe triples of trees that do not admit a 1-planar packing.

Theorem 1

For every $n \ge 10$, there exists a triple of caterpillars that does not admit a 1-planar packing.

Proof

The triple consists of three isomorphic caterpillars $T_1, T_2, T_3$ with $n \ge 10$ vertices. Each $T_i$ has a backbone of length 5 and $n-5$ leaves all adjacent to the middle vertex of the spine, which we call the center of $T_i$. First, notice that each $T_i$ satisfies Property 1, i.e., $\deg _{T_i}(v) \le n-3$. Namely, the vertex with largest degree in $T_i$ is its center, which has degree $n-3$. Let G be any packing of $T_1$, $T_2$, and $T_3$ and let $v_1$, $v_2$, and $v_3$ be the three vertices of G where the three centers of $T_1, T_2, T_3$, respectively, are mapped. The three vertices $v_1$, $v_2$, and $v_3$ must be distinct because otherwise they would have degree larger than $n-1$ in G, which is impossible. For each $v_i$ we have $\deg _{T_i}(v_i)=n-3$ and $\deg _{T_j}(v_i) \ge 1$, for $j \ne i$. This implies that $\deg _G(v_i)=n-1$ for each $v_i$. In other words, each $v_i$ is adjacent to all the other vertices of G. Thus, G contains $K_{3,n-3}$ as a subgraph. Since $n \ge 10$ and $K_{3,7}$ is not 1-planar [2], G is not 1-planar.   $\square$

Motivated by Theorem 1, we consider triples where one of the caterpillars is a path. Also in this case there exist triples that do not have a 1-planar packing.

Theorem 2

There exists a triple consisting of a path and two caterpillars with $n=7$ vertices that does not admit a 1-planar packing.

Proof

Let $T_i$ ($i=1,2$) be a caterpillar with a backbone of length four such that one of the two internal vertices has degree three and the other one has degree four. Let G be a packing of $T_1$, $T_2$ and a path P of 7 vertices. Let $v_1$, $v_2$, $v_3$, and $v_4$ be the four vertices of G where the internal vertices of the backbones of $T_1$ and $T_2$ are mapped to. We first observe that $v_1$, $v_2$, $v_3$, and $v_4$ must be distinct. Suppose, as a contradiction, that two of them coincide, say $v_1$ and $v_2$; then $\deg _{T_1}(v_1)+\deg _{T_2}(v_1)\ge 6$. On the other hand $\deg _{P}(v_1) \ge 1$, and therefore $\deg _G(v_1) \ge 7$, which is impossible (since G has only 7 vertices). Denote by $G_{1,2}$ the subgraph of G containing only the edges of $T_1$ and $T_2$. Two vertices among $v_1$, $v_2$, $v_3$, and $v_4$, say $v_1$ and $v_2$, have degree 5 in $G_{1,2}$, while the other two have degree 4 in $G_{1,2}$. Consider now the edges of P. Since the maximum vertex degree in a graph of seven vertices is six, $v_1$ and $v_2$ must be the end-vertices of P, while $v_3$ and $v_4$ are internal vertices. This means that they all have degree 6 in G. The vertices distinct from $v_1$, $v_2$, $v_3$, and $v_4$ have degree 2 in $G_{1,2}$ and degree 4 in G. Thus in G there are four vertices of degree 6 and three vertices of degree 4. The only graph of seven vertices with this degree distribution is the graph obtained from $K_7$ by deleting all the edges of a 3-cycle, which is known to be non-1-planar [12].   $\square$

4 1-Planar Packings of Two Paths and a Caterpillar

In this section we prove that a triple consisting of two paths $P_1$ and $P_2$ and a 5-legged caterpillar T with at least six vertices admits a 1-planar packing. Let P be the backbone of T and let $P'_1$ and $P'_2$ be two paths with the same length as P. We first show how to construct a 1-planar packing of P, $P'_1$ and $P'_2$. We then modify the computed packing to include the leaves of the caterpillar; this requires transforming some edges of $P'_1$ and $P'_2$ to sub-paths that pass through the added leaves. The resulting packing is a 1-planar packing of $P_1$, $P_2$ and T.

Let $\varGamma$ be a 1-planar drawing, possibly with parallel edges, and let e be an edge of $\varGamma$. If e has one crossing c, then each of the two parts in which e is divided by c are called sub-edges of e; if e has no crossing, e itself is called a sub-edge of e. Let v be a vertex of $\varGamma$; a cutting curve of v is a Jordan arc $\gamma$ such that: (i) $\gamma$ has v as an end-point; (ii) $\gamma$ intersects two edges $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$ (possibly $u_1=u_2$ and/or $v_1=v_2$); (iii) $\gamma$ does not intersect any other edge of $\varGamma$; (iv) $e_1$ and $e_2$ do not cross each other; (v) if $e_1$ and $e_2$ are parallel edges (i.e., $u_1=u_2$ and $v_1=v_2$), they have no crossings. The stub of $e_i$ with respect to $\gamma$ is the sub-edge of $e_i$ intersected by $\gamma$ ($i=1,2$). Given a cutting curve $\gamma$ of a vertex v, and an integer $k \ge 5$, a k-leaf addition operation adds k vertices $w_1, w_2, \dots , w_k$ and the edges $(v,w_1), (v,w_2), \dots , (v,w_k)$ to $\varGamma$ in such a way that: (i) the added vertices subdivide the stubs of both $e_1$ and $e_2$ with respect to $\gamma$; (ii) the subgraph induced by $u_1, u_2, v_1,v_2,w_1,w_2,\dots ,w_k$ has no multiple edges (see Fig. 1 for an example). In other words, a leaf addition adds a set of vertices adjacent to v and replaces the stubs of $e_1$ and $e_2$ with two edge-disjoint paths. This operation will be used to modify the 1-planar packing of P, $P'_1$ and $P'_2$ to include the leaves of the caterpillar. When the value of k is not relevant, a k-leaf addition will be simply called a leaf addition.

Fig. 1.

A 5-leaf addition operation. The cutting curve is shown with a zig-zag pattern on it.

Lemma 1

Let $\varGamma$ be a 1-planar drawing possibly with parallel edges, let v be a vertex of $\varGamma$ and let $\gamma$ be a cutting curve of v. It is possible to execute a k-leaf addition for every $k \ge 5$ in such a way that the resulting drawing is still 1-planar.

Fig. 2.

Gadgets for the proof of Lemma 1. (a)–(d) and (i) are used for parallel edges; (e)–(h) and (j) are used for non-parallel edges.

Proof

Denote by $e_1$ and $e_2$ the two edges crossed by $\gamma$. If one of them or both are crossed in $\varGamma$ replace their crossing points with dummy vertices. Let $e'_i$ be the stub of $e_i$ with respect to $\gamma$ (if $e_i$ is not crossed in $\varGamma$, $e'_i$ coincides with $e_i$). After the replacement of the crossings with the dummy vertices the two stubs $e'_1$ and $e'_2$ have no crossing. Since $\gamma$ does not cross any edge distinct from $e_1$ and $e_2$, the drawing $\varGamma '$ obtained by removing $e'_1$ and $e'_2$ has a face f whose boundary contains the vertex v and all the end-vertices of $e'_1$ and of $e'_2$ (there are at least two and at most four such vertices). The idea now is to insert into the face f, without creating any crossing, a gadget that realizes the k-leaf addition for the desired value of $k \ge 5$. A gadget has k vertices that will be added to $\varGamma$, a vertex that will be identified with v, and four vertices a, b, c, and d that will be identified with the end-vertices of $e'_1$ and $e'_2$. The four vertices a, b, c, and d will be called attaching vertices and the edges incident to them will be called attaching edges. In order to guarantee that the leaf addition is valid and that the drawing $\varGamma ''$ obtained by the insertion of the gadget inside f is 1-planar, we have to pay attention to two aspects: (i) if an attaching edge is crossed in the gadget, then its attaching vertex cannot be identified with a dummy vertex (otherwise when we remove the dummy vertex we obtain an edge that is crossed twice); (ii) if two attaching vertices of the gadget are coincident (because two end-vertices of $e'_1$ and $e'_2$ coincide), then the corresponding attaching edges must not have the second end-vertex in common in the gadget (otherwise the leaf addition is not valid because it creates multiple edges). We use different gadgets depending on whether $e_1$ and $e_2$ are parallel edges or not. If they are parallel edges, we use the gadgets of Figs. 2(a)–(d) and (i). Notice that in this case, $e_1$ and $e_2$ are not crossed by definition of cutting curve. It follows that f has no dummy vertex and (i) is guaranteed. On the other hand, both end-vertices of $e_1$ and $e_2$ coincide and therefore the end-vertices of the attaching edges that are not attaching vertices must be distinct. This is true for the gadgets used in this case. If $e_1$ and $e_2$ are non-parallel, we use the gadgets of Figs. 2(e)–(h) and (j). All these gadgets have only one attaching edge that is crossed (labeled d in the figure); also, vertex d can be identified with vertex c without creating multiple edges. If $e_1$ and $e_2$ are non-parallel, at most two end-vertices of $e'_1$ and $e'_2$ are dummy; they cannot belong to the same stub, and they cannot coincide (because $e_1$ and $e_2$ do not cross each other). Thus we can identify d with a non-dummy vertex and we can identify c and d if needed.    $\square$

We are ready to describe our construction of a 1-planar packing of $P_1$, $P_2$, and T. We use different techniques for different lengths of the backbone of T.

Fig. 3.

1-planar packings of three paths with $n' \ge 8$ vertices (case $k=3$); A cutting curve is shown (zig-zag pattern) for each internal vertex of the black path.

Lemma 2

Two paths and a 5-legged caterpillar whose backbone contains $n' \ge 6$ vertices admit a 1-planar packing.

Proof

We start with the construction of a 1-planar packing of the three paths $P'_1$, $P'_2$ and P. Let $n'$ be the number of vertices of $P'_1$, $P'_2$ and P, assume first that $n' \ge 8$ and $n' \equiv 0 \pmod 4$. A 1-planar packing of $P'_1$, $P'_2$ and P for this case is shown in Fig. 3(a) for $n'=16$ and it is easy to see that it can be extended to any $n'$ multiple of 4. Assume that the backbone P of T is the path shown in black in Fig. 3(a). To add the leaves of T to the construction we define a cutting curve for each vertex that has some leaves attached; we then execute a leaf addition operation for each such vertex. By Lemma 1, it is possible to execute each leaf addition so to guarantee the 1-planarity of the resulting drawing. The cutting curve for each internal vertex of P is shown in Fig. 3(a) with a zig-zag pattern. Note that, regardless of the order in which the leaf additions are executed, the cutting curves remain valid.

Suppose that $n' \ge 8$ and $n' \not \equiv 0 \pmod 4$. We first construct a 1-planar packing of three paths with $n''=4k$ vertices (with $k = \lfloor \frac{n'}{4} \rfloor$) using the same construction as in the previous case and then we add one, two or three vertices as shown in Figs. 3(b)–(d), which also show the cutting curves for each internal vertex of P. If $n'$ is 6 or 7, we use the same approach; the difference is in the construction of the 1-planar packing of $P'_1$, $P'_2$ and P. The construction for such a packing and the cutting curves for the internal vertices of P are in Figs. 4(a)–(b).   $\square$

Lemma 3

Two paths and a 5-legged caterpillar T whose backbone contains $n' = 5$ vertices admit a 1-planar packing, unless T is a path.

Proof

If T is a path, then $P_1$, $P_2$ and T are all paths of length five, and by Property 1, a 1-planar packing of $P_1$, $P_2$ and T does not exist. Suppose therefore that at least one internal vertex of the backbone P of T has some leaves attached. We use an approach similar to the one of Lemma 2. However, as just explained, a 1-planar packing of $P'_1$, $P'_2$ and P does not exist in this case. We start with a 1-planar packing with two pairs of parallel edges. For each pair, one edge belongs to $P'_1$ and the other one to $P'_2$. We will remove the parallel edges by performing the leaf addition operations. To this aim we must guarantee that there is a cutting curve for each pair of parallel edges. The 1-planar packing $P'_1$, $P'_2$ and P and the cutting curves for the internal vertices of P are shown in Fig. 4(c), for the case when at least two vertices have leaves attached. Indeed, if only two vertices have leaves attached, they are either consecutive along the backbone or not. In the first case, these two vertices are mapped to the vertices labeled a and b in Fig. 4(c) and the depicted cutting curves will remove the parallel edges; in the second case, the two vertices are mapped to the vertices labeled a and c and also in this case the depicted cutting curves will remove the parallel edges.

Fig. 4.

1-planar packings of three paths with $n' \in \{5,6,7\}$ vertices, with a cutting curve (zig-zag pattern) for each internal vertex of the black path.

If only one vertex of P has leaves attached, we have only one cutting curve and thus it is not possible to intersect both pairs of parallel edges. To handle this case we use an ad-hoc technique which can be found in [3].   $\square$

The next theorem gives a complete characterization for the case in which the backbone of T has length four.

Theorem 3

Two paths and a caterpillar T whose backbone contains $n' = 4$ vertices admit a 1-planar packing if and only if $n \ge 6$ and $\deg _T(v) \le n-3$ for every vertex v.

Lemmas 2 and 3, together with Theorem 3 imply the next theorem.

Theorem 4

Two paths and a 5-legged caterpillar T with n vertices admit a 1-planar packing if and only if $n \ge 6$ and $\deg _T(v) \le n-3$ for every vertex v.

5 1-Planar Packings with Constant Edge Crossings

The technique described in the previous section constructs 1-planar drawings that have a linear number of crossings. A natural question is whether it is possible to compute a 1-planar packing with a constant number of crossings. In this section we prove that seven (resp. fourteen) crossings suffice for packing three paths (resp. cycles). It is worth remarking that a 1-planar packing of three paths has at least three crossings (because it has $3n-3$ edges), while a 1-planar packing of three cycles has at least six crossings (because it has 3n edges).

Theorem 5

Three paths with $n\ge 6$ vertices can be packed into a 1-plane graph with at most 7 edge crossings.

Fig. 5.

Illustration for the proof of Theorem 5.

Proof

We prove the statement by showing how to construct a 1-planar drawing with at most 7 crossings of a graph that is the union of three paths. Suppose first that $n=7+3k$ for $k \in \mathbb {N}$. If $k=0$, we draw the union of the three paths with 7 vertices as shown in Fig. 4(a). The drawing is 1-planar and has three crossings in total. Suppose now that $k > 0$. We consider three rays $r_0,r_1,r_2$ with a common origin pairwise forming a $120^\circ$ angle and we place k vertices on each line. We denote by $u_{i,1},u_{i,2},\dots ,u_{i,k}$ the vertices of line $r_i$ ($i=0,1,2$) in the order they appear along $r_i$ starting from the origin (see Fig. 5(a)). In the following, indices will be taken modulo 3 when working with the indices of the rays $r_i$. To draw path $P_i$ ($i=0,1,2$) we draw the edges $(u_{i,1},u_{i+1,1})$, $(u_{i,j},u_{i+1,j-1})$, and $(u_{i,j},u_{i+1,j})$ (for $j=2,\dots ,k$) as straight-line segments. Notice that, these edges form a zig-zagging path between the vertices of rays $r_i$ and $r_{i+1}$, so $P_i$ passes through all vertices of $r_i$ and $r_{i+1}$ but not through the vertices of $r_{i+2}$. To include these missing vertices in $P_i$, we add to $P_i$ edges $(u_{i+2,j},u_{i+2,j+1})$ (for $j=1,2,\dots ,k-1$). In this way we draw two disjoint sub-paths for each path $P_i$, namely a zig-zagging path between $r_i$ and $r_{i+1}$ and a straight-line path along $r_{i+2}$. Moreover, we only draw 3k edges and therefore there are still 7 missing vertices (and 8 missing edges) in each path. To add the missing vertices and edges and to connect the two sub-paths of each path, we construct a drawing $\varGamma _0$ of three paths $P'_0,P'_1,P'_2$ with seven vertices as in the case when $k=0$. Denote with $v_i$ and $w_i$ the end-vertices of $P'_i$ in $\varGamma _0$. We place $\varGamma _0$ inside the triangle $u_{0,1}, u_{1,1}, u_{2,1}$ and add the edges $(v_i,u_{i,1})$ and $(w_i,u_{i+2,1})$. It is easy to see (see also Fig. 5(b)) that these six edges can be added so that the drawing is still 1-planar and so that the total number of crossings is 6. This concludes the proof for $n=7+3k$. If $n=7+3k+1$ we start with the same construction as in the previous case and then add an extra vertex v outside the triangle $u_{1,k}, u_{2,k}, u_{3,k}$. Notice that each of these three vertices is the end-vertex of two of the three paths with $7+3k$ vertices. Thus we can extend each path to include v by connecting it to each of the three vertices $u_{1,k}, u_{2,k}, u_{3,k}$ in a planar way (see Fig. 5(c) ignoring vertex w). If $n=7+3k+2$, then we add two extra vertices outside the triangle $u_{0,k}, u_{1,k}, u_{2,k}$ and connect both of them to the three vertices $u_{0,k}, u_{1,k}, u_{2,k}$ (recall that each of these three vertices is the end-vertex of two distinct paths with $7+3k$ vertices). In this case however the addition of the two extra vertices causes the creation of one crossing. Thus the final drawing is 1-planar and the total number of crossings is at most 7 (see Fig. 5(c)). This concludes the proof for $n \ge 7$. If $n=6$ we construct a 1-planar packing of three paths with three crossings in total as shown in Fig. 4(b).    $\square$

The construction of Theorem 5 can be extended to three cycles.

Theorem 6

Three cycles with $n\ge 20$ vertices can be packed into a 1-plane graph with at most 14 edge crossings.

6 From Triples to Quadruples

In this section we extend the study of 1-planar packings from triples of graphs to quadruples of graphs. By Property 1, a 1-planar packing of four graphs does not exist if all graphs are connected, because the number of edges of the four graphs is higher than the number of edges allowed in a 1-planar graph. We consider therefore a quadruple consisting of three paths and a perfect matching. Notice that, in this case the number of vertices n has to be even.

Theorem 7

Three paths and a perfect matching with $n \ge 12$ vertices admit a 1-planar packing. If $n \le 10$, the quadruple does not admit a 1-planar packing.

Fig. 6.

(a) Graph $G'$ used in the proof of Theorem 7 $(n=8k, k=3)$. (b)–(e) 1-planar packings of three paths and a perfect matching obtained starting from $G'$.

Proof

Three paths and a perfect matching have a total of $3(n-1)+\frac{n}{2}=\frac{7n}{2}-3$ edges. Since a 1-planar graph has at most $4n-8$ edges, a 1-planar packing of three paths and a perfect matching exists only if $\frac{7n}{2}-3 \le 4n-8$, i.e., if $n \ge 10$. If $n=10$, we have $\frac{7n}{2}-3=32$ and $4n-8=32$, which means that any 1-planar packing of three paths and a perfect matching with $n=10$ vertices is an optimal 1-planar graph. It is known that every optimal 1-planar graph has at least eight vertices of degree exactly six [1]. On the other hand, in any 1-planar packing of three paths and a perfect matching all vertices, except the at most six end-vertices of the three paths, have degree seven, which implies that a 1-planar packing of three paths and a perfect matching does not exist.

We now prove that a 1-planar packing exists if $n \ge 12$. We only discuss here the case when $n \ge 24$; the cases in which $12 \le n \le 22$ are described in [3]. Based on the fact that in any 1-planar packing of three paths and a perfect matching at least $n - 6$ vertices have degree seven, we construct the desired 1-planar packing starting from a 1-planar graph G such that at least $n - 6$ vertices have degree at least seven; we then partition the edges of G into five sets; three of these sets form a spanning path each, the fourth one forms a perfect matching, and the fifth one contains edges that will not be part of the 1-planar packing. For every $n = 8k$ and $k\ge 3$ it is possible to construct a 1-planar graph with n vertices each having degree at least seven as follows. We start with $k-1$ cycles $C_1,C_2,\dots ,C_{k-1}$. Each cycle $C_i$ ($1 \le i \le k-1$) has eight vertices $v_{i,j}$ with $0 \le j \le 7$. Cycle $C_i$, for $1 \le i \le k-2$, is embedded inside $C_{i+1}$ and is connected to it with edges $(v_{i,j},v_{i+1,j})$ for each $0 \le j \le 7$. We have a cycle with four vertices $u_0, u_1, u_2, u_3$ embedded inside $C_1$ and connected to it with edges $(u_j,v_{1,2j})$ and $(u_j,v_{1,2j+1})$. Finally, we have a cycle with four vertices $w_0, w_1, w_2, w_3$ embedded outside $C_{k-1}$ and connected to it with edges $(w_j,v_{k-1,2j})$ and $(w_j,v_{k-1,2j+1})$. The graph $G'$ described so far has n vertices, is planar, all its vertices have degree four, and each vertex is incident to at most one face of size three (see Fig. 6(a)). By adding two crossing edges inside each face of size four, we obtain a 1-planar graph G with n vertices having degree at least seven. The graph G and the partition of the edges of G in five sets defining three paths and a matching is shown in Fig. 6(b). If n is not a multiple of 8, then it will be $n=8k+r$, with $0<r<8$ and r even (because n is even). In this case we construct $G'$ as explained above and then we extend the paths $u_0, v_{1,1}, \dots ,v_{k-1,1}$ and $u_1, v_{1,2}, \dots ,v_{k-1,2}$ to the left with 1, 2 or 3 vertices each; we then suitably rearrange the edges of $G'$. The graph G is then obtained, as in the previous case, by adding a pair of crossing edges inside each face of size four. The resulting graph G and a partition of its edges in five sets defining three paths and a matching is shown in Figs. 6(c), (d), and (e), for the cases when $r=2$, $r=4$, and $r=6$, respectively.   $\square$

7 Open Problems

We find that the 1-planar packing problem is a fertile and still largely unexplored research subject. We conclude the paper with a list of open problems.(i) Theorem 2 holds only for $n=7$. Do two caterpillars (or more general trees) and a path admit a 1-planar packing if they have more than 7 vertices? (ii) Can Theorem 4 be extended to general caterpillars? What about two paths and a tree more complex than a caterpillar, for example a binary tree? (iii) Is it possible to compute a 1-planar packing of three paths or cycles with the minimum number of crossings (three and six, respectively)? Can we compute 1-planar packings with few crossings for triples of other types of trees?