#  $k$-planar Placement and Packing
of $\Delta$-regular Caterpillars

Carla Binucci  Dipartimento di Ingegneria, Università degli Studi di Perugia,
via G. Duranti 93, 06125, Perugia, Italy. {carla.binucci, emilio.digiacomo,
giuseppe.liotta<EMAIL_ADDRESS>Emilio Di Giacomo  Dipartimento
di Ingegneria, Università degli Studi di Perugia, via G. Duranti 93, 06125,
Perugia, Italy. {carla.binucci, emilio.digiacomo, giuseppe.liotta,
<EMAIL_ADDRESS>Michael Kaufmann  Wilhelm-Schickard Institut für
Informatik, Universität Tübingen, Sand 13, 72076, Tübingen, Germany.
<EMAIL_ADDRESS>Giuseppe Liotta  Dipartimento di Ingegneria,
Università degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy.
{carla.binucci, emilio.digiacomo, giuseppe.liotta,
<EMAIL_ADDRESS>Alessandra Tappini  Dipartimento di Ingegneria,
Università degli Studi di Perugia, via G. Duranti 93, 06125, Perugia, Italy.
{carla.binucci, emilio.digiacomo, giuseppe.liotta,
<EMAIL_ADDRESS>
###### Abstract

This paper studies a _packing_ problem in the so-called beyond-planar setting,
that is when the host graph is “almost-planar” in some sense. Precisely, we
consider the case that the host graph is $k$-planar, i.e., it admits an
embedding with at most $k$ crossings per edge, and focus on families of
$\Delta$-regular caterpillars, that are caterpillars whose non-leaf vertices
have the same degree $\Delta$. We study the dependency of $k$ from the number
$h$ of caterpillars that are packed, both in the case that these caterpillars
are all isomorphic to one another (in which case the packing is called
_placement_) and when they are not. We give necessary and sufficient
conditions for the placement of $h$ $\Delta$-regular caterpillars and
sufficient conditions for the packing of a set of $\Delta_{1}$-,
$\Delta_{2}$-, $\dots$, $\Delta_{h}$-regular caterpillars such that the degree
$\Delta_{i}$ and the degree $\Delta_{j}$ of the non-leaf vertices can differ
from one caterpillar to another, for $1\leq i,j\leq h$, $i\neq j$.

##  1 Introduction

Graph _packing_ is a classical problem in graph theory. The original
formulation requires to merge several smaller graphs into a larger graph,
called the _host graph_ , without creating multiple edges. More precisely,
graphs $G_{1},G_{2},\dots,G_{h}$ with $G_{i}=(V_{i},E_{i})$ should be combined
to a new graph $G=(V,E)$ by injective mappings $\eta_{i}:V_{i}\rightarrow V$
so that $V=V_{1}\cup V_{2}\cup\dots\cup V_{h}$ and the images of the edge sets
$E_{i}$ do not intersect. It has been often assumed that $|V_{i}|=n$ for all
$i=1,2,\dots h$, and thus the mappings $\eta_{i}$ are bijective. Many
combinatorial problems can be regarded as packing problems. For example, the
Hamiltonian cycle problem for a graph $G$ can be stated as the problem of
packing an $n$-vertex cycle with the complement of $G$.

When no restriction is imposed on the host graph, we say that the host graph
is $K_{n}$. Some classical results in this setting are those by Bollobás and
Eldridge [6], Teo and Yap [26], Sauer and Spencer [25], while related famous
conjectures are by Erdős and Sós from 1963 [10] and by Gyárfás from 1978 [16].
Within this line of research, Wang and Sauer [27], and Mahéo et al. [22]
characterized triples of trees that admit a packing into $K_{n}$. Haler and
Wang [17] extended this result to four copies of a tree. Further notable work
on graph packing into $K_{n}$ is by Hedetniemi et al. [18], Wozniak and Wojda
[28] and Aichholzer et al. [2]. A packing problem with identical copies of a
graph is also called a _placement problem_ (see, e.g., [17, 27, 29]).

A tighter relation to graph drawing was established when researchers did not
consider $K_{n}$ to be the host graph, but required that the host graph is
planar. The main question here is how to pack two trees of size $n$ into a
planar graph of size $n$. After a long series of intermediate steps [11, 12,
13, 14, 24] where the class of trees that could be packed has been gradually
generalized, Geyer et al. [15] showed that any two non-star trees can be
embedded into a planar graph.

Relaxing the planarity condition allows for packing of more (than two) trees,
and restricting the number of crossings for each edge, i.e., in the so-called
beyond-planar setting [9, 19, 21], still keeps the host graph sparse. The
study of the packing problem in the beyond planarity setting was started by De
Luca et al. [8], who consider how to pack caterpillars, paths, and cycles into
1-planar graphs (see, e.g., [21] for a survey and references on 1-planarity).
While two trees can always be packed into a planar graph, it may not be
possible to pack three trees into a $1$-planar graph.

In this work we further generalize the problem by allowing the host graph to
be $k$-planar for any $k\geq 1$, and we study the dependency of $k$ on the
number of caterpillars to be packed and on their vertex degree. We consider
_$\Delta$ -regular_ caterpillars, which are caterpillars whose non-leaf
vertices all have the same degree. Our results can be briefly outlined as
follows.

  * •

We consider the packing problem of $h$ copies of the same $\Delta$-regular
caterpillar into a $k$-planar graph. We characterize those families of $h$
$\Delta$-regular caterpillars which admit a placement into a $k$-planar graph
and show that $k\in O(\Delta h+h^{2})$.

  * •

We extend the study from the placement problem to the packing problem by
considering a set of $\Delta_{1}$-, $\Delta_{2}$-, $\dots$,
$\Delta_{h}$-regular caterpillars such that the degree $\Delta_{i}$ and the
degree $\Delta_{j}$ of the non-leaf vertices can differ from one caterpillar
to another, with $1\leq i,j\leq h$, $i\neq j$. By extending the techniques of
the bullet above, we give sufficient conditions for the existence of a
$k$-planar packing of these caterpillars and show that $k\in O(\Delta h^{2})$.

  * •

Finally, we prove a general lower bound on $k$ and show that this lower bound
can be increased for small values of $h$ and for caterpillars that are not
$\Delta$-regular.

The rest of the paper is organized as follows. Preliminaries are in Section 2.
The placement of $h$ $\Delta$-regular caterpillars into a $k$-planar graph is
discussed in Section 3. Section 4 is devoted to $k$-planar $h$-packing, while
Section 5 gives lower bounds on the value of $k$ as a function of $h$.
Concluding remarks and open problems can be found in Section 6.

##  2 Preliminaries

We assume familiarity with basic graph drawing and graph theory terminology
(see, e.g., [5, 20, 23]) and recall here only those concepts and notation that
will be used in the paper.

Given a graph $G$, we denote by $\deg_{G}(v)$ the degree of a vertex $v$ in
$G$. Let $G_{1},G_{2},\dots,G_{h}$ be $h$ graphs, all having $n$ vertices, an
_$h$ -packing_ of $G_{1},G_{2},\dots,G_{h}$ is an $n$-vertex graph $G$ that
contains $G_{1},G_{2},\dots,G_{h}$ as edge-disjoint spanning subgraphs. We
also say that $G_{1},G_{2},\dots,G_{h}$ can be _packed into $G$_ and that $G$
is the _host graph_ of $G_{1},G_{2},\dots,G_{h}$. An $h$-packing of $h$ graphs
into a host graph $G$ such that the $h$ graphs are all isomorphic to a graph
$H$, is called an _$h$ -placement_ of $H$ into $G$. We also say that
$G_{1},G_{2},\dots,G_{h}$ can be _placed into $G$_. The following property
establishes a necessary condition for the existence of an $h$-packing into any
host graph.

######  Property 1.

A packing of $h$ connected $n$-vertex graphs exists only if $n\geq 2h$ and
$\deg_{G_{i}}(v)\leq n-h$, for each $i\in\\{1,2,\dots,h\\}$ and for each
vertex $v$.

###### Proof.

Each $G_{i}$ has at least $n-1$ edges (because it is connected); thus, if
$n<2h$ the $h$ graphs have more edges in total than the number of edges of any
graph with $n$ vertices. But since graphs $G_{i}$ must be edge-disjoint
subgraphs of $G$, the number of edges of $G$ must be at least the total number
of edges of the graphs $G_{i}$. Since $\deg_{G_{i}}(v)\geq 1$ for every
$i\in\\{1,2,\dots,h\\}$ and for each $v$ (because each $G_{i}$ is connected)
and since $\sum_{i=1}^{h}\deg_{G_{i}}(v)\leq n-1$ (because $G$ cannot have
vertex-degree larger that $n-1$), it holds that $\deg_{G_{i}}(v)\leq n-h$, for
each $i\in\\{1,2,\dots,h\\}$ and for each vertex $v$. ∎

A _$k$ -planar graph_ is a graph that admits a drawing in the plane such that
each edge is crossed at most $k$ times. If the host graph of an $h$-packing
($h$-placement) is $k$-planar, we will talk about a _k-planar $h$-packing_
(_k-planar $h$-placement_). Sometimes, we shall simply say $k$-planar packing
or $k$-planar placement, when the value of $h$ is clear from the context or
not relevant.

A _caterpillar_ is a tree such that removing all leaves we are left with a
path, called _spine_. A caterpillar $T$ is _$\Delta$ -regular_, for
$\Delta\geq 2$, if $\deg_{T}(v)=\Delta$ for every vertex $v$ of the spine of
$T$. The number of vertices of a $\Delta$-regular caterpillar is
$n=\sigma(\Delta-1)+2$ for some positive integer $\sigma$, which is the number
of vertices of the spine.

##  3 $h$-placement of $\Delta$-regular Caterpillars into $k$-planar Graphs

Given $h$ copies of a same $\Delta$-regular caterpillar, we want to study
under which conditions they admit a placement into a $k$-planar graph. We
start by showing that the necessary condition stated in Property 1 is, in
general, not sufficient to guarantee a placement even for $\Delta$-regular
caterpillars.

######  Theorem 1.

For every $h\geq 2$, let $\Delta$ be a positive integer such that
$\frac{h-1}{\Delta-1}$ is not an integer. A set of $h$ $\Delta$-regular
caterpillars with $n=2h$ vertices does not admit a placement into any graph.

###### Proof.

Since each caterpillar has $n-1$ edges and the number of caterpillars is
$h=\frac{n}{2}$, the total number of edges is $\frac{n(n-1)}{2}$ and thus, if
a placement exists, the host graph can only be $K_{n}$. We now prove that this
is not possible. Denote by $C_{1},C_{2},\ \dots,C_{h}$ the $h$ caterpillars
and suppose that a packing into $K_{n}$ exists. Let $v$ be a vertex of $K_{n}$
and let $v_{1},v_{2},\dots,v_{h}$ be the $h$ vertices that are mapped to $v$,
with $v_{i}$ being a vertex of $C_{i}$. Each vertex $v_{i}$ has degree in
$C_{i}$ that is either $\Delta$ or $1$ (because each $C_{i}$ is
$\Delta$-regular). Denote by $c$ the number of vertices among
$v_{1},v_{2},\dots,v_{h}$ that have degree $\Delta$; the degree of $v$ in the
packing is $c\Delta+(h-c)$ and since the degree of $v$ in $K_{n}$ is $n-1$, it
must be $c\Delta+(h-c)=n-1$, i.e., $c\Delta+(h-c)=2h-1$, which can be
rewritten as $c=\frac{h-1}{\Delta-1}$. But this is not possible because $c$ is
integer, while $\frac{h-1}{\Delta-1}$ is not. ∎

In the rest of this section we shall establish necessary and sufficient
conditions that characterize when a set of $h$ isomorphic $\Delta$-regular
caterpillars admit a $k$-planar $h$-placement. Concerning the sufficiency, in
Section 3.1 we describe a constructive argument that computes a set of so-
called _zig-zag drawings_ and study the properties of such drawings. In
Section 3.2, we complete the characterization by also giving necessary
conditions for an $h$-placement of $\Delta$-regular caterpillars into a
$k$-planar graph; in the same section, we give an upper bound on $k$ as a
function of $h$ and $\Delta$.

We recall that a $\Delta$-regular caterpillar has a number of vertices $n$
that is equal to $\sigma(\Delta-1)+2$ for some natural number $\sigma$, which
is the number of vertices of the spine. While $\Delta$-regular caterpillars
are defined for any value of $\sigma\geq 1$, when we want to pack a set of
$h\geq 2$ caterpillars, Property 1 requires that each caterpillar has at least
two spine vertices, i.e., that $\sigma\geq 2$ for each caterpillar. Otherwise,
the unique spine vertex would have degree $n-1$ and Property 1 would not hold.

###  3.1 Zig-zag Drawings of $\Delta$-regular caterpillars

Figure 1:  (a) A zig-zag drawing of a $4$-regular caterpillar; (b) the upper
and the lower part are highlighted; c) a $2$-packing obtained by the drawing
of (b) with a copy of it rotated by one step.

Let $C$ be a $\Delta$-regular caterpillar with $n$ vertices; we construct a
drawing $\Gamma$ of $C$ as shown in Fig. 1. The number of vertices of the
spine of $C$ is $\sigma=\frac{n-2}{\Delta-1}$; consider a set of $\sigma$
points on a circle $\gamma$ and denote by $u_{1},u_{2},\dots,u_{\sigma}$ these
points according to the circular clockwise order they appear along $\gamma$.
Draw the spine of $C$ by connecting, for
$i=1,2,\dots,\lfloor\frac{\sigma}{2}\rfloor$, the points $u_{i}$ and $u_{i+1}$
to the point $u_{\sigma-i+1}$; see Fig. 1. If $\sigma$ is even and
$i=\frac{\sigma}{2}$, the points $u_{i+1}$ and $u_{\sigma-i+1}$ coincide and
therefore the point $u_{\frac{\sigma}{2}}$ is connected only to
$u_{\frac{\sigma}{2}+1}$. Notice that all points $u_{i}$ have two incident
edges, except $u_{1}$ and $u_{\lfloor\frac{\sigma}{2}\rfloor+1}$ which have
only one. We add the leaves adjacent to each vertex
$u_{i}\not\in\\{u_{1},u_{\lfloor\frac{\sigma}{2}\rfloor+1}\\}$ by connecting
$u_{\sigma-i+1}$ to $\Delta-2$ points between $u_{i}$ and $u_{i+1}$; we then
add the leaves adjacent to $u_{1}$ by connecting it to $\Delta-1$ points
between $u_{\sigma}$ and $u_{1}$; we finally add the leaves adjacent to
$u_{\lfloor\frac{\sigma}{2}\rfloor+1}$ by connecting it to $\Delta-1$ points
between $u_{\frac{\sigma}{2}}$ and $u_{\frac{\sigma}{2}+1}$ if $\sigma$ is
even, or to $\Delta-1$ points between $u_{\lfloor\frac{\sigma}{2}\rfloor+1}$
and $u_{\lfloor\frac{\sigma}{2}\rfloor+2}$ if $\sigma$ is odd. The resulting
drawing is called a _zig-zag drawing_ of $C$.

From now on, we assume that in a zig-zag drawing the points that represent
vertices are equally spaced on the circle $\gamma$. Let $\chi$ be the convex
hull of the points representing the vertices of $C$ in $\Gamma$. A zig-zag
drawing has exactly two sides of $\chi$ that coincide with two edges of $C$;
we call these two edges _short edges_ of $\Gamma$; each other side of $\chi$
is called a _hole_. Denote by $v_{1},v_{2},\dots,v_{n}$ the vertices of
$\Gamma$ according to the circular clockwise order they appear along $\chi$
with $v_{1}\equiv u_{1}$; see Fig. 1. Notice that $(v_{1},v_{n})$ is a short
edge and $v_{n}$ is the degree-1 vertex of this edge.

Consider a straight line $s$ that intersects both short edges of $\Gamma$;
line $s$ intersects all the edges of the zig-zag drawing. Without loss of
generality, assume that $s$ is horizontal and denote by $U$ the set of
vertices that are above $s$ and by $L$ the set of vertices that are below $s$.
The vertices in $U$ form the _upper part_ of $\Gamma$ and those in $L$ form
the _lower part_ of $\Gamma$. Without loss of generality assume that $v_{1}$
is in the upper part (and therefore $v_{n}$ is in the lower part). It follows
that each edge has the end-vertex with lower index in the upper part, and the
end-vertex with higher index in the lower part. Hence the short edge different
from $(v_{1},v_{n})$, which we denote as $(v_{r-1},v_{r})$, is such that
$v_{r-1}$ is in the upper part and $v_{r}$ is in the lower part. The first
vertex of the upper part, i.e., vertex $v_{1}$, is called _starting point_ of
$\Gamma$, while the first vertex of the lower part, i.e., vertex $v_{r}$, is
called _ending point_ of $\Gamma$. We observe that $r=\frac{n}{2}+1$ if the
number of vertices of the spine $\sigma=\frac{n-2}{\Delta-1}$ is even, while
$r=1+\frac{n-(\Delta-1)}{2}$ if $\sigma$ is odd. This can be written with a
single formula as $r=1+\frac{n-(\Delta-1)(\sigma\mod 2)}{2}$. The two short
edges separate two sets of consecutive holes, one completely contained in the
upper part and one completely contained in the lower part; if $\sigma$ is
even, these two sets have the same number of holes equal to $\frac{n-2}{2}$;
if $\sigma$ is odd, then one of the two sets has $\frac{n-\Delta-1}{2}$ holes,
while the other has $\frac{n+\Delta-3}{2}$. Note that the smaller set is in
the upper part.

Let $\ell$ be a positive integer and let $\Gamma^{\prime}$ be the drawing
obtained by re-mapping vertex $v_{i}$ to the point111In a drawing in convex
position the indices of the vertices are taken modulo $n$. representing
$v_{i+\ell}$ in $\Gamma$. We say that $\Gamma^{\prime}$ is the drawing
obtained by _rotating $\Gamma$ by $\ell$ steps._ Note that the starting point
of $\Gamma^{\prime}$ is $v_{j}$ with $j=1+\ell$ and the ending point is
$v_{r}$ with $r=1+\ell+\frac{n-(\Delta-1)(\sigma\mod
2)}{2}=j+\frac{n-(\Delta-1)(\sigma\mod 2)}{2}$. The drawing in Fig. 1 is the
union of two zig-zag drawings $\Gamma_{1}$ and $\Gamma_{2}$, where
$\Gamma_{2}$ is obtained by rotating $\Gamma_{1}$ by one step; the starting
point of $\Gamma_{1}$ is $v_{1}$ while its ending point is $v_{8}$; the
starting point of $\Gamma_{2}$ is $v_{2}$, while its ending point is $v_{9}$.

######  Lemma 1.

Let $\Gamma_{1}$ be a zig-zag drawing of a $\Delta$-regular caterpillar $C$
with starting point $j_{1}$ and ending point $r_{1}$; let $\Gamma_{2}$ be a
zig-zag drawing of $C$ with starting point $j_{2}$. If
$0<j_{2}-j_{1}<\frac{n-(\Delta-1)(\sigma\mod 2)}{2}$, where $\sigma$ is the
number of spine vertices of $C$, then $\Gamma_{1}\cup\Gamma_{2}$ has no
multiple edges.

###### Proof.

We first observe that $\Gamma_{2}$ is obtained by rotating $\Gamma_{1}$ by
$\ell$ steps, where $\ell=j_{2}-j_{1}$. Suppose that a multiple edge
$(v_{i},v_{g})$, with $i<g$ exists in $\Gamma_{1}\cup\Gamma_{2}$. This implies
that in the drawing $\Gamma_{1}$ there must be an edge
$(v_{i^{\prime}},v_{g^{\prime}})$ that, when rotated by $\ell$ steps,
coincides with $(v_{i},v_{g})$. In other words, the two edges $(v_{i},v_{g})$
and $(v_{i^{\prime}},v_{g^{\prime}})$ must be such that: (i)
$i^{\prime}<i<r_{1}\leq g<g^{\prime}$; (ii) $g=i^{\prime}+\ell$; (iii) the
number $\alpha$ of vertices encountered between $v_{i}$ and $v_{g}$ when going
clockwise from $v_{i}$ to $v_{g}$ is the same as the number of vertices
encountered when going clockwise from $v_{g^{\prime}}$ to $v_{i^{\prime}}$
(see Fig. 2). Denote by $\beta$ the number of vertices encountered when going
clockwise from $v_{i^{\prime}}$ to $v_{i}$, and by $\zeta$ the number of
vertices encountered when going clockwise from $v_{g}$ to $v_{g^{\prime}}$. We
have $2\alpha+\beta+\zeta+4=n$. If $\sigma$ is even, then $\beta=\zeta$ (see
Fig. 2), which implies $\alpha+\beta+2=\frac{n}{2}$. Notice that
$g=i^{\prime}+\ell$ implies that $\ell=\beta+\alpha+2$ ($\ell$ is equal to the
number of vertices encountered clockwise between $v_{i^{\prime}}$ and $v_{g}$
plus one) and therefore $(v_{i^{\prime}},v_{g^{\prime}})$ can coincide with
$(v_{i},v_{g})$ after a rotation of $\ell$ steps only if $\ell=\frac{n}{2}$
but, when $\sigma$ is even, we have $\ell=j_{2}-j_{1}<\frac{n}{2}$ and
therefore a multiple edge cannot exist.

Figure 2:  Illustration for the proof of Lemma 1; (a) $\sigma$ even; (b)-(c)
$\sigma$ odd.

If $\sigma$ is odd, then $\beta-(\Delta-1)\leq\zeta\leq\beta+(\Delta-1)$ (see
Figs. 2 and 2) and therefore $2\alpha+2\beta-(\Delta-1)+4\leq
2\alpha+\beta+\zeta+4=n\leq 2\alpha+2\beta+(\Delta-1)+4$, which can be
rewritten as
$\frac{n-(\Delta-1)}{2}\leq\alpha+\beta+2\leq\frac{n+(\Delta-1)}{2}$. It
follows that, in order to have $(v_{i^{\prime}},v_{g^{\prime}})$ and
$(v_{i},v_{g})$ coincident after a rotation of $\ell$ steps, the value of
$\ell$ must be such that
$\frac{n-(\Delta-1)}{2}\leq\ell\leq\frac{n+(\Delta-1)}{2}$; but, when $\sigma$
is odd, we have $\ell=j_{2}-j_{1}<\frac{n-(\Delta-1)}{2}$ and therefore a
multiple edge cannot exist. ∎

We conclude this section by computing the maximum number of crossings per edge
in the union of two zig-zag drawings without overlapping edges. We state this
lemma in general terms assuming that the two $\Delta$-regular caterpillars can
have different vertex degrees, as we are going to use the lemma to establish
upper bounds on $k$ both for $k$-planar $h$-placements and for $k$-planar
$h$-packings (Section 4).

Let $\Gamma$ be a union of a set of zig-zag drawings. To ease the description
that follows, we regard $\Gamma$ as a sub-drawing of a straight-line drawing
of $K_{n}$ whose vertices coincide with those of $\Gamma$ (and therefore are
equally spaced along a circle). In particular, for each vertex $v_{j}$, we
denote by $e_{j,0},e_{j,1},\dots,e_{j,n-2}$ the edges incident to $v_{j}$ in
$K_{n}$ according to the circular counterclockwise order around $v_{j}$
starting from $e_{j,0}=(v_{j},v_{j-1})$. Each of the zig-zag drawings that
form $\Gamma$ contains a subset of these edges and $\Gamma$ is a valid packing
if there is no edge that belongs to two different zig-zag drawings in the set
whose union is $\Gamma$.

We denote by $\mathcal{S}_{n}$ the (circular) sequence of slopes
$s_{i}=i\cdot\frac{\pi}{n}$, for $i=0,1,\dots,n-1$; refer to Fig. 3. Notice
that, without loss of generality, we can assume that the convex hull of
$\Gamma$ has a side with slope $s_{0}$ and, as a consequence, every edge of
$\Gamma$ has a slope in the set $\mathcal{S}_{n}$. Let $v_{j}$ be a vertex; if
the slope of $e_{j,0}$ is $s_{i_{j}}$, then the slope of $e_{j,p}$ is
$s_{{i_{j}}+p}$ (with indices taken modulo $n$); in other words, the edges
incident to each vertex have slopes that form a sub-sequence of $n-1$
consecutive elements of $\mathcal{S}_{n}$; we denote such a sequence as
$\psi(i_{j})$, where $i_{j}$ indicates that the first element of $\psi(i_{j})$
is $s_{i_{j}}$. We say that $v_{j}$ _uses_ the sequence $\psi(i_{j})$. If we
consider two different vertices $v_{j}$ and $v_{j+p}$ and $v_{j}$ uses the
sequence $\psi(i_{j})$, then $v_{j+p}$ uses the sequence $\psi(i_{j}-2p)$
(with indices taken modulo $n$); in other words, the sequence used by a vertex
shifts clockwise by two elements moving to the next vertex.

Figure 3: Illustration for the definition of slopes.

######  Lemma 2.

Let $C_{1}$ be an $n$-vertex $\Delta_{1}$-regular caterpillar and let $C_{2}$
be an $n$-vertex $\Delta_{2}$-regular caterpillar with $\Delta_{i}\leq n-2$
(for $i=1,2$). Let $\Gamma_{1}$ be a zig-zag drawing of $C_{1}$ with starting
point $v_{j_{1}}$ and let $\Gamma_{2}$ be a zig-zag drawing of $C_{2}$ with
starting point $v_{j_{2}}$ with $0<j_{2}-j_{1}<\frac{n}{2}$. If
$\Gamma_{1}\cup\Gamma_{2}$ has no multiple edges, then any edge of
$\Gamma_{1}\cup\Gamma_{2}$ is crossed at most
$2(\Delta_{1}+\Delta_{2})+4(j_{2}-j_{1})$ times.

###### Proof.

We first observe that the edges of a zig-zag drawing of a $\Delta$-regular
caterpillar are all drawn as segments whose slope belongs to a set of $\Delta$
slopes. In particular, for every spine vertex $v$, the edges incident to $v$
are drawn using all these $\Delta$ slopes.

Consider the starting vertex $v_{j_{1}}$ of $\Gamma_{1}$; the edges incident
to $v_{j_{1}}$ are drawn with the first $\Delta_{1}$ slopes of
$\psi(i_{j_{1}})$. Analogously, the edges incident to the starting vertex
$v_{j_{2}}$ of $\Gamma_{2}$ are drawn with the first $\Delta_{2}$ slopes of
$\psi(i_{j_{2}})$. The sequence $\psi(i_{j_{2}})$ is shifted clockwise by
$2(j_{2}-j_{1})$ units with respect to $\psi(i_{j_{1}})$. On the other hand,
since $j_{2}-j_{1}<\frac{n}{2}$, the first slope of $\psi(i_{j_{2}})$ is
distinct from the first slope of $\psi(i_{j_{1}})$.

Figure 4:  Illustration for the proof of Lemma 2. The edges of $\Gamma_{2}$
are dashed.

Let $e=(v_{i},v_{g})$ be an edge of $\Gamma_{1}$. We now prove that the number
of crossings along $e$ is at most the one given in the statement. Let
$e_{1}=(v_{i},v_{a})$ be the edge of $\Gamma_{2}$ incident to $v_{i}$ that
forms the smallest angle with $e$; analogously, let $e_{2}=(v_{g},v_{b})$ be
the edge of $\Gamma_{2}$ incident to $v_{g}$ that forms the smallest angle
with $e$. Notice that, in principle there are four possible clockwise orders
of $v_{i}$, $v_{a}$, $v_{g}$, and $v_{b}$ (see cases (a)–(d) in Fig. 4 for an
illustration). However the case (b) cannot happen. Namely, in case (b) the
slopes used to draw the edges of $\Gamma_{2}$ would be shifted
counterclockwise with respect to those used to represent the edges of
$\Gamma_{1}$; but, as observed above, the slopes used by $\Gamma_{2}$ are
shifted clockwise with respect to those used by $\Gamma_{1}$.

Let $\alpha_{1}$ be the angle between $e$ and $e_{1}$ and let $\alpha_{2}$ be
the angle between $e$ and $e_{2}$. Let $V_{1}$ be the set of vertices seen by
the angle $\alpha_{1}$ including $v_{a}$ and excluding $v_{g}$; analogously
let $V_{2}$ be the set of vertices seen by the angle $\alpha_{2}$ including
$v_{b}$ and excluding $v_{i}$. In each of the three cases (a), (c), and (d),
at least one of $\alpha_{1}$ and $\alpha_{2}$ is such that $e$ sweeps the
angle moving clockwise. Let $\alpha_{l}$ with $l\in\\{1,2\\}$ be the angle
that satisfies this condition. In particular, for case (a) $\alpha_{l}$ can be
both $\alpha_{1}$ or $\alpha_{2}$, in case (c) $\alpha_{l}$ is $\alpha_{2}$
and in case (d) $\alpha_{l}$ is $\alpha_{1}$ (see Fig. 4). Every edge that
crosses $e$ has an end-vertex in $V_{1}$ and one end-vertex in $V_{2}$. To
count the number of such edges (and therefore the number of crossings along
$e$), we evaluate $|V_{l}|$. The value of $|V_{l}|$ is at most the number of
slopes of $\mathcal{S}_{n}$ that are encountered in counterclockwise order
between the slope $s\in\mathcal{S}_{n}$ of $e_{l}$ and the slope
$s^{\prime}\in\mathcal{S}_{n}$ of $e$. In particular, in case (a) $|V_{l}|$ is
exactly this number, while in case (c) and (d) $|V_{l}|$ is less than this
number. The slope $s^{\prime}$ is at most the last slope used by $\Gamma_{1}$,
which is $s_{p}$ with $p=j_{1}+\Delta_{1}$, while the slope $s$ is at least
the first slope used by $\Gamma_{2}$, which is $s_{q}$ with
$q=j_{1}-2(j_{2}-j_{1})$. Thus, the number of slopes between $s^{\prime}$
(included) and $s$ (excluded) is at most $p-q=\Delta_{1}+2(j_{2}-j_{1})$.
Hence $|V_{l}|\leq\Delta_{1}+2(j_{2}-j_{1})$.

We call a _block_ a subset of consecutive vertices of $V_{l}$ starting with a
spine vertex and containing all the leaves that follow that spine vertex. The
number of edges of $\Gamma_{2}$ incident to the vertices of a block is
$2(\Delta_{2}-1)$ (since $\Delta_{2}$ edges are incident to the spine vertex
and $\Delta_{2}-2$ is the number of leaves). The number of blocks in $V_{l}$
is $\left\lceil\frac{|V_{l}|}{(\Delta_{2}-1)}\right\rceil$. It follows that
the number of crossings $\chi_{e}$ along $e$ is at most
$\left\lceil\frac{|V_{l}|}{(\Delta_{2}-1)}\right\rceil 2(\Delta_{2}-1)$ which
is less than $2(|V_{l}|+\Delta_{2})$. Since
$|V_{l}|\leq\Delta_{1}+2(j_{2}-j_{1})$, we have $\chi_{e}\leq
2(\Delta_{1}+\Delta_{2})+4(j_{2}-j_{1})$, which concludes the proof in the
case when $e$ belongs to $\Gamma_{1}$. The case when the edge $e$ belongs to
$\Gamma_{2}$ is analogous. In particular, when $e$ belongs to $\Gamma_{2}$,
the cases (b), (c), and (d) apply, while case (a) does not happen. ∎

###  3.2 Characterization

We are now ready to characterize the $\Delta$-regular caterpillars that admit
an $h$-placement.

######  Theorem 2.

Let $C$ be a $\Delta$-regular caterpillar with $n$ vertices. An $h$-placement
of $C$ exists if and only if: (i) $\Delta\leq n-h$; and (ii) $n\geq
2h+(\Delta-1)\cdot(\sigma\mod 2)$, where $\sigma$ is the number of spine
vertices of $C$. Further, if an $h$-placement exists, there exists one that is
$k$-planar for $k\in O(\Delta h+h^{2})$.

###### Proof.

We first prove the sufficient condition. Let $C_{1},C_{2},\dots,C_{h}$ be the
$h$ caterpillars and assume that $n\geq 2h+(\Delta-1)(\sigma\mod 2)$. We
compute an $h$-placement of $C_{1},C_{2},\dots,C_{h}$ starting from a zig-zag
drawing $\Gamma_{1}$ of $C_{1}$ and obtaining the drawing $\Gamma_{i}$ of
$C_{i}$ by rotating $\Gamma_{1}$ by $i-1$ steps, for $i=2,3,\dots,h$.

Notice that, when the number of spine vertices $\sigma$ of each $C_{i}$ is
even, $h\leq\frac{n}{2}$ and therefore each $\Gamma_{i}$ is rotated by less
than $\frac{n}{2}$ steps; when $\sigma$ is odd $h\leq\frac{n-(\Delta-1)}{2}$
and each $\Gamma_{i}$ is rotated by less than $\frac{n-(\Delta-1)}{2}$ steps.
In both cases, each pair of drawings $\Gamma_{i}$ and $\Gamma_{j}$ satisfies
the conditions of Lemma 1 and therefore there are no multiple edges, that is,
the union of all $\Gamma_{i}$ is a valid $h$-placement of
$C_{1},C_{2},\dots,C_{h}$.

We now prove the necessary condition. If $\sigma$ is even, then conditions (i)
and (ii) are necessary by Property 1. Hence, consider the case when $\sigma$
is odd. Condition (i) is necessary by Property 1. Assume, by contradiction,
that (ii) is not necessary, i.e., there exists an $h$-placement of $h$
caterpillars $C_{1},C_{2},\dots,C_{h}$ such that $n<2h+(\Delta-1)$. Since
$C_{1},C_{2},\dots,C_{h}$ admit an $h$-placement, by Property 1 $n$ must be at
least $2h$. Thus, it would be $2h\leq n<2h+(\Delta-1)$; in other words,
$n=2h+\alpha$ with $0\leq\alpha\leq\Delta-2$.

Let $G$ be the host graph of the $h$-placement and let $v$ be the vertex of
$G$ to which the largest number of spine vertices of $C_{1},C_{2},\dots,C_{h}$
is mapped. Let $\beta$ be the number of spine vertices that are mapped to $v$.
There are other $h-\beta$ leaf vertices that are mapped to $v$ (because one
vertex per caterpillar has to be mapped on each vertex of $G$). The degree of
$v$ in $G$ is at most $n-1$ and each of the spine vertices mapped to $v$ has
degree $\Delta$. Hence, the $\beta$ spine vertices mapped to $v$ have degree
$\beta\Delta$ in total. Vertex $v$ can have at most other $n-1-\beta\Delta$
edges and therefore it must be $n-1-\beta\Delta\geq h-\beta$, i.e.,
$\beta\leq\frac{n-1-h}{\Delta-1}$. On the other hand, there are $\sigma h$
spine vertices in total and, since $G$ has $n$ vertices, there are at least
$\lceil\frac{\sigma h}{n}\rceil$ spine vertices mapped to $v$, i.e.,
$\beta\geq\lceil\frac{\sigma h}{n}\rceil$. Putting together the two conditions
on $\beta$ we obtain:

$\left\lceil\frac{\sigma
h}{n}\right\rceil\leq\beta\leq\frac{n-1-h}{\Delta-1}.$

Since $n=2h+\alpha$, we have $h=\frac{n-\alpha}{2}$; replacing $h$ in Section
3.2, we obtain:

$\left\lceil\frac{\sigma}{2}-\frac{\sigma\alpha}{2n}\right\rceil\leq\beta\leq\frac{n+\alpha-2}{2(\Delta-1)}.$

Since $n=\sigma(\Delta-1)+2$, we have:

$\left\lceil\frac{\sigma}{2}-\frac{\sigma\alpha}{2(\sigma(\Delta-1)+2)}\right\rceil\leq\beta\leq\frac{\sigma(\Delta-1)+\alpha}{2(\Delta-1)}.$
(1)

Eq. 1 implies that:

$\left\lceil\frac{\sigma}{2}-\frac{\alpha}{2(\Delta-1)+\frac{4}{\sigma}}\right\rceil\leq\frac{\sigma}{2}+\frac{\alpha}{2(\Delta-1)}.$
(2)

We now prove that Eq. 2 cannot be satisfied. Since $\sigma$ is odd, it is
$\sigma=2i+1$ for some $i\in\mathbb{N}$, and thus:

$\left\lceil i+\frac{1}{2}-\zeta\right\rceil\leq
k+\frac{1}{2}+\zeta^{\prime},$ (3)

with $\zeta=\frac{\alpha}{2(\Delta-1)+\frac{4}{\sigma}}$ and
$\zeta^{\prime}=\frac{\alpha}{2(\Delta-1)}$. We have $\zeta<\zeta^{\prime}$
and we prove that $\zeta^{\prime}<\frac{1}{2}$:

$\zeta^{\prime}=\frac{\alpha}{2(\Delta-1)}\leq\frac{\Delta-2}{2(\Delta-1)}<\frac{\Delta-1}{2(\Delta-1)}=\frac{1}{2}.$

The first term of Eq. 3 is $i+1$ because $0<\frac{1}{2}-\zeta<1$; the second
term is less than $i+1$ because $0<\frac{1}{2}+\zeta^{\prime}<1$. It follows
that Eq. 3 does not hold and therefore Eq. 2 does not hold.

We now prove the bound on the number of crossings along an edge. We consider
an edge of $\Gamma_{1}$; the number of crossings along an edge of the drawing
of another caterpillar is bounded by the same number. Let $e$ be an edge of
the drawing $\Gamma_{1}$. By Lemma 2, the number of crossings $\chi_{e}$ along
$e$ due to the edges of another drawing $\Gamma_{l}$ (with $2\leq l\leq h$) is
at most $2(\Delta_{1}+\Delta_{l})+4(j_{l}-j_{1})$. Summing over all drawings
distinct from $\Gamma_{1}$, we obtain
$\chi_{e}\leq\sum_{l=2}^{h}(2(\Delta_{1}+\Delta_{l})+4(j_{l}-j_{1}))$.
Considering that $\Delta_{l}=\Delta$ for every $l$ and that $j_{l}-j_{1}=l-1$,
we have

$\chi_{e}\leq\sum_{l=2}^{h}(4\Delta+4(l-1))\leq(4\Delta-2)h+2h^{2}-4\Delta.$
(4)

∎

Figure 5:  (a) An inner zig-zag drawing and (d) an outer zig-zag drawing of a
$4$-regular caterpillar.

We conclude by observing that the number of crossings given by Eq. 4 can be
reduced, although not asymptotically. A zig-zag drawing can be embedded inside
the circle (see Fig. 5) or outside the circle (see Fig. 5). Thus, the number
given by Eq. 4 can be halved by embedding half of the caterpillars inside the
circle and the other half outside the circle.

##  4 $h$-packing of $\Delta$-regular Caterpillars in $k$-planar Graphs

In this section we study $h$-packings of $h$ $\Delta_{1}$-, $\Delta_{2}$-,
$\dots$, $\Delta_{h}$-regular caterpillars such that the degree $\Delta_{i}$
and the degree $\Delta_{j}$ of the spine vertices can differ from one
caterpillar to another, for $1\leq i,j\leq h$, $i\neq j$.

######  Lemma 3.

Let $C_{1}$ be an $n$-vertex $\Delta_{1}$-regular caterpillar and let $C_{2}$
be an $n$-vertex $\Delta_{2}$-regular caterpillar such that
$\Delta_{1}>\Delta_{2}$ and $\Delta_{1}\leq n-2$. Let $\Gamma_{1}$ be a zig-
zag drawing of $C_{1}$ with starting point $v_{j_{1}}$ and ending point
$v_{r_{1}}$, and let $\Gamma_{2}$ be a zig-zag drawing of $C_{2}$ with
starting point $v_{j_{2}}$ and ending point $v_{r_{2}}$. If
$\frac{\Delta_{2}}{2}\leq j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}$, then
$\Gamma_{1}\cup\Gamma_{2}$ has no multiple edges.

###### Proof.

As described in the proof of Lemma 2, the edges of a zig-zag drawing of a
$\Delta$-regular caterpillar are all drawn as segments whose slope belongs to
a set of $\Delta$ slopes. In particular, for every spine vertex $v$, the edges
incident to $v$ are drawn using all these $\Delta$ slopes. Based on this
observation, we show that the $\Delta_{1}$ slopes used to represent the edges
of $\Gamma_{1}$ are distinct from the $\Delta_{2}$ slopes used to represent
the edges of $\Gamma_{2}$. We use the same notation used in Theorem 2.

Consider the staring vertex $v_{j_{1}}$ of $\Gamma_{1}$; the edges incident to
$v_{j_{1}}$ are drawn with the first $\Delta_{1}$ slopes of $\psi(i_{j_{1}})$.
Analogously, the edges incident to the starting vertex $v_{j_{2}}$ of
$\Gamma_{2}$ are drawn with the first $\Delta_{2}$ slopes of
$\psi(i_{j_{2}})$. Since $j_{2}-j_{1}\geq\frac{\Delta_{2}}{2}$, the sequence
$\psi(i_{j_{2}})$ is shifted clockwise by $\Delta_{2}$ units with respect to
$\psi(i_{j_{1}})$. On the other hand, since
$j_{2}-j_{1}\leq\frac{n-(\Delta_{1}-1)}{2}$, the sequence of the first
$\Delta_{2}$ slopes of $\psi(i_{j_{2}})$ does not overlap with the first
$\Delta_{1}$ slopes of $\psi(i_{j_{1}})$, which concludes the proof.∎

######  Theorem 3.

Let $C_{1},C_{2},\dots,C_{h}$ be $h$ caterpillars such that $C_{i}$ is
$\Delta_{i}$-regular, for $1\leq i\leq h$, and
$\Delta_{h}\leq\Delta_{h-1}\leq\dots\leq\Delta_{1}\leq n-h$. If
$\sum_{i=1}^{h}\Delta_{i}\leq n-1$ and
$\sum_{i=2}^{h}\left\lceil\frac{\Delta_{i}}{2}\right\rceil<\frac{n-(\Delta_{1}-1)}{2}$,
then there exists a $k$-planar packing with $k\in O(\Delta_{1}h^{2})$.

###### Proof.

We compute a zig-zag drawing of $C_{1}$ with starting point $v_{j_{1}}$, with
$j_{1}=1$; for each $C_{i}$, with $2\leq i\leq h$, we compute a zig-zag
drawing $\Gamma_{i}$ with starting vertex $v_{j_{i}}$ where
$j_{i}=j_{i-1}+\left\lceil\frac{\Delta_{i}}{2}\right\rceil$. Notice that, each
vertex $v$ of $\Gamma_{1}\cup\Gamma_{2}\cup\dots\cup\Gamma_{h}$ has degree at
most $n-1$; namely
$\sum_{i=1}^{h}\deg_{C_{i}}(v)\leq\sum_{i=1}^{h}\Delta_{i}\leq n-1$. Moreover,
given two caterpillars $C_{i}$ and $C_{i^{\prime}}$ with $1\leq
i<i^{\prime}\leq h$, we have that: (i) $j_{i^{\prime}}-j_{i}\geq
j_{i^{\prime}}-j_{i^{\prime}-1}=\left\lceil\frac{\Delta_{i^{\prime}}}{2}\right\rceil$;
and (ii) $j_{i^{\prime}}-j_{i}\leq
j_{h}-j_{1}=\sum_{i=2}^{h}\lceil\frac{\Delta_{i}}{2}\rceil$, which gives
$j_{i^{\prime}}-j_{i}<\frac{n-(\Delta_{1}-1)}{2}<\frac{n-(\Delta_{i}-1)}{2}$.
Putting together (i) and (ii), we obtain
$\frac{\Delta_{i^{\prime}}}{2}<j_{i^{\prime}}-j_{i}<\frac{n-(\Delta_{i}-1)}{2}$.
Hence, Lemma 3 holds for every pair of caterpillars and the union of all the
zig-zag drawings $\Gamma_{1},\Gamma_{2},\dots,\Gamma_{h}$ is a valid packing
of $C_{1},C_{2},\dots,C_{h}$.

We now prove the bound on the number of crossings along an edge. We consider
an edge of $\Gamma_{1}$; the number of crossings along an edge of another
drawing is bounded by the same number. Let $e$ be an edge of the drawing
$\Gamma_{1}$. By Lemma 2, the number of crossings $\chi_{e}$ along $e$ due to
the edges of another drawing $\Gamma_{l}$ (with $2\leq l\leq h$) is at most
$2(\Delta_{1}+\Delta_{l})+4(j_{l}-j_{1})$. Summing over all drawings distinct
form $\Gamma_{1}$, we obtain
$\chi_{e}\leq\sum_{l=2}^{h}(2(\Delta_{1}+\Delta_{l})+4(j_{l}-j_{1}))$.
Considering that $j_{l}\geq
j_{l-1}+\left\lceil\frac{\Delta_{i}}{2}\right\rceil$, we obtain that
$j_{l}-j_{1}=\sum_{i=2}^{l}\left\lceil\frac{\Delta_{i}}{2}\right\rceil$. Since
$\Delta_{l}\leq\Delta_{1}$ for every $2\leq l\leq h$, we have
$j_{l}-j_{1}\leq(l-1)(\frac{\Delta_{1}}{2}+1)$. Therefore, we obtain
$\chi_{e}\leq\sum_{l=2}^{h}(4\Delta_{1}+4(l-1)(\frac{\Delta_{1}}{2}+1))\leq(\Delta_{1}+2)h^{2}+4\Delta_{1}(h-1)$.
∎

We now consider a special case of packing a set of $h$ $\Delta_{1}$-,
$\Delta_{2}$-, $\dots$, $\Delta_{h}$-regular caterpillars where, for each
$\Delta_{i}$ $(1\leq i\leq h$), we have that $\Delta_{i}-1$ is a multiple of
$\Delta_{i+1}-1$. In this case, we show that the sufficient conditions of
Theorem 3 can be relaxed. For example, consider the packing of a $17$-regular
caterpillar and two $9$-regular caterpillars, each having $34$ vertices. These
three caterpillars do not satisfy the sufficient condition of Theorem 3.
However, a $k$-planar packing of these caterpillars is possible, as proven in
Theorem 4. We start with the following property, which immediately follows
from the construction of a zig-zag drawing (see also Fig. 6 for an
illustration).

######  Property 2.

Let $\Gamma$ be a zig-zag drawing of a $\Delta$-regular caterpillar with
starting vertex $v_{j}$ and ending vertex $v_{r}$. If $v_{i}$ is a spine
vertex in the upper part of $\Gamma$, then $i=j+c(\Delta-1)$ for some
$c\in\mathbb{N}$; if $v_{g}$ is a spine vertex in the lower part of $\Gamma$,
then $g=r+d(\Delta-1)$ for some $d\in\mathbb{N}$. Moreover, if $v_{i}$ and
$v_{g}$ are adjacent then either
$c+d=\left\lceil\frac{\sigma}{2}\right\rceil-1$ or
$c+d=\left\lceil\frac{\sigma}{2}\right\rceil$, where $\sigma$ is the number of
spine vertices of $\Gamma$.

Figure 6: Illustration for Property 2; $\sigma=5$. For each spine vertex, $c$
and $d$ are shown. Considering adjacent spine vertices, the sum of $c$ and $d$
is 2 or 3.

Property 2 is extensively used in the proof of the following lemma.

######  Lemma 4.

Let $C_{1}$ be an $n$-vertex $\Delta_{1}$-regular caterpillar and let $C_{2}$
be an $n$-vertex $\Delta_{2}$-regular caterpillar such that
$\Delta_{1}-1=q(\Delta_{2}-1)$, for some $q\in\mathbb{N}^{+}$ and
$\Delta_{i}\leq n-2$ (for $i=1,2$). Let $\Gamma_{1}$ be a zig-zag drawing of
$C_{1}$ with starting point $v_{j_{1}}$ and ending point $v_{r_{1}}$, and let
$\Gamma_{2}$ be a zig-zag drawing of $C_{2}$ with starting point $v_{j_{2}}$
and ending point $v_{r_{2}}$. If $0<j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}$,
then $\Gamma_{1}\cup\Gamma_{2}$ has no multiple edges.

###### Proof.

Let $(v_{i_{1}},v_{g_{1}})$ be an edge of $\Gamma_{1}$ and
$(v_{i_{2}},v_{g_{2}})$ be an edge of $\Gamma_{2}$. Assume that $v_{i_{1}}$
belongs to the upper part of $\Gamma_{1}$ and $v_{i_{2}}$ belongs to the upper
part of $\Gamma_{2}$. Note that this implies that $v_{g_{1}}$ belongs to the
lower part of $\Gamma_{1}$ and $v_{g_{2}}$ belongs to the lower part of
$\Gamma_{2}$. We prove that $(v_{i_{1}},v_{g_{1}})$ and
$(v_{i_{2}},v_{g_{2}})$ do not coincide.

We first show that it does not happen that $v_{i_{1}}$ coincides with
$v_{i_{2}}$ and $v_{g_{1}}$ coincides with $v_{g_{2}}$. We then show that it
does not happen that $v_{i_{1}}$ coincides with $v_{g_{2}}$ and $v_{g_{1}}$
coincides with $v_{i_{2}}$. In the rest of the proof we will express the four
indices $i_{1}$, $i_{2}$, $g_{1}$ and $g_{2}$ in terms of the values $j_{1}$,
$j_{2}$, $r_{1}$ and $r_{2}$, according to Property 2. Without loss of
generality, we can assume that $r_{2}\leq n$ and $j_{1}\geq 1$, i.e., that the
vertices $v_{r_{2}}$, $v_{n}$, $v_{1}$, and $v_{j_{1}}$ appear in this
clockwise order, with $v_{r_{2}}$ and $v_{n}$ possibly coincident and with
$v_{1}$ and $v_{j_{1}}$ possibly coincident. With these assumptions, we have
$j_{1}<j_{2}<r_{1}<r_{2}$ and $v_{i_{1}}$ can coincide with $v_{g_{2}}$ only
if $i_{1}=g_{2}-n$, i.e., only if the value of $g_{2}$ is greater than $n$ and
coincides with $i_{1}$ modulo $n$. Thus, while assuming that $v_{i_{1}}$
coincides with $v_{i_{2}}$ implies that $i_{1}=i_{2}$, assuming that
$v_{i_{1}}$ coincides with $v_{g_{2}}$ implies that $i_{1}=g_{2}-n$.

Case 1: It does not happen that $v_{i_{1}}$ coincides with $v_{i_{2}}$ and
$v_{g_{1}}$ coincides with $v_{g_{2}}$.

At least one vertex per edge is a spine vertex. We distinguish four sub-cases
depending on which vertex is a spine vertex for each edge. Since all the cases
are very similar, we give here only the first case and the others can be found
in the appendix.

Case 1.a: $v_{i_{1}}$ and $v_{i_{2}}$ are spine vertices. By Property 2 we
have, for some $c_{1},c_{2}\in\mathbb{N}$:

$i_{1}=j_{1}+c_{1}(\Delta_{1}-1)=j_{1}+qc_{1}(\Delta_{2}-1).$ (5)

and

$i_{2}=j_{2}+c_{2}(\Delta_{2}-1).$ (6)

If $v_{i_{1}}$ coincides with $v_{i_{2}}$, we have $i_{1}=i_{2}$; from Eq. 5
and Eq. 6 we obtain:

$j_{2}-j_{1}=(qc_{1}-c_{2})(\Delta_{2}-1).$ (7)

Concerning $v_{g_{1}}$ and $v_{g_{2}}$, we have:

$g_{1}^{m}\leq g_{1}\leq g_{1}^{M};$ $g_{2}^{m}\leq g_{2}\leq g_{2}^{M}.$

with $g_{l}^{m}=r_{l}+d_{l}(\Delta_{l}-1)$,
$g_{l}^{M}=r_{l}+(d_{l}+1)(\Delta_{l}-1)$ for some $d_{l}\in\mathbb{N}$ such
that $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, where
$\sigma_{l}$ is the number of spine vertices of $C_{l}$, for $l=1,2$.

We prove that $g_{1}^{M}<g_{2}^{m}$, which implies $g_{1}\neq g_{2}$. To have
$g_{1}^{M}<g_{2}^{m}$ it must be:

$\displaystyle r_{1}+(d_{1}+1)(\Delta_{1}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{1}+q(d_{1}+1)(\Delta_{2}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{2}-r_{1}>(qd_{1}+q-d_{2})(\Delta_{2}-1).$ (8)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 8 can be rewritten as:

$j_{2}-j_{1}>\left((qd_{1}+q-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}\right)(\Delta_{2}-1).$ (9)

Combining Eq. 7 and Eq. 9 we obtain:

$qc_{1}-c_{2}>(qd_{1}+q-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle qc_{1}-c_{2}>\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q+q-\frac{\sigma_{2}}{2}-\frac{1(\sigma_{2}\mod 2)}{2}+c_{2}+$
$\displaystyle+1+\frac{\sigma_{2}\mod 2}{2}-\frac{q(\sigma_{1}\mod 2)}{2}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-c_{2}>\frac{1}{2}$ (10)

In summary, to have $g_{1}^{M}<g_{2}^{m}$ Eq. 10 must hold. On the other hand,
from Eq. 7 and from the hypothesis that $j_{2}-j_{1}>0$ we obtain
$(qc_{1}-c_{2})(\Delta_{2}-1)>0$ which, since $(\Delta_{2}-1)>0$, implies
$qc_{1}-c_{2}>0$ and, since $qc_{1}-c_{2}$ is integer, can be rewritten as
$qc_{1}-c_{2}\geq 1$. This implies that Eq. 10 holds and therefore that
$g_{1}^{M}<g_{2}^{m}$ and $g_{1}\neq g_{2}$.

Case 2: It does not happen that $v_{i_{1}}$ coincides with $v_{g_{2}}$ and
$v_{g_{1}}$ coincides with $v_{i_{2}}$.

Also in this case we distinguish four sub-cases depending on which vertex is a
spine vertex for each edge. As in Case 1, we give here only the first sub-
case, while the others can be found in the appendix.

Case 2.a: $v_{i_{1}}$ and $v_{i_{2}}$ are spine vertices. Since $v_{g_{2}}$ is
a vertex in the lower part of $\Gamma_{2}$, it must be
$g_{2}=r_{2}+d_{2}(\Delta_{2}-1)+\alpha_{2}$, for some $\alpha_{2}$ such that
$0\leq\alpha_{2}<\Delta_{2}-1$. If $v_{g_{2}}$ coincides with $v_{i_{1}}$, as
explained above, it must be $i_{1}=g_{2}-n$. Combining the expression of
$g_{2}$ with Eq. 5 we obtain:

$r_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)-\alpha_{2}+n.$ (11)

Concerning $v_{g_{1}}$, we have:

$g_{1}^{m}\leq g_{1}\leq g_{1}^{M};$

with $g_{1}^{m}=r_{1}+d_{1}(\Delta_{1}-1)$,
$g_{1}^{M}=r_{1}+(d_{1}+1)(\Delta_{1}-1)$ for some $d_{1}\in\mathbb{N}$ such
that $c_{1}+d_{1}=\left\lceil\frac{\sigma_{1}}{2}\right\rceil-1$, where
$\sigma_{1}$ is the number of spine vertices of $C_{1}$.

We prove that $i_{2}<g_{1}^{m}$, which implies $i_{2}\neq g_{1}$. To have
$i_{2}<g_{1}^{m}$ it must be:

$\displaystyle j_{2}+c_{2}(\Delta_{2}-1)<r_{1}+d_{1}(\Delta_{1}-1)$
$\displaystyle j_{2}+c_{2}(\Delta_{2}-1)<r_{1}+qd_{1}(\Delta_{2}-1)$
$\displaystyle j_{2}-r_{1}<(qd_{1}-c_{2})(\Delta_{2}-1).$ (12)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 11 can be rewritten as:

$j_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)-\alpha_{2}+\frac{n}{2}+\frac{(\Delta_{2}-1)(\sigma_{2}\mod
2)}{2},$ (13)

while Eq. 12 can be rewritten as:

$j_{2}-j_{1}<\left((qd_{1}-c_{2})-\frac{q(\sigma_{1}\mod
2)}{2}\right)(\Delta_{2}-1)+\frac{n}{2}.$ (14)

Combining Eq. 13 and Eq. 14 we obtain:

$qc_{1}-d_{2}<(qd_{1}-c_{2})-\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}+\frac{\alpha_{2}}{\Delta_{2}-1}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle qc_{1}-\frac{\sigma_{2}}{2}-\frac{\sigma_{2}\mod
2}{2}+c_{2}+1<\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q-c_{2}-$ $\displaystyle-\frac{\sigma_{2}\mod
2}{2}-\frac{q(\sigma_{1}\mod 2)}{2}+\frac{\alpha_{2}}{\Delta_{2}-1}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}<-\frac{q+1}{2}+\frac{\alpha_{2}}{2(\Delta_{2}-1)}$
(15)

In summary, to have $i_{2}^{M}<g_{1}^{m}$ Eq. 15 must hold. On the other hand,
from Eq. 13 and from the hypothesis that
$j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}=\frac{n-q(\Delta_{2}-1)}{2}$ we
obtain:

$qc_{1}-d_{2}+\frac{1}{2}(\sigma_{2}\mod
2)<-\frac{q}{2}+\frac{\alpha_{2}}{\Delta_{2}-1}.$

Replacing again $d_{2}$ with $\frac{\sigma_{2}+1(\sigma_{2}\mod
2)}{2}-c_{2}-1$, we obtain:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}<-\frac{q+2}{2}+\frac{\alpha_{2}}{\Delta_{2}-1}.$
(16)

We have that
$-\frac{q}{2}-1+\frac{\alpha_{2}}{\Delta_{2}-1}<-\frac{q}{2}-\frac{1}{2}+\frac{\alpha_{2}}{2(\Delta_{2}-1)}$,
since $\frac{\alpha_{2}}{2(\Delta_{2}-1)}<\frac{1}{2}$.

In other words, Eq. 16 implies that Eq. 15 holds and therefore that
$i_{2}<g_{1}^{m}$ and $i_{2}\neq g_{1}$.

∎

######  Theorem 4.

Let $C_{1},C_{2},\dots,C_{h}$ be $h$ caterpillars such that $C_{i}$ is
$\Delta_{i}$-regular, $\Delta_{i}-1$ is a multiple of $\Delta_{i+1}-1$, with
$1\leq i<h$, and $\Delta_{i}\leq n-h$ (for $i=1,2,\dots,h$). If $n\geq
2h+(\Delta_{1}-1)$, then there exists a $k$-planar packing with $k\in
O(\Delta_{1}h+h^{2})$.

###### Proof.

For each $C_{i}$, with $1\leq i\leq h$, we compute a zig-zag drawing
$\Gamma_{i}$ with starting vertex $v_{i}$. Notice that, given two caterpillars
$C_{j_{1}}$ and $C_{j_{2}}$ with $1\leq j_{1}<j_{2}\leq h$, we have that
$\Delta_{j_{1}}-1$ is a multiple of $\Delta_{j_{2}}-1$, and the zig-zag
drawings $\Gamma_{j_{1}}$ and $\Gamma_{j_{2}}$ have starting vertices
$v_{j_{1}}$ and $v_{j_{2}}$, respectively. Hence, $0<j_{2}-j_{1}<h$ and by
hypothesis $h\leq\frac{n-(\Delta_{1}-1)}{2}$. Hence, Lemma 4 holds for every
pair of caterpillars and the union of all zig-zag drawings
$\Gamma_{1},\Gamma_{2},\dots,\Gamma_{h}$ is a valid packing of
$C_{1},C_{2},\dots,C_{h}$.

The proof of the bound on the number of crossings along an edge is the same as
the one of Theorem 2, considering that $\Delta_{l}\leq\Delta_{1}$ and that
$j_{l}-j_{1}=l-1$ for every $2\leq l\leq h$. ∎

##  5 Lower bounds

In this section we first give a general lower bound on the value of $k$ for
$k$-planar $h$-packings; we then increase this lower bound for some small
values of $h$.

######  Theorem 5.

Every $k$-planar $h$-packing of $h$ graphs with $n$ vertices and $m$ edges is
such that $k\geq\frac{h^{2}m^{2}}{14.6n^{2}}$.

###### Proof.

The number of edges of a $k$-planar graph with $n$ vertices is at most
$3.81\sqrt{k}\cdot n$, for $k\geq 2$ [1]. Since the $h$ graphs have $h\cdot m$
edges in total, a $k$-planar packing of these graphs can exist only if $h\leq
3.81\sqrt{k}\frac{n}{m}$, i.e., if $k\geq\frac{h^{2}m^{2}}{14.6n^{2}}$. ∎

Since for a tree $m=n-1$, we have the following.

######  Corollary 1.

Every $k$-planar $h$-packing of $h$ trees is such that
$k\geq\frac{h^{2}}{58.4}$.

We now refine the lower bound above for small values of $h$ in an
$h$-placement of caterpillars. Specifically we show that for values of $h$
equal to $3$, $4$, and $5$ the corresponding lower bounds are $2$, $3$, and
$5$, respectively. Note that for all these cases the lower bound implied by
Corollary 1 is $1$.

######  Theorem 6.

For $h=3,4$ there exists a caterpillar $C$ with at least $h+7$ vertices for
which every $k$-planar $h$-placement of $C$ is such that $k\geq h-1$. For
$h=5$ there exists a caterpillar $C$ with at least $24$ vertices for which
every $k$-planar $5$-placement of $C$ is such that $k\geq h$.

###### Proof.

Case $h=3,4$. Let $n$ be an integer such that $n\geq h+7$, and let $C_{n,h}$
be the $n$-vertex caterpillar shown in Fig. 7. Notice that the vertex of
$C_{n,h}$ denoted as $v$ in Fig. 7 has degree $n-h$; we call it the _center_
of $C_{n,h}$. Consider any $h$-placement of $C_{n,h}$ into a graph $G$ and
denote as $v_{i}$ the vertex of $G$ which the center of $C_{i}$ is mapped to
($i=1,2,\dots,h$). The vertices $v_{1},v_{2},\dots,v_{h}$ must be distinct
because, if two centers were mapped to the same vertex of $G$ then this vertex
would have degree larger than $n-1$. Namely, if two centers are mapped to the
same vertex, this vertex has degree $2n-2h$ which is larger than $n-1$ if
$n>2h-1$, i.e., if $h+7>2h-1$, which is true for $h<6$. Since each $v_{i}$
($1\leq i\leq h$) has degree $n-h$ in $C_{i}$ and degree $1$ in each of the
$h-1$ other caterpillars, its degree in $G$ is $n-1$. Thus, $G$ contains
$K_{h,n-h}$. Thus, for $h=3$, $G$ contains $K_{3,7}$ ($n\geq 10$ in this
case), which is not $1$-planar [7]; for $h=4$, $G$ contains $K_{4,7}$ ($n\geq
11$ in this case), which is not $2$-planar [4]. The case $h=5$ is analogous
with $K_{5,19}$, which is not $4$-planar [3].∎

Figure 7:  A caterpillar as described in the proof of Theorem 6.

##  6 Concluding Remarks and Open Problems

This paper studied the placement and the packing of caterpillars into
$k$-planar graphs. It proved necessary and sufficient conditions for the
$h$-placement of $\Delta$-regular caterpillars in a $k$-planar graph and
sufficient conditions for the packing of a set of $\Delta_{1}$-,
$\Delta_{2}$-, $\dots$, $\Delta_{h}$-regular caterpillars with $k\in
O(\Delta_{1}h^{2})$ ($\Delta_{1}$ is the maximum vertex degree in the set).
The work in this paper contributes to the rich literature concerning the
placement and the packing problem in planar and non-planar host graphs and it
specifically relates with a recent re-visitation of these questions in the
beyond-planar context.

Many open problems naturally arise from the research in this paper. We
conclude the paper by listing some of those that, in our opinion, are among
the most interesting.

  * •

Extend the characterization of Theorem 2 to the placement of caterpillars that
are not $\Delta$-regular.

  * •

Theorems 4 and 3 give sufficient conditions for the $k$-planar packing of some
families of caterpillars. It would be interesting to give a complete
characterization of the packability of these families into $k$-planar graphs.

  * •

Theorem 6 improves the lower bound of Theorem 5 for caterpillars that are not
$\Delta$-regular. It would be interesting to find a similar result with
$\Delta$-regular caterpillars.

Finally, we point out that one could investigate what graphs can be
packed/placed into a $k$-planar graph for a given value of $k$, instead of
studying how $k$ varies with the number $h$ and the vertex degree of the
caterpillars that are packed/placed. While the interested reader can refer to
[3] for results with $k=1$, the following theorem gives a preliminary result
for $k=2$ (see the appendix for a proof). Notice that Eq. 4 in the proof of
Theorem 2 would give upper bounds in the range $[86,137]$ for the caterpillars
considered by the following theorem.

######  Theorem 7.

A $\Delta$-regular caterpillar with $4\leq\Delta\leq 7$ admits a $2$-planar
$3$-placement.

## References

  * [1] Eyal Ackerman.  On topological graphs with at most four crossings per edge.  Computational Geometry, 85:101574, 2019.
  * [2] Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann, and Emo Welzl.  Packing plane spanning trees and paths in complete geometric graphs.  Information Processing Letters, 124:35 – 41, 2017.
  * [3] Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, and Thomas Schneck.  1-fan-bundle-planar drawings of graphs.  Theoretical Computer Science, 723:23–50, 2018.
  * [4] Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, and Thomas Schneck.  Efficient generation of different topological representations of graphs beyond-planarity.  Journal of Graph Algorithms and Applications, 24(4):573–601, 2020\.
  * [5] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis.  Graph Drawing: Algorithms for the Visualization of Graphs.  Prentice-Hall, 1999.
  * [6] Béla Bollobás and Stephen E. Eldridge.  Packings of graphs and applications to computational complexity.  J. Comb. Theory, Ser. B, 25(2):105–124, 1978.
  * [7] Július Czap and Dávid Hudák.  1-planarity of complete multipartite graphs.  Discrete Applied Mathematics, 160(4):505–512, 2012.
  * [8] Felice De Luca, Emilio Di Giacomo, Seok-Hee Hong, Stephen G. Kobourov, William Lenhart, Giuseppe Liotta, Henk Meijer, Alessandra Tappini, and Stephen K. Wismath.  Packing trees into 1-planar graphs.  J. Graph Algorithms Appl., 25(2):605–624, 2021.
  * [9] Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani.  A survey on graph drawing beyond planarity.  ACM Comput. Surv., 52(1):4:1–4:37, 2019.
  * [10] P. Erdős.  Extremal problems in graph theory.  In Theory of Graphs and its Applications, Proc. Sympos. Smolenice, pages 29–36, 1964.
  * [11] Fabrizio Frati.  Planar packing of diameter-four trees.  In Proceedings of the 21st Annual Canadian Conference on Computational Geometry, pages 95–98, 2009.
  * [12] Fabrizio Frati, Markus Geyer, and Michael Kaufmann.  Planar packing of trees and spider trees.  Inf. Process. Lett., 109(6):301–307, 2009.
  * [13] Alfredo García Olaverri, M. Carmen Hernando, Ferran Hurtado, Marc Noy, and Javier Tejel.  Packing trees into planar graphs.  Journal of Graph Theory, 40(3):172–181, 2002.
  * [14] Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.  Planar packing of binary trees.  In WADS 2013, volume 8037 of LNCS, pages 353–364. Springer, 2013.
  * [15] Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.  The planar tree packing theorem.  JoCG, 8(2):109–177, 2017.
  * [16] András Gyárfás and Jenő Lehel.  Packing trees of different order into $K_{n}$.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 1, pages 463–469. North-Holland New York, 1978.
  * [17] Sean P. Haler and Hong Wang.  Packing four copies of a tree into a complete graph.  Australas. J Comb., 59:323–332, 2014.  URL: http://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p323.pdf.
  * [18] S.M. Hedetniemi, Stephen Hedetniemi, and P.J. Slater.  A note on packing two trees into $K_{n}$.  Ars Combinatoria, 11, 01 1981.
  * [19] Seok-Hee Hong and Takeshi Tokuyama, editors.  Beyond Planar Graphs.  Springer, 2020.  doi:10.1007/978-981-15-6533-5.
  * [20] Michael Kaufmann and Dorothea Wagner, editors.  Drawing Graphs, Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer, 2001.  doi:10.1007/3-540-44969-8.
  * [21] Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani.  An annotated bibliography on 1-planarity.  Computer Science Review, 25:49 – 67, 2017.
  * [22] Maryvonne Mahéo, Jean-François Saclé, and Mariusz Wozniak.  Edge-disjoint placement of three trees.  Eur. J. Comb., 17(6):543–563, 1996.
  * [23] Takao Nishizeki and Md. Saidur Rahman.  Planar Graph Drawing, volume 12 of Lecture Notes Series on Computing.  World Scientific, 2004.  doi:10.1142/5648.
  * [24] Yoshiaki Oda and Katsuhiro Ota.  Tight planar packings of two trees.  In 22nd European Workshop on Computational Geometry, 2006.
  * [25] Norbert Sauer and Joel Spencer.  Edge disjoint placement of graphs.  J. Comb. Theory, Ser. B, 25(3):295–302, 1978.
  * [26] S. K. Teo and H. P. Yap.  Packing two graphs of order $n$ having total size at most $2n-2$.  Graphs Comb., 6(2):197–205, 1990.
  * [27] Hong Wang and Norbert Sauer.  Packing three copies of a tree into a complete graph.  European Journal of Combinatorics, 14(2):137 – 142, 1993.
  * [28] Mariusz Wozniak and A. Pawel Wojda.  Triple placement of graphs.  Graphs and Combinatorics, 9(1):85–91, 1993.
  * [29] Andrzej Zak.  A note on k-placeable graphs.  Discret. Math., 311(22):2634–2636, 2011.  doi:10.1016/j.disc.2011.08.002.

##  Appendix A Missing cases for the proof of Lemma 4

Case 1.b: $v_{g_{1}}$ and $v_{g_{2}}$ are spine vertices. By Property 2 we
have, for some $d_{1},d_{2}\in\mathbb{N}$:

$g_{1}=r_{1}+d_{1}(\Delta_{1}-1)=r_{1}+qd_{1}(\Delta_{2}-1).$ (17)

and

$g_{2}=r_{2}+d_{2}(\Delta_{2}-1).$ (18)

If $v_{g_{1}}$ coincides with $v_{g_{2}}$, we have $g_{1}=g_{2}$; from Eq. 17
and Eq. 18 we obtain:

$r_{2}-r_{1}=(qd_{1}-d_{2})(\Delta_{2}-1).$ (19)

Concerning $v_{i_{1}}$ and $v_{i_{2}}$, we have:

$i_{1}^{m}\leq i_{1}\leq i_{1}^{M};$ $i_{2}^{m}\leq i_{2}\leq i_{2}^{M}.$

with $i_{l}^{m}=i_{l}+c_{l}(\Delta_{l}-1)$,
$i_{l}^{M}=i_{l}+(c_{l}+1)(\Delta_{l}-1)$ for some $c_{l}\in\mathbb{N}$ such
that $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, where
$\sigma_{l}$ is the number of spine vertices of $C_{l}$, for $l=1,2$.

We prove that $i_{1}^{M}<i_{2}^{m}$, which implies $i_{1}\neq i_{2}$. To have
$i_{1}^{M}<i_{2}^{m}$ it must be:

$\displaystyle j_{1}+(c_{1}+1)(\Delta_{1}-1)<j_{2}+c_{2}(\Delta_{2}-1)$
$\displaystyle j_{1}+q(c_{1}+1)(\Delta_{2}-1)<j_{2}+c_{2}(\Delta_{2}-1)$
$\displaystyle j_{2}-j_{1}>(qc_{1}+q-c_{2})(\Delta_{2}-1).$ (20)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 19 can be rewritten as:

$j_{2}-j_{1}=\left((qd_{1}-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}\right)(\Delta_{2}-1).$ (21)

Combining Eq. 21 and Eq. 20 we obtain:

$c_{2}-qc_{1}-q>-\frac{1}{2}.$ (22)

In summary, to have $i_{1}^{M}<i_{2}^{m}$ Eq. 22 must hold. On the other hand,
from Eq. 21 and from the hypothesis that $j_{2}-j_{1}>0$ we obtain
$c_{2}-qc_{1}-q>-1$ which, since $c_{2}-qc_{1}-q$ is integer, can be rewritten
as $c_{2}-qc_{1}-q\geq 0$. This implies that Eq. 22 holds and therefore that
$i_{1}^{M}<i_{2}^{m}$ and $i_{1}\neq i_{2}$.

Case 1.c: $v_{i_{1}}$ and $v_{g_{2}}$ are spine vertices. By Property 2 we
have, for some $c_{1}\in\mathbb{N}$:

$i_{1}=j_{1}+c_{1}(\Delta_{1}-1)=j_{1}+qc_{1}(\Delta_{2}-1).$ (23)

We also have, for some $c_{2}\in\mathbb{N}$ and
$0\leq\alpha_{2}<\Delta_{2}-1$:

$i_{2}=j_{2}+c_{2}(\Delta_{2}-1)+\alpha_{2}.$ (24)

If $v_{i_{1}}$ coincides with $v_{i_{2}}$, we have $i_{1}=i_{2}$; from Eq. 23
and Eq. 24 we obtain:

$j_{2}-j_{1}=(qc_{1}-c_{2})(\Delta_{2}-1)-\alpha_{2}.$ (25)

Concerning $v_{g_{1}}$, we have:

$g_{1}^{m}\leq g_{1}\leq g_{1}^{M};$

with $g_{1}^{m}=r_{1}+d_{1}(\Delta_{1}-1)$,
$g_{1}^{M}=r_{1}+(d_{1}+1)(\Delta_{1}-1)$ for some $d_{1}\in\mathbb{N}$ such
that $c_{1}+d_{1}=\left\lceil\frac{\sigma_{1}}{2}\right\rceil-1$, where
$\sigma_{1}$ is the number of spine vertices of $C_{1}$.

Since $v_{g_{2}}$ is a vertex in the lower part of $\Gamma_{2}$, it must be
$g_{2}=r_{2}+d_{2}(\Delta_{2}-1)$.

We prove that $g_{1}^{M}<g_{2}$, which implies $g_{1}\neq g_{2}$. To have
$g_{1}^{M}<g_{2}$ it must be:

$\displaystyle r_{1}+(d_{1}+1)(\Delta_{1}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{1}+q(d_{1}+1)(\Delta_{2}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{2}-r_{1}>(qd_{1}+q-d_{2})(\Delta_{2}-1).$ (26)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 26 can be rewritten as:

$j_{2}-j_{1}>\left((qd_{1}+q-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}\right)(\Delta_{2}-1).$ (27)

Combining Eq. 25 and Eq. 27 we obtain:

$qc_{1}-c_{2}-\frac{\alpha_{2}}{\Delta_{2}-1}>(qd_{1}+q-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle
qc_{1}-c_{2}-\frac{\alpha_{2}}{\Delta_{2}-1}>\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q+q-\frac{\sigma_{2}}{2}-\frac{1(\sigma_{2}\mod 2)}{2}+c_{2}+$
$\displaystyle+1+\frac{\sigma_{2}\mod 2}{2}-\frac{q(\sigma_{1}\mod 2)}{2}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-c_{2}>\frac{1}{2}+\frac{\alpha_{2}}{2(\Delta_{2}-1)}$ (28)

In summary, to have $g_{1}^{M}<g_{2}$ Eq. 28 must hold. On the other hand,
from Eq. 25 and from the hypothesis that $j_{2}-j_{1}>0$ we obtain
$(qc_{1}-c_{2})(\Delta_{2}-1)-\alpha_{2}>0$ which, since $(\Delta_{2}-1)>0$,
implies $qc_{1}-c_{2}>\frac{\alpha_{2}}{\Delta_{2}-1}$. Since
$0\leq\frac{\alpha_{2}}{\Delta_{2}-1}<1$ and $qc_{1}-c_{2}$ is integer, we
have $qc_{1}-c_{2}\geq 1$. This implies that Eq. 28 holds and therefore that
$g_{1}^{M}<g_{2}$ and $g_{1}\neq g_{2}$.

Case 1.d: $v_{g_{1}}$ and $v_{i_{2}}$ are spine vertices. By Property 2 we
have, for some $c_{2}\in\mathbb{N}$:

$i_{2}=j_{2}+c_{2}(\Delta_{2}-1).$ (29)

We also have, for some $c_{1}\in\mathbb{N}$ and
$0\leq\alpha_{1}<\Delta_{2}-1$:

$i_{1}=j_{1}+c_{1}(\Delta_{1}-1)+\alpha_{1}=j_{1}+qc_{1}(\Delta_{2}-1)+\alpha_{1}.$
(30)

If $v_{i_{1}}$ coincides with $v_{i_{2}}$, we have $i_{1}=i_{2}$; from Eq. 30
and Eq. 29 we obtain:

$j_{2}-j_{1}=(qc_{1}-c_{2})(\Delta_{2}-1)+\alpha_{1}.$ (31)

Concerning $v_{g_{2}}$, we have:

$g_{2}^{m}\leq g_{2}\leq g_{2}^{M}.$

with $g_{2}^{m}=r_{2}+d_{2}(\Delta_{2}-1)$,
$g_{2}^{M}=r_{2}+(d_{2}+1)(\Delta_{2}-1)$ for some $d_{2}\in\mathbb{N}$ such
that $c_{2}+d_{2}=\left\lceil\frac{\sigma_{2}}{2}\right\rceil-1$, where
$\sigma_{2}$ is the number of spine vertices of $C_{2}$.

Since $v_{g_{1}}$ is a vertex in the lower part of $\Gamma_{1}$, it must be
$g_{1}=r_{1}+d_{1}(\Delta_{1}-1)$.

We prove that $g_{1}<g_{2}^{m}$, which implies $g_{1}\neq g_{2}$. To have
$g_{1}<g_{2}^{m}$ it must be:

$\displaystyle r_{1}+d_{1}(\Delta_{1}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{1}+qd_{1}(\Delta_{2}-1)<r_{2}+d_{2}(\Delta_{2}-1)$
$\displaystyle r_{2}-r_{1}>(qd_{1}-d_{2})(\Delta_{2}-1).$ (32)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 32 can be rewritten as:

$j_{2}-j_{1}>\left((qd_{1}-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}\right)(\Delta_{2}-1).$ (33)

Combining Eq. 31 and Eq. 33 we obtain:

$qc_{1}-c_{2}+\frac{\alpha_{1}}{\Delta_{2}-1}>(qd_{1}-d_{2})+\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle
qc_{1}-c_{2}+\frac{\alpha_{1}}{\Delta_{2}-1}>\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q-\frac{\sigma_{2}}{2}-\frac{1(\sigma_{2}\mod 2)}{2}+c_{2}+$
$\displaystyle+1+\frac{\sigma_{2}\mod 2}{2}-\frac{q(\sigma_{1}\mod 2)}{2}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-c_{2}>\frac{1-q}{2}-\frac{\alpha_{1}}{2(\Delta_{2}-1)}$ (34)

In summary, to have $g_{1}<g_{2}^{m}$ Eq. 34 must hold. On the other hand,
from Eq. 31 and from the hypothesis that $j_{2}-j_{1}>0$ we obtain
$(qc_{1}-c_{2})(\Delta_{2}-1)+\alpha_{1}>0$ which, since $(\Delta_{2}-1)>0$,
implies $qc_{1}-c_{2}>-\frac{\alpha_{1}}{\Delta_{2}-1}$. Since
$0\leq\frac{\alpha_{1}}{\Delta_{2}-1}<1$ and $qc_{1}-c_{2}$ is integer, we
have $qc_{1}-c_{2}>0$. Since $q$ is a positive integer, this implies that Eq.
34 holds and therefore that $g_{1}<g_{2}^{m}$ and $g_{1}\neq g_{2}$.

Case 2.b: $v_{g_{1}}$ and $v_{g_{2}}$ are spine vertices. Since $v_{g_{2}}$ is
a vertex in the lower part of $\Gamma_{2}$, it must be
$g_{2}=r_{2}+d_{2}(\Delta_{2}-1)$. If $v_{g_{2}}$ coincides with $v_{i_{1}}$,
as explained above, it must be $i_{1}=g_{2}-n$. Combining the expression of
$g_{2}$ with Eq. 30 we obtain:

$r_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)+\alpha_{1}+n.$ (35)

Concerning $v_{i_{2}}$, we have:

$i_{2}^{m}\leq i_{2}\leq i_{2}^{M};$

with $i_{2}^{M}=j_{2}+(c_{2}+1)(\Delta_{2}-1)$ for some $c_{2}\in\mathbb{N}$
such that $c_{2}+d_{2}=\left\lceil\frac{\sigma_{2}}{2}\right\rceil-1$, where
$\sigma_{2}$ is the number of spine vertices of $C_{2}$.

We prove that $i_{2}^{M}<g_{1}$, which implies $i_{2}\neq g_{1}$. To have
$i_{2}^{M}<g_{1}$ it must be:

$\displaystyle j_{2}+(c_{2}+1)(\Delta_{2}-1)<r_{1}+d_{1}(\Delta_{1}-1)$
$\displaystyle j_{2}+(c_{2}+1)(\Delta_{2}-1)<r_{1}+qd_{1}(\Delta_{2}-1)$
$\displaystyle j_{2}-r_{1}<(qd_{1}-c_{2}-1)(\Delta_{2}-1).$ (36)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 35 can be rewritten as:

$j_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)/\alpha_{1}+\frac{n}{2}+\frac{(\Delta_{2}-1)(\sigma_{2}\mod
2)}{2},$ (37)

while Eq. 36 can be rewritten as:

$j_{2}-j_{1}<\left((qd_{1}-c_{2}-1)-\frac{q(\sigma_{1}\mod
2)}{2}\right)(\Delta_{2}-1)+\frac{n}{2}.$ (38)

Combining Eq. 37 and Eq. 38 we obtain:

$qc_{1}-d_{2}<(qd_{1}-c_{2}-1)-\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}-\frac{\alpha_{1}}{\Delta_{2}-1}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle qc_{1}-\frac{\sigma_{2}}{2}-\frac{\sigma_{2}\mod
2}{2}+c_{2}+1+\frac{\sigma_{2}\mod
2}{2}+\frac{\alpha_{1}}{\Delta_{2}-1}<\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-$ $\displaystyle-qc_{1}-q-c_{2}-\frac{q(\sigma_{1}\mod 2)}{2}-1$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}+1<-\frac{q}{2}-\frac{\alpha_{1}}{2(\Delta_{2}-1)}$
(39)

In summary, to have $i_{2}^{M}<g_{1}^{m}$ Eq. 39 must hold. On the other hand,
from Eq. 37 and from the hypothesis that
$j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}=\frac{n-q(\Delta_{2}-1)}{2}$ we
obtain:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}+1<-\frac{q}{2}-\frac{\alpha_{1}}{\Delta_{2}-1}.$
(40)

We have that
$-\frac{q}{2}-\frac{\alpha_{1}}{\Delta_{2}-1}<-\frac{q}{2}-\frac{\alpha_{1}}{2(\Delta_{2}-1)}$,
since $\frac{\alpha_{1}}{2(\Delta_{2}-1)}<\frac{1}{2}$. In other words, Eq. 40
implies that Eq. 39 holds and therefore that $i_{2}^{M}<g_{1}$ and $i_{2}\neq
g_{1}$.

Case 2.c: $v_{i_{1}}$ and $v_{g_{2}}$ are spine vertices. Since $v_{g_{2}}$ is
a vertex in the lower part of $\Gamma_{2}$, it must be
$g_{2}=r_{2}+d_{2}(\Delta_{2}-1)$. If $v_{g_{2}}$ coincides with $v_{i_{1}}$,
as explained above, it must be $i_{1}=g_{2}-n$. Combining the expression of
$g_{2}$ with Eq. 23 we obtain:

$r_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)+n.$ (41)

Concerning $v_{g_{1}}$, we have:

$g_{1}^{m}\leq g_{1}\leq g_{1}^{M};$

with $g_{1}^{m}=r_{1}+d_{1}(\Delta_{1}-1)$,
$g_{1}^{M}=r_{1}+(d_{1}+1)(\Delta_{1}-1)$ for some $d_{1}\in\mathbb{N}$ such
that $c_{1}+d_{1}=\left\lceil\frac{\sigma_{1}}{2}\right\rceil-1$, where
$\sigma_{1}$ is the number of spine vertices of $C_{1}$.

We prove that $i_{2}^{M}<g_{1}^{m}$, which implies $i_{2}\neq g_{1}$. To have
$i_{2}^{M}<g_{1}^{m}$ it must be:

$\displaystyle j_{2}+(c_{2}+1)(\Delta_{2}-1)<r_{1}+d_{1}(\Delta_{1}-1)$
$\displaystyle j_{2}+(c_{2}+1)(\Delta_{2}-1)<r_{1}+qd_{1}(\Delta_{2}-1)$
$\displaystyle j_{2}-r_{1}<(qd_{1}-c_{2}-1)(\Delta_{2}-1).$ (42)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 41 can be rewritten as:

$j_{2}-j_{1}=(qc_{1}-d_{2})(\Delta_{2}-1)+\frac{n}{2}+\frac{(\Delta_{2}-1)(\sigma_{2}\mod
2)}{2},$ (43)

while Eq. 42 can be rewritten as:

$j_{2}-j_{1}<\left((qd_{1}-c_{2}-1)-\frac{q(\sigma_{1}\mod
2)}{2}\right)(\Delta_{2}-1)+\frac{n}{2}.$ (44)

Combining Eq. 43 and Eq. 44 we obtain:

$qc_{1}-d_{2}<(qd_{1}-c_{2}-1)-\frac{(\sigma_{2}\mod
2)}{2}-\frac{q(\sigma_{1}\mod 2)}{2}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle qc_{1}-\frac{\sigma_{2}}{2}-\frac{\sigma_{2}\mod
2}{2}+c_{2}+1<\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q-c_{2}-1-$ $\displaystyle-\frac{\sigma_{2}\mod
2}{2}-\frac{q(\sigma_{1}\mod 2)}{2}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}+1<-\frac{q}{2}$ (45)

In summary, to have $i_{2}^{M}<g_{1}^{m}$ Eq. 45 must hold. On the other hand,
from Eq. 43 and from the hypothesis that
$j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}=\frac{n-q(\Delta_{2}-1)}{2}$ we
obtain:

$qc_{1}-d_{2}+\frac{1}{2}(\sigma_{2}\mod 2)<-\frac{q}{2}.$

Replacing again $d_{2}$ with $\frac{\sigma_{2}+1(\sigma_{2}\mod
2)}{2}-c_{2}-1$, we obtain:

$qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}+1<-\frac{q}{2}.$ (46)

Since Eq. 45 is equivalent to Eq. 46, we can conclude that Eq. 45 holds and
therefore that $i_{2}^{M}<g_{1}^{m}$ and $i_{2}\neq g_{1}$.

Case 2.d: $v_{g_{1}}$ and $v_{i_{2}}$ are spine vertices. Since $v_{g_{1}}$ is
a vertex in the lower part of $\Gamma_{1}$, it must be
$g_{1}=r_{1}+d_{1}(\Delta_{1}-1)$. If $v_{g_{1}}$ coincides with $v_{i_{2}}$,
combining the expression of $g_{1}$ with Eq. 6 we obtain:

$j_{2}-r_{1}=(qd_{1}-c_{2})(\Delta_{2}-1).$ (47)

Concerning $v_{i_{1}}$ $v_{g_{2}}$, we have:

$i_{1}^{m}\leq i_{1}\leq i_{1}^{M};$

and

$g_{2}^{m}\leq g_{2}\leq g_{2}^{M}.$

with $i_{1}^{m}=j_{1}+c_{1}(\Delta_{1}-1)=j_{1}+qc_{1}(\Delta_{2}-1)$,
$g_{2}^{M}=r_{2}+(d_{2}+1)(\Delta_{2}-1)-n$ for some $d_{2}\in\mathbb{N}$ such
that $c_{2}+d_{2}=\left\lceil\frac{\sigma_{2}}{2}\right\rceil-1$, where
$\sigma_{2}$ is the number of spine vertices of $C_{2}$.

We prove that $g_{2}^{M}<i_{1}^{m}$, which implies $g_{2}\neq i_{1}$. To have
$g_{2}^{M}<i_{1}^{m}$ it must be:

$\displaystyle r_{2}+(d_{2}+1)(\Delta_{2}-1)-n<j_{1}+c_{1}(\Delta_{1}-1)$
$\displaystyle r_{2}+(d_{2}+1)(\Delta_{2}-1)-n<j_{1}+qc_{1}(\Delta_{2}-1)$
$\displaystyle r_{2}-j_{1}<(qc_{1}-d_{2}-1)(\Delta_{2}-1)+n(\Delta_{2}-1).$
(48)

Since $r_{l}=j_{l}+\frac{n-(\Delta_{l}-1)(\sigma_{l}\mod 2)}{2}$, for $l=1,2$,
Eq. 47 can be rewritten as:

$j_{2}-j_{1}=(qd_{1}-c_{2})(\Delta_{2}-1)-\frac{q(\Delta_{2}-1)(\sigma_{1}\mod
2)}{2}+\frac{n}{2},$ (49)

while Eq. 48 can be rewritten as:

$j_{2}-j_{1}<(qc_{1}-d_{2}-1)(\Delta_{2}-1)+\frac{(\Delta_{2}-1)(\sigma_{2}\mod
2)}{2}+\frac{n}{2}.$ (50)

Combining Eq. 49 and Eq. 50 we obtain:

$qd_{1}-c_{2}-\frac{q(\sigma_{1}\mod
2)}{2}<(qc_{1}-d_{2}-1)+\frac{(\sigma_{2}\mod 2)}{2}.$

Since $c_{l}+d_{l}=\left\lceil\frac{\sigma_{l}}{2}\right\rceil-1$, we have
$d_{l}=\frac{\sigma_{l}+1(\sigma_{l}\mod 2)}{2}-c_{l}-1$, for $l=1,2$;
replacing $d_{1}$ and $d_{2}$ in the previous equation, we obtain:

$\displaystyle\frac{q\sigma_{1}}{2}+\frac{q(\sigma_{1}\mod
2)}{2}-qc_{1}-q-c_{2}-\frac{q(\sigma_{1}\mod
2)}{2}<qc_{1}-\frac{\sigma_{2}}{2}-\frac{\sigma_{2}\mod 2}{2}+$
$\displaystyle+c_{2}+1-1+\frac{\sigma_{2}\mod 2}{2}$

which, considering that
$\sigma_{2}=\frac{n-2}{\Delta_{2}-1}=\frac{q(n-2)}{\Delta_{1}-1}=q\sigma_{1}$,
implies:

$2\left(qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}\right)>-q$ (51)

In summary, to have $g_{2}^{M}<i_{1}^{m}$ Eq. 51 must hold. On the other hand,
from Eq. 49 and from the hypothesis that
$j_{2}-j_{1}<\frac{n-(\Delta_{1}-1)}{2}=\frac{n-q(\Delta_{2}-1)}{2}$ we
obtain:

$qd_{1}-c_{2}-\frac{q}{2}(\sigma_{1}\mod 2)<-\frac{q}{2}.$

Replacing again $d_{1}$ with $\frac{\sigma_{1}+1(\sigma_{1}\mod
2)}{2}-c_{1}-1$, we obtain:

$2\left(qc_{1}-\frac{q\sigma_{1}}{2}+c_{2}\right)>-q.$ (52)

Since Eq. 51 is equivalent to Eq. 52, we can conclude that Eq. 51 holds and
therefore that $g_{2}^{M}<i_{1}^{m}$ and $g_{2}\neq i_{1}$.

##  Appendix B Proof of Theorem 7

See 7

###### Proof.

Let $C_{1}$, $C_{2}$, and $C_{3}$ be three copies (shown in red, blue and
green, respectively, in Fig. 8) of a $\Delta$-regular caterpillar $C$ with
$4\leq\Delta\leq 7$. We denote the vertices of caterpillar $C_{j}$ for
$j=1,2,3$ as follows; the spine vertices are denoted as
$v^{j}_{0},v^{j}_{1},\dots,v^{j}_{c-1}$ in the order they appear along the
spine; the leaves adjacent to vertex $v^{j}_{i}$ (for $i=1,2,\dots,c-1$) are
denoted as $u^{j}_{i,l}$ with $l=0,1,\dots,d$, where $d=\Delta-2$ if $i=0$ or
$i=c-1$ and $d=\Delta-3$ if $0<i<c-1$.

Let $p_{0},p_{1},\dots,p_{n-1}$ be $n$ points on a circle in clockwise order
(with indices taken modulo $n$). To construct the packing, we compute a
drawing for each caterpillar such that the vertices are mapped to points
$p_{1},p_{2},\dots,p_{n}$ and the union of the three drawings is a $2$-planar
drawing. We describe the construction for $\Delta=4,5,6$ (see also Figs. 8, 8
and 8); the construction in the case $\Delta=7$ is slightly different and it
is shown in Fig. 8.

Caterpillar $C_{1}$ is drawn outside the circle so that vertex $v^{1}_{0}$ is
mapped to point $p_{0}$, each vertex $v^{1}_{i}$, for $i=1,2,\dots,c-1$ is
mapped to $p_{i(\Delta-1)+1}$, each leaf $u^{1}_{0,l}$ is mapped to the point
$p_{l+1}$, and each leaf $u^{1}_{i,l}$ is mapped to the point
$p_{i(\Delta-1)+2+l}$. In other words, each vertex of the spine is followed
clockwise by its leaves and the last of these leaves is followed by the next
vertex of the spine. Caterpillar $C_{2}$ is drawn inside the circle so that
vertex $v^{2}_{i}$ is mapped to the point immediately following clockwise the
point hosting $v^{1}_{i}$ and each leaf $u^{2}_{i,l}$ is mapped to the point
immediately following clockwise $u^{1}_{i,l}$. Clearly, the drawings of the
first two caterpillars do not cross each other because they are on different
sides of the circle; also, their union has no multiple edges. Concerning
$C_{3}$, the vertex $v^{3}_{i}$, for $i=0,1,\dots,c-2$ is mapped to the point
that hosts $u^{1}_{i,d}$ and $u^{2}_{i,d-1}$, i.e., the last leaf of
$v^{1}_{i}$ and the second last leaf of $v^{2}_{i}$; the vertex $v^{3}_{c-1}$
is mapped to the point that hosts $u^{1}_{i,d-1}$ and $u^{2}_{i,d-2}$, i.e.,
the second last leaf of $v^{1}_{c-1}$ and the third last leaf of $v^{2}_{i}$.
About this mapping, observe that if we draw the edges of the spine of $C_{3}$
outside the circle, each edge of the spine of $C_{3}$ intersects two
consecutive edges of the spine of $C_{1}$ and each edge of the spine of
$C_{1}$ intersects at most two consecutive edges of the spine of $C_{3}$. To
complete the drawing, we need to draw the leaves of $C_{3}$. Consider two
consecutive spine vertices $v^{3}_{i}$ and $v^{3}_{i+1}$, with $0\leq i\leq
c-2$; between these two vertices there are $\Delta-2$ points not yet used by
$C_{3}$, we connect the first two of these vertices in clockwise order to
$v_{i}$. Depending on the value of $\Delta$, there remain $0$, $1$, or $2$
points between $v_{i}$ and $v_{i+1}$ not yet used by $C_{3}$; we connect these
points to $v_{i+1}$. Notice that, there remain to map $\Delta-3$ leaves
adjacent to $v^{3}_{0}$ and $3$ leaves adjacent to $v^{3}_{c-1}$. On the other
hand, there are $\Delta$ points not yet used by $C_{3}$ that are between
$v^{3}_{c-1}$ and $v^{3}_{0}$ clockwise; we connect the three vertices
following clockwise $v^{3}_{c-1}$ to $v^{3}_{c-1}$, and the remaining ones to
$v^{3}_{0}$. All the edges of $C_{3}$ that are incident to leaves are drawn
inside the circle. This mapping of $C_{3}$ does not create multiple edges and
gives rise to at most two crossings along the edges of $C_{2}$ and $C_{3}$. ∎

Figure 8:  $2$-planar $3$-placements of $\Delta$-regular caterpillars.