# On asymptotic packing of convex geometric and ordered graphs

Jiaxi Nie Max Planck Institute for Mathematics in the Sciences, Leipzig, 04103
Germany. Email<EMAIL_ADDRESS>Erlang Surya Department of Mathematics,
University of California at San Diego, La Jolla, CA, 92093 USA. Email:
<EMAIL_ADDRESS>Supported by NSF grant DMS-2225631. Ji Zeng Department of
Mathematics, University of California at San Diego, La Jolla, CA, 92093 USA.
Email<EMAIL_ADDRESS>Supported by NSF grant DMS-1800746.

###### Abstract

A convex geometric graph $G$ is said to be packable if there exist edge-
disjoint copies of $G$ in the complete convex geometric graph $K_{n}$ covering
all but $o(n^{2})$ edges. We prove that every convex geometric graph with
cyclic chromatic number at most $4$ is packable. With a similar definition of
packability for ordered graphs, we prove that every ordered graph with
interval chromatic number at most $3$ is packable. Arguments based on the
average length of edges imply these results are best possible. We also
identify a class of convex geometric graphs that are packable due to having
many “long” edges.

##  1 Introduction

For two graphs $G$ and $H$, a _combinatorial $G$-packing_ of $H$ is a
collection of edge-disjoint subgraphs of $H$ that are isomorphic to $G$. In
the study of graph packing, we typically seek the maximum cardinality of a
combinatorial $G$-packing of $H$, denoted by $p(H,G)$. Clearly,
$p(H,G)\leq|E(H)|/|E(G)|$. When equality holds, we call the corresponding
collection a _perfect combinatorial $G$-packing_ of $H$. Due to a well-known
result of Kirkman [13], $K_{n}$ has a perfect combinatorial $K_{3}$-packing if
and only if $n\equiv 1$ or $3\mod 6$. More generally, Wilson [21] proved that,
for $n$ large enough, $K_{n}$ has a perfect combinatorial $G$-packing if and
only if $|E(G)|$ divides $\binom{n}{2}$ and the greatest common divisor of the
vertex degrees of $G$ divides $n-1$. This result is also generalized to
hypergraphs [10, 12].

Although a perfect combinatorial $G$-packing of the complete graph $K_{n}$
doesn’t always exist, we can pack any $G$ into complete graphs “almost
perfectly”. Let us call a graph $G$ _combinatorially packable_ if

$\lim_{n\rightarrow\infty}\frac{p(K_{n},G)|E(G)|}{|E(K_{n})|}=1.$

In other words, $G$ is combinatorially packable if there exist combinatorial
$G$-packings of $K_{n}$ covering all but $o(n^{2})$ edges. Using a technique
known as Rödl Nibble (see Theorem 2.2), one can easily show that all fixed
graphs are combinatorially packable. See [22] for a survey on combinatorial
packing problems.

In this paper, we consider the packability of convex geometric graphs. A
_convex geometric graph_ (shortly _cgg_) $G$ is a graph with a cyclic order
$\prec$ on its vertex set $V(G)$. Equivalently, it can be represented as a
graph drawn in the plane such that $V(G)$ consists of points in convex
position, $E(G)$ consists of straight-line segments connecting the
corresponding points, and $\prec$ is the clockwise ordering of $V(G)$. Two
cgg’s $G$ and $H$ are _isomorphic_ if there is a graph isomorphism $f$ between
them preserving the cyclic order, that is, $u\prec v\prec w$ if and only if
$f(u)\prec f(v)\prec f(w)$. Note that any two complete cgg’s of the same size
are isomorphic, we use $K_{n}$ to denote a complete cgg on $n$ vertices. For
cgg’s $G$ and $H$, a _convex $G$-packing_ (shortly _$G$ -packing_) of $H$ is a
collection of edge-disjoint sub-cgg’s of $H$ that are isomorphic to $G$. We
call a cgg $G$ _convex-packable_ (shortly _packable_) if there exist (convex)
$G$-packings of $K_{n}$ covering all but $o(n^{2})$ edges.

In contrast to combinatorial packability, there exist cgg’s that are not
packable, for example, the plane cycle $C_{5}$ of length $5$. To see why
$C_{5}$ isn’t packable, we can consider the average length of edges. Inside a
cgg $G$, an _interval_ of $V(G)$ is a subset that is contiguous with respect
to $\prec$, and the _length_ $l_{G}(e)$ of an edge $e$ is one less than the
smallest cardinality of an interval containing $e$. One can check that the
average length of all edges in $K_{n}$ is $(1+o(1))n/4$. On the other hand,
the average length of the edges in a copy of $C_{5}$ in $K_{n}$ is at most
$n/5$, so the average length of all edges covered by a $C_{5}$-packing of
$K_{n}$ is at most $n/5$. Hence, a $C_{5}$-packing can never cover all but
$o(n^{2})$ edges of $K_{n}$.

Partly based on this average length argument, Cranston, Nie, Verstraëte, and
Wesolek [8] recently determined all packable plane Hamiltonian cgg’s. See
Figure 1.

Figure 1: All packable plane Hamiltonian cgg’s.

Because the average length of edges in $K_{n}$ is roughly $n/4$, it’s natural
to predict that a cgg is packable if it is “cyclically 4-partite”. Our main
result confirms this prediction. The _cyclic chromatic number_ $\chi_{c}(G)$
of a cgg $G$ is the minimum number of intervals that $V(G)$ can be partitioned
into such that every edge in $E(G)$ has its endpoints in different parts.

######  Theorem 1.1.

Let $G$ be a cgg. If $\chi_{c}(G)\leq 4$, then $G$ is packable.

Theorem 1.1 is best possible since (plane) $C_{5}$ has cyclic chromatic number
$5$ and is not packable. To prove Theorem 1.1, we prove a sufficient condition
for the packability of a cgg (see Lemma 2.1) which is satisfied by all cgg $G$
with $\chi_{c}(G)\leq 4$. The sufficient condition is quite general, and we
also use it to show that some cggs with higher cyclic chromatic numbers can
still be packable if they have many “long” edges. Let
$\mathcal{P}=\\{V_{1},\dots,V_{k}\\}$ be an interval partition of $V(G)$ with
each edge in $E(G)$ having its endpoints in different parts. Since every
$V_{i}$ is an interval, we can define a cyclic order on $\mathcal{P}$ by
setting $V_{i_{1}}\prec V_{i_{2}}\prec V_{i_{3}}$ if $v_{i_{1}}\prec
v_{i_{2}}\prec v_{i_{3}}$ for any $v_{i_{j}}\in V_{i_{j}}$. For each pair
$\\{V_{i},V_{j}\\}$, we use $l_{\mathcal{P}}(\\{V_{i},V_{j}\\})$ to denote the
length of this pair in $\mathcal{P}$, and $E_{G}(V_{i},V_{j})$ to denote the
set of edges between this pair.

######  Theorem 1.2.

For every integer $k>2$ there is an absolute constant $C_{k}$ with the
following property. Suppose $\mathcal{P}=\\{V_{1},\dots,V_{2k}\\}$ is an
interval partition of a cgg $G$ with each edge having its endpoints in
different parts, and $E_{l}$ is the union of all $E_{G}(V_{i},V_{j})$ with
$l_{\mathcal{P}}(\\{V_{i},V_{j}\\})=l$ for $l\in[k]$. If $E_{1}\neq\emptyset$
and $|E_{k}|\geq C_{k}\cdot\sum_{l<k}|E_{l}|$, then $G$ is packable.

We also prove an analogue of Theorem 1.1 for ordered graphs. An ordered graph
is a graph $G$ with a linear order $<$ on $V(G)$. An isomorphism between
ordered graphs is a graph isomorphism preserving the linear order. Packings,
intervals, and lengths are defined similarly for ordered graphs. We say an
ordered graph $G$ is _linearly packable_ (shortly _packable_) if there exist
$G$-packings of the complete ordered graph $K_{n}$ that covers all but
$o(n^{2})$ edges. The _interval chromatic number_ $\chi_{<}(G)$ of an ordered
graph $G$ is the minimum number of intervals that $V(G)$ can be partitioned
into such that every edge in $E(G)$ has its endpoints in different parts.

######  Theorem 1.3.

Let $G$ be an ordered graph. If $\chi_{<}(G)\leq 3$, then $G$ is packable.

Theorem 1.3 is also best possible: the ordered graph $P_{3}$, whose vertices
are $1<2<3<4$ and edges are $\\{1,2\\},\\{2,3\\},\\{3,4\\}$, is not packable.
We give a heuristic explanation of this fact. The average length of all edges
in the complete ordered graph $K_{n}$ is $(1+o(1))n/3$. Although the average
length of the edges in a copy of $P_{3}$ in $K_{n}$ can attain $(1-o(1))n/3$,
it only happens when the head and tail of this copy are very close to the head
and tail of $V(K_{n})$ with respect to $<$. But there are not enough such
$P_{3}$-copies to cover most edges of $K_{n}$.

To end this introduction, we remark that research have been done for packing
problems of (not necessarily convex) geometric graphs [1, 4, 5, 6, 15, 20].
The extremal problems about cgg’s and ordered graphs are also extensively
studied, with many results particularly related to cyclic chromatic numbers
and/or interval chromatic numbers [3, 7, 9, 11, 16].

The rest of this paper is organized as follows. In Section 2, we prove Lemma
2.1 which translates the packing problems of cgg’s into fractional packing
problems of weighted cgg’s. It will be useful to view the fractional packing
problems as linear programming problems. In Section 3 and Section 4, we
establish Theorem 1.1 and Theorem 1.2, by proving the feasibility of their
corresponding linear programs through Farkas’ lemma. In Section 5, we prove
Theorem 1.3 directly using Rödl Nibble. Section 6 lists some final remarks. We
systemically omit floors and ceilings whenever they are not crucial for the
sake of clarity in our presentation.

##  2 Fractional packing of weighted convex geometric graphs

In this section, we prove an auxiliary lemma which relates the packability of
a given cgg to a fractional packing problem of an associated weighted cgg. We
introduce some notions before we state and prove this lemma.

A _weighted cgg_ is a cgg $G$ together with a function
$\omega_{G}:E(G)\to{\mathbb{R}_{\geq 0}}$. A weighted sub-cgg $G$ of $H$ is a
weighted cgg whose underlying cgg structure is a sub-cgg of $H$. An unweighted
cgg $H$ can be seen as a weighted cgg with each edge having weight $1$. An
isomorphism $f:G\to H$ between two weighted cgg’s is a cgg-isomorphism such
that $\omega_{G}(e)=\omega_{H}(f(e))$ for all $e\in E(G)$. We use
$\mathcal{I}(H,G)$ to denote the set of all weighted sub-cgg’s of $H$ that are
isomorphic to $G$. A _perfect fractional $G$-packing_ of $H$ is a function
$\phi:\mathcal{I}(H,G)\to\mathbb{R}_{\geq 0}$ such that

$\displaystyle\sum_{S\in\mathcal{I}(H,G)}\phi(S)\omega_{S}(e)=\omega_{H}(e)\text{
for all $e\in E(H)$}.$ (2.1)

Here, we take the convention that $\omega_{S}(e)=0$ if $e\not\in E(S)$.

For an unweighted cgg $G$ and an interval partition
$\mathcal{P}=\\{V_{1},\dots,V_{k}\\}$ of $V(G)$ with each edge having its
endpoints in different parts, we described in Section 1 that $\mathcal{P}$ has
an induced cyclic order. A _weighted representation_ of $G$ (constructed from
$\mathcal{P}$) is a complete weighted cgg $W$ with vertex set $\mathcal{P}$
and edge weight given by

$\omega_{W}(\\{V_{i},V_{j}\\})=|E_{G}(V_{i},V_{j})|\text{ for every $i\neq
j\in[k]$}.$

See Figure 2 for an example of weighted representations.

Now we state the main result of this section.

######  Lemma 2.1.

Let $G$ and $H$ be two cgg’s. Suppose $\chi_{c}(G)\geq 3$ and $W$ is a
weighted representation of $G$. If $H$ is packable and has a perfect
fractional $W$-packing, then $G$ is packable.

To prove this lemma, we need the following theorem, known as Rödl Nibble [19].
The version stated here is due to Pippenger and Spencer [17], see also [2,
Section 4.7].

######  Theorem 2.2 (Rödl Nibble).

For every integer $r\geq 2$ and real numbers $c\geq 1$ and $\epsilon>0$, there
exist $\gamma=\gamma(r,c,\epsilon)$, $n_{0}=n_{0}(r,c,\epsilon)$ and
$d_{0}=d_{0}(r,c,\epsilon)$ such that for all integers $n\geq n_{0}$ and
$D\geq d_{0}$, the following holds. If $\mathcal{H}=(\mathcal{V},\mathcal{E})$
is an $n$-vertex $r$-uniform hypergraph satisfying

  1. 1.

For all $x\in V$ but at most $\gamma n$ of them, its degree
$d(x)=(1\pm\gamma)D$.

  2. 2.

For all $x\in V$, its degree $d(x)<cD$.

  3. 3.

For any two distinct $x_{1},x_{2}\in V$, their codegree $d(x_{1},x_{2})<\gamma
D$.

Then $\mathcal{H}$ contains a matching of at least $(1-\epsilon)n/r$
hyperedges.

Another ingredient in our proof is the notion of blowups of cgg’s. Given a cgg
$H$ and a positive integer $n$, the _$n$ -regular blowup_ $H[n]$ of $H$ is a
cgg constructed as follows. The vertex set of $H[n]$ consists of $|V(H)|$
intervals, denoted as $\\{I_{v}\\}_{v\in V(H)}$, each of cardinality $n$, and
$I_{v_{1}}\prec I_{v_{2}}\prec I_{v_{3}}$ in $H[n]$ whenever $v_{1}\prec
v_{2}\prec v_{3}$ in $H$; The edge set of $H[n]$ consists of all pairs between
$I_{u}$ and $I_{v}$ whenever $\\{u,v\\}\in E(H)$. See Figure 2 for an example
of blowups.

$1$$1$$1$$1$$2$$0$ Figure 2: A cgg $H$; A weighted representation of $H$; The
blowup $H[2]$.

###### Proof of Lemma 2.1.

We claim that there exist $G$-packings of the blowup $H[n]$ covering all but
$o(n^{2})$ edges. We first prove $G$ is packable given this claim. Take an
arbitrary positive integer $n$. Since $H$ is packable, there exists an
$H$-packing $\mathcal{C}$ of $K_{n}$ that covers all but $o(n^{2})$ edges.
Observe that $\mathcal{C}$ induces an $H[n]$-packing $\mathcal{C}^{\prime}$ of
the blowup $K_{n}[n]$ as follows: if $H^{\prime}\in\mathcal{C}$ is a sub-cgg
of $K_{n}$, then $H^{\prime}[n]$ is naturally a sub-cgg of $K_{n}[n]$ and we
include it in $\mathcal{C}^{\prime}$. For each copy of $H[n]$ in
$\mathcal{C}^{\prime}$, according to the claim, we can use a $G$-packing to
cover all but $o(n^{2})$ of its edges, and consequently obtain a $G$-packing
$\mathcal{C}^{\prime\prime}$ of $K_{n}[n]$. Since $K_{n}[n]$ is a sub-cgg of
$K_{n^{2}}$, we view $\mathcal{C}^{\prime\prime}$ as a $G$-packing of
$K_{n^{2}}$, whose uncovered edges are in either one of the following
categories:

  * •

Edges that are in $K_{n^{2}}$ but not in $K_{n}[n]$. There are $O(n^{3})$ many
of them;

  * •

Edges of $K_{n}[n]$ that are not covered by $\mathcal{C}^{\prime}$. There are
at most $o(n^{2})\cdot n^{2}=o(n^{4})$ of them (the $o(n^{2})$ term
corresponds to edges of $K_{n}$ not covered by $\mathcal{C}$);

  * •

Edges of copies of $H[n]$ in $\mathcal{C}^{\prime}$ that are not covered by
$\mathcal{C}^{\prime\prime}$. There are at most $|\mathcal{C}^{\prime}|\cdot
o(n^{2})=o(n^{4})$ of them (note that
$|\mathcal{C}^{\prime}|<|E(K_{n})|=O(n^{2})$).

Therefore, the $G$-packing $\mathcal{C}^{\prime\prime}$ covers all but
$o(n^{4})$ edges of $K_{n^{2}}$. So $G$ is packable by the arbitrariness of
$n$.

For the rest of this proof, we show the existence of $G$-packings of $H[n]$
covering all but $o(n^{2})$ edges. Let $\mathcal{P}=\\{V_{1},\dots,V_{k}\\}$
be the interval partition from which $W$ is constructed. Note that
$k\geq\chi_{c}(G)\geq 3$. Denote each interval in the blowup $H[n]$
corresponding to a vertex $v\in V(H)$ as $I_{v}$. By assumption, there’s a
function $\phi:\mathcal{I}(H,W)\to\mathbb{R}_{\geq 0}$ satisfying (2.1) for
$W$. We write

$\Phi:=\max_{S\in\mathcal{I}(H,W)}\phi(S)\quad\text{and}\quad
m:=\max\\{|V_{1}|,\dots,|V_{k}|\\}.$

We construct a random hypergraph $\mathcal{H}$ whose vertex set $\mathcal{V}$
consists of all edges of $H[n]$ and edge set $\mathcal{E}$ consists of copies
of $G$ coming from the following random experiment: For each sub-cgg
$G^{\prime}\subset H[n]$ satisfying

  * •

there exists an isomorphism $f:G\to G^{\prime}$ such that there are vertices
$v_{1},\dots,v_{k}\in V(H)$ with $f(V_{i})\subset I_{v_{i}}$, and

  * •

there exists $\delta\in[1,\log n]$ such that for all $i$, every consecutive
pair of vertices in $V(G^{\prime})\cap I_{v_{i}}$ has length $\delta$ in
$H[n]$,

its weighted representation $W^{\prime}$ is naturally a weighted sub-cgg of
$H$ (on vertices $v_{1},\dots,v_{k}$). See Figure 3. We include
$E(G^{\prime})$ into $\mathcal{E}$ as a hyperedge with probability
$\phi(W^{\prime})/\Phi$.

$1$$1$$3$$2$ Figure 3: A sub-cgg $G^{\prime}\subset H[2]$; Its weighted
representation $W^{\prime}\subset H$. (Edges of $H$ and $H[2]$ are not
pictured here but in Figure 2.)

Now we check that $\mathcal{H}$ satisfies the conditions of Rödl Nibble with
high probability.

Take any vertex $x\in\mathcal{V}$ and denote its degree in $\mathcal{H}$ as
$D_{x}$. Write $x=\\{u_{1},u_{2}\\}$ as an edge in $H[n]$. Consider $v_{i}\in
V(H)$ such that $u_{i}\in I_{v_{i}}$ for $i=1,2$ and let
$e:=\\{v_{1},v_{2}\\}\in E(H)$. We say $x$ is _good_ if $u_{1}$ and $u_{2}$
are at least $m\log n$ vertices away from both boundary vertices of the
interval $I_{v_{i}}$. If $x$ is good, then we can compute the expectation

$\mathbb{E}(D_{x})=(1-o(1))\frac{n^{k-2}\log n}{\Phi}.$

Indeed, for each $W^{\prime}\in\mathcal{I}(H,W)$ containing $e$, we count the
number of $G^{\prime}$ in $\mathcal{H}$ whose weighted representation is
$W^{\prime}$ and covering the edge $x\in E(H[n])$. There are $\log n$ choices
for $\delta$, $\omega_{W^{\prime}}(e)$ choices for $f^{-1}(x)$, and
$(1-o(1))n^{k-2}$ choices for vertices in $V(G^{\prime})\cap I_{v}$ with $v\in
V(W^{\prime})\setminus e$. Hence the computation follows from linearity of
expectations, $H$ being unweighted, and (2.1).

If $x$ is not good, there are fewer choices in the above process, so
$\mathbb{E}(D_{x})\leq(1-o(1))n^{k-2}\log n/\Phi$. Moreover, there are at most
$\binom{|V(H)|}{2}(2m\log n)2n=O(n\log n)$ edges of $H[n]$ that are not good.

Take any two distinct vertices $x_{1},x_{2}\in\mathcal{V}$ and denote their
codegree in $\mathcal{H}$ by $D_{x_{1}x_{2}}$. Write
$x_{i}=\\{u_{i1},u_{i2}\\}\in E(H[n])$ and let $v_{ij}\in V(H)$ such that
$u_{ij}\in I_{v_{ij}}$ for $i,j=1,2$. Consider the two edges
$e_{i}=\\{v_{i1},v_{i2}\\}$. If $e_{1}=e_{2}$, we can compute the expectation

$\mathbb{E}(D_{x_{1}x_{2}})\leq(1-o(1))\frac{m^{2}n^{k-2}}{\Phi}.$

Indeed, for each $W^{\prime}\in\mathcal{I}(H,W)$ containing $e:=e_{1}=e_{2}$,
we count the number of $G^{\prime}$ in $\mathcal{H}$ whose weighted
representation is $W^{\prime}$ and covering the edges $x_{1},x_{2}\in
E(H[n])$. There are at most $\omega_{W^{\prime}}(e)$ choices for both
$f^{-1}(x_{1})$ and $f^{-1}(x_{2})$. Note that $\omega_{W^{\prime}}(e)\leq
m^{2}$. However, after those two choices, $\delta$ will be fixed. And there
are still $(1-o(1))n^{k-2}$ choices for vertices in $V(G^{\prime})\cap I_{v}$
with $v\in V(W^{\prime})\setminus e$. Hence the computation follows again.

If $e_{1}\neq e_{2}$, we can check
$\mathbb{E}(D_{e_{1}e_{2}})\leq(1-o(1))m^{2}n^{k-3}\log n/\Phi$ by similar
counting and computation. Essentially, there are fewer choices for vertices in
$V(G^{\prime})\cap I_{v}$ with $v\in V(W^{\prime})\setminus(e_{1}\cup e_{2})$
after $\delta$ is fixed.

Finally, we check these degrees and codegrees are concentrated around their
expectations. Observe that $D_{x}$ is a summation of independent random
variables all taking values from $\\{0,1\\}$. By Chernoff bound ([2, Corollary
A.1.14]), for any $x\in\mathcal{V}$, we have

$\Pr\left(|D_{x}-\mathbb{E}(D_{x})|>\frac{1}{\sqrt{\log
n}}\mathbb{E}(D_{x})\right)<2\exp\left(\frac{-\mathbb{E}(D_{x})}{3\log
n}\right)\leq\exp(-\Omega(n)).$

Here we used $k\geq 3$. On the other hand, there are at most
$\binom{|V(H)|}{2}n^{2}$ many vertices in $\mathcal{V}$. Therefore, by union
bound, the probability that every $x\in\mathcal{V}$ satisfies
$|D_{x}-\mathbb{E}(D_{x})|\leq\mathbb{E}(D_{x})/\sqrt{\log n}$ converges to
$1$ as $n$ tends to infinity. By a similar argument, the probability that
every distinct pair $x_{1},x_{2}\in\mathcal{V}$ satisfies
$D_{x_{1}x_{2}}<2m^{2}n^{k-2}/\Phi$ converges to $1$ as $n$ tends to infinity.

To summarise, we have shown, when $n$ is large enough, $\mathcal{H}$ almost
surely satisfies: All $x\in\mathcal{V}$ but $O(n\log n)$ of them have degree
$d(x)=(1\pm o(1))n^{k-2}\log n/\Phi$; All $x\in\mathcal{V}$ have degree
$d(x)<2n^{k-2}\log n/\Phi$; Any two distinct $x_{1},x_{2}\in\mathcal{V}$ have
codegree $d(x,y)<o(n^{k-2}\log n)$. Thus, there is a realization of
$\mathcal{H}$ that satisfies the conditions of Theorem 2.2, meaning there is a
matching which corresponds to $G$-packings of $H[n]$ covering all but
$o(n^{2})$ edges, as claimed. ∎

##  3 Proof of Theorem 1.1

To prove Theorem 1.1, we need the following lemma.

######  Lemma 3.1.

Let $W$ be a complete weighted cgg on vertices $v_{1}\prec v_{2}\prec
v_{3}\prec v_{4}$ with

$\displaystyle\omega_{W}(\\{v_{1},v_{2}\\})=\omega_{W}(\\{v_{2},v_{3}\\})=\omega_{W}(\\{v_{3},v_{4}\\})=\omega_{W}(\\{v_{4},v_{1}\\})>0,$
$\displaystyle\omega_{W}(\\{v_{1},v_{3}\\})=\omega_{W}(\\{v_{2},v_{4}\\})>0.$

Then there exists some $K_{m}$ having a perfect fractional $W$-packing.

Before we establish this lemma, we first use it to prove Theorem 1.1. For a
complete cgg whose vertices are $v_{1}\prec v_{2}\prec\dots\prec v_{m}$ in
cyclic order, its _rotation_ refers to an automorphism that maps $v_{i}$ to
$v_{i+r}$ for all $i\in[m]$ and some fixed $r\in\mathbb{Z}$, where the indices
are meant modulo $m$.

###### Proof of Theorem 1.1.

Let $G$ be the given cgg. If $\chi_{c}(G)=2$, a result of Brass, Károlyi and
Valtr [7] states that

$\text{ex}_{c}(n,G)=\left(1-\frac{1}{\chi_{c}(G)-1}\right)\binom{n}{2}+o(n^{2})=o(n^{2}),$

where $\text{ex}_{c}(n,G)$ is the maximum number of edges in a cgg on $n$
vertices that doesn’t contain $G$ as a sub-cgg. Clearly, for a $G$-packing of
$K_{n}$ with maximal cardinality, the number of uncovered edges is less than
$\text{ex}_{c}(n,G)$. So for this case we conclude $G$ is packable.

If $\chi_{c}(G)=3$, let $\mathcal{P}$ be an interval partition of $G$ into 3
parts with each edge having its endpoints in different parts, and $W$ the
weighted representation of $G$ constructed from $\mathcal{P}$. Write the
vertices of $W$ as $v_{1}\prec v_{2}\prec v_{3}$, and consider another
weighted cgg $W^{\prime}$ on these vertices with
$\omega_{W^{\prime}}(\\{v_{1},v_{2}\\})$,
$\omega_{W^{\prime}}(\\{v_{2},v_{3}\\})$, and
$\omega_{W^{\prime}}(\\{v_{3},v_{1}\\})$ all equal to

$\omega_{W}(\\{v_{1},v_{2}\\})+\omega_{W}(\\{v_{2},v_{3}\\})+\omega_{W}(\\{v_{3},v_{1}\\}).$

By considering the rotations of $W$, we can see that $W^{\prime}$ has a
perfect fractional $W$-packing. The unweighted triangle $K_{3}$ has a perfect
fractional $W^{\prime}$-packing just by scaling. So $K_{3}$ has a perfect
fractional $W$-packing and because $K_{3}$ is packable (see Figure 1), using
Lemma 2.1 we conclude the theorem.

If $\chi_{c}(G)=4$, let $W$ be a weighted representation of $G$ constructed
from an interval partition with 4 parts. Write the vertices of $W$ as
$v_{1}\prec v_{2}\prec v_{3}\prec v_{4}$ and consider another weighted cgg
$W^{\prime}$ on these vertices such that every edge with length $l$ in
$W^{\prime}$ has weight $w_{l}$, where

$\displaystyle
w_{1}:=\omega_{W}(\\{v_{1},v_{2}\\})+\omega_{W}(\\{v_{2},v_{3}\\})+\omega_{W}(\\{v_{3},v_{4}\\})+\omega_{W}(\\{v_{4},v_{1}\\}),$
$\displaystyle
w_{2}:=2\omega_{W}(\\{v_{1},v_{3}\\})+2\omega_{W}(\\{v_{2},v_{4}\\}).$

Similarly, $W^{\prime}$ has a perfect fractional $W$-packing by rotations.
It’s easy to check that $\chi_{c}(G)=4$ guarantees $w_{1}>0$. If $w_{2}=0$,
then the plane cycle $C_{4}$ of length 4 has a perfect fractional
$W^{\prime}$-packing just by scaling. So $C_{4}$ has a perfect fractional
$W$-packing and because $C_{4}$ is packable (see Figure 1), by Lemma 2.1 we
are done. If $w_{2}>0$, by Lemma 3.1, a complete cgg $K_{m}$ has a perfect
fractional $W^{\prime}$-packing, hence $K_{m}$ also has a perfect fractional
$W$-packing. Then we conclude Theorem 1.1 by Lemma 2.1 and the next
observation. ∎

######  Observation 3.2.

Any complete (unweighted) cgg $K_{m}$ is packable.

###### Proof.

Since every abstract graph is combinatorially packable, there are
combinatorial $K_{m}$-packings of $K_{n}$ that cover all but $o(n^{2})$ edges.
But we know that all complete cgg’s of the same size are isomorphic to each
other, so such combinatorial $K_{m}$-packings are also convex
$K_{m}$-packings. ∎

The remainder of the section is dedicated to the proof of Lemma 3.1, which is
based on the well-known Farkas’ lemma [14].

######  Lemma 3.3 (Farkas’ Lemma).

Let $M\in\mathbb{R}^{a\times b}$ and $z\in\mathbb{R}^{a}$. Then exactly one of
the following two assertions is true:

  1. 1.

There exists $x\in\mathbb{R}^{b}$ such that $x\geq 0$ and $Mx=z$.

  2. 2.

There exists $y\in\mathbb{R}^{a}$ such that $z^{T}y<0$ and $M^{T}y\geq 0$.

To approach Lemma 3.1 using the Farkas’ lemma, we define the following matrix:
Two sub-cgg’s $S_{1},S_{2}\in\mathcal{I}(K_{m},W)$ are _rotationally
equivalent_ if there is a rotation of $K_{m}$ that transforms $S_{1}$ to
$S_{2}$. For every $S\in\mathcal{I}(K_{m},W)$, we denote its rotational
equivalence class by $\overline{S}$. Let $M_{K_{m},W}$ be the matrix whose
rows are indexed by all possible edge-lengths in $K_{m}$, and columns indexed
by rotational equivalence classes in $\mathcal{I}(K_{m},W)$, and set

$M_{K_{m},W}(l,\overline{S})=\sum_{e\in E(S);l_{K_{m}}(e)=l}\omega_{S}(e).$
(3.1)

######  Observation 3.4.

If $m$ is odd and there exists a vector $x\geq 0$ such that
$M_{K_{m},W}x=\vec{1}$, then $K_{m}$ has a perfect fractional $W$-packing.

###### Proof.

For every $S\in\mathcal{I}(K_{m},W)$, let $\phi(S)$ be the entry of $x$
indexed by $\overline{S}$. Observe that for any two edges $e_{1},e_{2}\in
E(K_{m})$ having the same length, there’s a unique rotation that transforms
$e_{1}$ to $e_{2}$. (This requires $m$ to be odd.) Also note that every edge
of $K_{m}$ has weight 1. We can check that $M_{K_{m},W}x=\vec{1}$ is
equivalent to (2.1). ∎

###### Proof of Lemma 3.1.

Write the weight of length-$l$ edges in $W$ as $w_{l}$ for $l=1,2$, and set

$m=2m^{\prime}+1\text{\quad
with\quad}m^{\prime}=\left\lceil\frac{12(w_{1}+w_{2})^{2}}{w_{1}w_{2}}\right\rceil.$

Note that $m^{\prime}$ is the largest edge-length in $K_{m}$. For the rest of
this proof, all the edge-lengths are defined in $K_{m}$.

By Observation 3.4, it suffices to show there exists some vector $x\geq 0$
with $M_{K_{m},W}x=\vec{1}$. For the sake of contradiction, suppose there’s no
such $x$. By Lemma 3.3, there exists $y\in\mathbb{R}^{m^{\prime}}$ such that

  * •

$\sum^{m^{\prime}}_{i=1}y_{i}=(\vec{1})^{T}\cdot y<0$; and

  * •

For any $S\in\mathcal{I}(K_{m},W)$, whose $w_{1}$-weighted edges have lengths
$i_{1},i_{2},i_{3},i_{4}$ and $w_{2}$-weighted edges have lengths
$i_{5},i_{6}$, we have

$y(\overline{S}):=w_{1}(y_{i_{1}}+y_{i_{2}}+y_{i_{3}}+y_{i_{4}})+w_{2}(y_{i_{5}}+y_{i_{6}})=(M^{T}_{K_{m},W}\cdot
y)_{\overline{S}}\geq 0.$

Let $I:=\\{i\in[m^{\prime}];y_{i}<0\\}$, $N=\sum_{i\in I}y_{i}$ and
$P=\sum_{i\not\in I}y_{i}$. Then we have $N+P<0$.

Let $i_{max}$ be the maximum element in $I$. For each $i\in I\setminus
i_{max}$, choose $S_{i}\in\mathcal{I}(K_{m},W)$ such that its $w_{1}$-weighted
edges have lengths $i,i_{max}-i,i,\min\\{i_{max}+i,m-i_{max}-i\\}$ following
the cyclic order. See Figure 4. Note that $\overline{S_{i}}$ is uniquely
determined in this way. Consider all the edges from all chosen $S_{i}$: for
each $i\in I\setminus i_{max}$, there are at least two $w_{1}$-weighted edges
having length $i$; for each $j\in[m^{\prime}]\setminus I$, there are at most
two $w_{1}$-weighted edges having length $j$ (notice that $j$ is not equal to
both $i_{max}+i_{1}$ and $i_{max}-i_{2}$ for $i_{1},i_{2}\in I$); there are
$2(|I|-1)$ many $w_{2}$-weighted edges having length $i_{max}$. So we have

$\displaystyle\sum_{i\in I\setminus i_{max}}y(\overline{S_{i}})$
$\displaystyle\leq 2w_{1}(N-y_{i_{max}})+2w_{1}P+2(|I|-1)w_{2}y_{i_{max}}$
$\displaystyle<2((|I|-1)w_{2}-w_{1})y_{i_{max}},$

where the last inequality holds since $N+P<0$.

$i_{max}-i$$i$$i$$\min\\{i_{max}+i,m-i_{max}-i\\}$$i_{max}$$i_{max}$$i_{0}$$i$$i$$i_{0}+2i$$i_{0}+i$$i_{0}+i$$i_{0}-2i$$i$$i$$i_{0}$$i_{0}-i$$i_{0}-i$

Figure 4: Configurations of $S_{i}$, $S^{\prime}_{i}$, and
$S^{\prime\prime}_{i}$. Numbers represent the edge-lengths.

Now, by the inequality above and the assumption $y(\overline{S_{i}})\geq 0$,
we conclude $(|I|-1)w_{2}-w_{1}<0$, so $|I|<\frac{w_{1}+w_{2}}{w_{2}}$. By the
pigeonhole principle, there exists $i_{0}\in I$ such that
$y_{i_{0}}<\frac{w_{2}}{w_{1}+w_{2}}N$.

If $i_{0}\leq m^{\prime}/2$, for each $1\leq i\leq m^{\prime}/4$, we choose
$S^{\prime}_{i}\in\mathcal{I}(K_{m},W)$ such that its $w_{1}$-weighted edges
have lengths $i,i_{0},i,i_{0}+2i$ following the cyclic order. See Figure 4.
Then $\overline{S^{\prime}_{i}}$ is uniquely determined and a similar analysis
of the edge-lengths gives

$\sum_{i=1}^{m^{\prime}/4}y(\overline{S^{\prime}_{i}})\leq\frac{m^{\prime}}{4}w_{1}y_{i_{0}}+3(w_{1}+w_{2})P<\frac{m^{\prime}}{4}\frac{w_{1}w_{2}}{w_{1}+w_{2}}N+3(w_{1}+w_{2})P<0,$

where the last inequality is by the value of $m^{\prime}$ and $N+P<0$. This
contradicts the assumption that $y(\overline{S^{\prime}_{i}})\geq 0$ for all
possible $i$.

If $i_{0}>m^{\prime}/2$, for each $1\leq i\leq m^{\prime}/4$, we choose
$S^{\prime\prime}_{i}\in\mathcal{I}(K_{m},W)$ such that its $w_{1}$-weighted
edges have lengths $i,i_{0},i,i_{0}-2i$ following the cyclic order. See Figure
4. Then $\overline{S^{\prime\prime}_{i}}$ is uniquely determined and a similar
analysis of the edge-lengths gives

$\sum_{i=1}^{m^{\prime}/4}y(\overline{S^{\prime\prime}_{i}})\leq\frac{m^{\prime}}{4}w_{1}y_{i_{0}}+3(w_{1}+w_{2})P<\frac{m^{\prime}}{4}\frac{w_{1}w_{2}}{w_{1}+w_{2}}N+3(w_{1}+w_{2})P<0,$

where the last inequality is by the value of $m^{\prime}$ and $N+P<0$. This is
also a contradiction, hence we conclude the proof. ∎

##  4 Proof of Theorem 1.2

The proof of Theorem 1.2 is based on the following lemma.

######  Lemma 4.1.

For every integer $k>2$ there is an absolute constant $C_{k}$ with the
following property. Suppose $W$ is a complete weighted cgg on $2k$ vertices
with every length-$l$ edge having weight $w_{l}$. If $w_{1}>0$ and $w_{k}\geq
C_{k}\sum_{l<k}w_{l}$, then there exists some $K_{m}$ having a perfect
fractional $W$-packing.

###### Proof of Theorem 1.2.

Let $C_{k}$ be as concluded by Lemma 4.1. Recall that we wish to prove any cgg
$G$ satisfying

$E_{1}\neq\emptyset\text{ and }|E_{k}|\geq C_{k}\cdot\sum_{l<k}|E_{l}|$

is packable. Here $\\{E_{l};l=1,\dots,k\\}$ are the edge collections
associated with an interval partition $\mathcal{P}=\\{V_{1},\dots,V_{2k}\\}$
as described in the statement of this theorem.

Denote the weighted representation of $G$ constructed from $\mathcal{P}$ as
$W$ and its vertices as $v_{1}\prec\dots\prec v_{2k}$ ($k>2$). Consider
another weighted cgg $W^{\prime}$ on these vertices such that every edge with
length $l$ in $W^{\prime}$ has weight $w_{l}$, where

$w_{k}=2\times\sum_{l_{W}(e)=k}\omega_{W}(e)\text{\quad
and\quad}w_{l}=\sum_{l_{W}(e)=l}\omega_{W}(e)\text{\quad for all
$l=1,\dots,k-1$}.$

By considering the rotations of $W$, we can check that $W^{\prime}$ has a
perfect fractional $W$-packing. Observe that we have $w_{k}=2|E_{k}|$ and
$w_{l}=|E_{l}|$ for $1\leq l<k$. Then by hypothesis and Lemma 4.1, some
$K_{m}$ has a perfect fractional $W^{\prime}$-packing, hence also a perfect
fractional $W$-packing. So we conclude the proof by Observation 3.2 and Lemma
2.1.∎

###### Proof of Lemma 4.1.

Let $C_{k}=16k$ and $W$ be as described. Note that $k$ is the largest edge-
length in $W$. We take

$m=2m^{\prime}+1\text{\quad with\quad}m^{\prime}=\left\lceil
24k^{3}w_{1}^{-1}\sum_{l=1}^{k}w_{l}\right\rceil.$

Note that $m^{\prime}$ is the largest edge-length in $K_{m}$. For the rest of
this proof, all the edge-lengths are defined in $K_{m}$.

By Observation 3.4, it suffices to show there exists some vector $x\geq 0$
with $M_{K_{m},W}x=\vec{1}$ for $M_{K_{m},W}$ defined in (3.1). For the sake
of contradiction, suppose there’s no such $x$, by Lemma 3.3, there exists
$y\in\mathbb{R}^{m^{\prime}}$ such that

  * •

$\sum^{m^{\prime}}_{i=1}y_{i}=(\vec{1})^{T}\cdot y<0$;

  * •

For any $S\in\mathcal{I}(K_{m},W)$, we have

$y(\overline{S}):=\sum_{e\in E(S)}\omega_{S}(e)\cdot
y_{l_{K_{m}}(e)}=(M^{T}_{K_{m},W}\cdot y)(\overline{S})\geq 0.$

Let $I:=\\{i\in[m^{\prime}];y_{i}<0\\}$, $N=\sum_{i\in I}y_{i}$, and
$P=\sum_{i\not\in I}y_{i}$. Then we have $N+P<0$. Also, write
$I^{\prime}=\\{i\in I;i<k\\}$ and $N^{\prime}=\sum_{i\in I^{\prime}}y_{i}$.

For each $i\in I\setminus I^{\prime}$, write $i=kq_{i}+r_{i}$ uniquely with
integers $q_{i}>0$ and $0\leq r_{i}<k$. We choose
$S_{i}\in\mathcal{I}(K_{m},W)$ such that the lengths of its $w_{1}$-weighted
edges listed following the cyclic order are

$\underbrace{q_{i},q_{i},\dots,q_{i}}_{\text{$k-1$ times}}\ ,\ q_{i}+r_{i}\ ,\
\underbrace{q_{i},q_{i},\dots,q_{i}}_{\text{$k-1$ times}}\ ,\
\min\\{2i-q_{i}-r_{i},m-(2i-q_{i}-r_{i})\\}.$

See Figure 5. Note that $\overline{S_{i}}$ is uniquely determined in this way.

$q_{i}+r_{i}$$q_{i}$$q_{i}$$q_{i}$$q_{i}$$\min\\{5q_{i}+r_{i},m-5q_{i}-r_{i}\\}$$i$$j$$j$$j$$j$$i+4j$
Figure 5: Configurations of $S_{i}$ and $S_{ij}$ for $k=3$. Numbers represent
the edge-lengths.

Observe that all $w_{k}$-weighted edges of $S_{i}$ have length $i$ and there
are $k$ many of them. On the other hand, for any $l\in[k]$, every
$w_{l}$-weighted edge of $S_{i}$ has length equal to either $lq_{i}$, or
$lq_{i}+r_{i}$, or $i+(k-l)q_{i}$, or $m-(i+(k-l)q_{i})$. And for each such
value, there are at most $2k$ many such edges of $S_{i}$ having it as their
length. Hence we can check, among all chosen $S_{i}$, there are at most
$8k^{2}$ many $w_{l}$-weighted edges having length $j$ for each
$j\in[m^{\prime}]\setminus I$. Overall we have

$\displaystyle\sum_{i\in I\setminus I^{\prime}}y(\overline{S_{i}})$
$\displaystyle\leq kw_{k}(N-N^{\prime})+8k^{2}\sum_{l<k}w_{l}P$
$\displaystyle=kw_{k}\left(\frac{1}{2}N-N^{\prime}+\frac{1}{2}N\right)+8k^{2}\sum_{l<k}w_{l}P$
$\displaystyle\leq
kw_{k}\left(\frac{1}{2}N-N^{\prime}\right)+\frac{1}{2}kC_{k}\sum_{l<k}w_{l}N+8k^{2}\sum_{l<k}w_{l}P$
$\displaystyle<kw_{k}\left(\frac{1}{2}N-N^{\prime}\right),$

where the last inequality is by the value of $C_{k}$ and $N+P<0$.

Now, by the inequality above and the assumption $y(\overline{S_{i}})\geq 0$,
we conclude $N^{\prime}<N/2$. For each $i\in I^{\prime}$ and
$j\leq\frac{m^{\prime}}{2k}$, we choose $S_{ij}\in\mathcal{I}(K_{m},W)$ such
that the lengths of its $w_{1}$-weighted edges listed following the cyclic
order are

$\underbrace{j,j,\dots,j}_{\text{$k-1$ times}}\ ,\ i\ ,\
\underbrace{j,j,\dots,j}_{\text{$k-1$ times}}\ ,\ i+(2k-2)j.$

See Figure 5. Note that $i+(2k-2)j\leq m^{\prime}$ in this definition. Again,
$\overline{S_{ij}}$ is uniquely determined and a similar analysis of the edge-
lengths gives

$\sum_{j=1}^{m^{\prime}/2k}y(\overline{S_{ij}})\leq\frac{m^{\prime}}{2k}w_{1}y_{i}+6k\sum_{l}w_{l}P.$

Hence, as $|I^{\prime}|<k$ and $N^{\prime}<N/2$, we have

$\sum_{i\in
I^{\prime}}\sum_{j=1}^{m^{\prime}/2k}y(\overline{S_{ij}})<\frac{m^{\prime}}{2k}w_{1}N^{\prime}+6k^{2}\sum_{l}w_{l}P<\frac{m^{\prime}}{2k}w_{1}\frac{N}{2}+6k^{2}\sum_{l}w_{l}P<0,$

where the last inequality is by the value of $m^{\prime}$ and $N+P<0$. This
contradicts the assumption that $y(\overline{S_{ij}})\geq 0$ for all $S_{ij}$,
so we conclude the proof. ∎

##  5 Proof of Theorem 1.3

Some details of this proof are abridged due to their similarity to previous
arguments.

###### Proof of Theorem 1.3.

Let $G$ be the given ordered graph. If $\chi_{<}(G)=2$, a result of Pach and
Tardos [16] states that

$\text{ex}_{<}(n,G)=\left(1-\frac{1}{\chi_{<}(G)-1}\right)\binom{n}{2}+o(n^{2})=o(n^{2}),$

where $\text{ex}_{<}(n,G)$ is the maximum number of edges in a $n$-vertex
ordered graph that doesn’t contain $G$ as an ordered subgraph. Similar to the
$\chi_{c}(G)=2$ case in Theorem 1.1, we conclude $G$ is packable.

If $\chi_{<}(G)=3$, let $\\{V_{1},V_{2},V_{3}\\}$ be an interval partition of
$V(G)$ with every edge in $E(G)$ having endpoints in different parts. Write
$e_{ij}=|E_{G}(V_{i},V_{j})|$ for $1\leq i<j\leq 3$. For each positive integer
$n$, the _irregular blow-up_ $\tilde{K}_{3}[n]$ is an ordered graph defined as
follows: the vertex set $V(\tilde{K}_{3}[n])$ consists of three intervals
$I_{1},I_{2},I_{3}$ in order, of size $e_{12}e_{13}n$, $e_{12}e_{23}n$,
$e_{13}e_{23}n$ respectively; the edge set $E(\tilde{K}_{3}[n])$ consists of
all pairs with endpoints in different parts.

First we prove that given arbitrary $\epsilon>0$, there exists $n_{\epsilon}$
such that, for all $n\geq n_{\epsilon}$ there is a $G$-packing of
$\tilde{K}_{3}[n]$ covering all but an $\epsilon$-fraction of edges. Consider
the hypergraph $\mathcal{H}$ whose vertex set $\mathcal{V}$ consists of all
edges of $\tilde{K}_{3}[n]$ and edge set $\mathcal{E}$ consists of all
$E(G^{\prime})$ where $G^{\prime}$ is a subgraph of $\tilde{K}_{3}[n]$
satisfying

  * •

there exists an isomorphism $f:G\to G^{\prime}$ such that with
$f(V_{i})\subset I_{i}$ for $i=1,2,3$; and

  * •

there exists $\delta\in[1,\log n]$ such that for $i=1,2,3$, every consecutive
pair of vertices in $V(G^{\prime})\cap I_{i}$ has length $\delta$ in
$\tilde{K}_{3}[n]$,

Using similar arguments as in the proof of Lemma 2.1, we can check inside
$\mathcal{H}$: All $x\in\mathcal{V}$ but $O(n\log n)$ of them have degree
$d(x)=(1\pm o(1))e_{12}e_{13}e_{23}n\log n$; All $x\in\mathcal{V}$ have degree
$d(x)<2e_{12}e_{13}e_{23}n\log n$; Any two distinct
$x_{1},x_{2}\in\mathcal{V}$ have codegree $d(x,y)<O(e_{12}e_{13}e_{23}n)$.
Therefore, by Theorem 2.2, there exists $n_{\epsilon}$ with the claimed
property.

Now we fix an arbitrary $\epsilon>0$ and describe a recursive construction of
a $G$-packing of $K_{n}$. Firstly, we partition $V(K_{n})$ into four intervals
$I_{1},I_{2},I_{3},I_{4}$ in order, where $I_{1},I_{2},I_{3}$ have sizes
$e_{12}e_{13}n^{\prime}$, $e_{12}e_{23}n^{\prime}$, $e_{13}e_{23}n^{\prime}$
respectively, for a unique $n^{\prime}$ such that $I_{4}$ has size less than
$q:=e_{12}e_{13}+e_{12}e_{23}+e_{13}e_{23}$. Then we can regard the subgraph
of $K_{n}$ with vertices $I_{1}\cup I_{2}\cup I_{3}$ and edges
$E_{K_{n}}(I_{1},I_{2})\cup E_{K_{n}}(I_{1},I_{3})\cup E_{K_{n}}(I_{2},I_{3})$
as $\tilde{K}_{3}[n^{\prime}]$. If $n^{\prime}<n_{\epsilon}$, we do nothing
and end this construction. Otherwise, we find a $G$-packing of this
$\tilde{K}_{3}[n^{\prime}]$ that covers all but an $\epsilon$-fraction of
edges, and we recursively repeat this process on the induced subgraphs on
$I_{1},I_{2},I_{3}$ respectively. Finally, collecting all the produced edge-
disjoint $G$-copies gives the resulting $G$-packing of $K_{n}$.

For $n$ sufficiently large, the uncovered edges of above $G$-packing are in
either one of the following categories:

  * •

Edges with a endpoint in $I_{4}$ at some stage. There are $O(n\log n)$ many of
them;

  * •

Edges in some $\tilde{K}_{3}[n^{\prime}]$ with $n^{\prime}<n_{\epsilon}$.
There are at most $\frac{n}{qn_{\epsilon}}\binom{qn_{\epsilon}}{2}=O(n)$ many
of them.

  * •

Edges in some $\tilde{K}_{3}[n^{\prime}]$ with $n^{\prime}\geq n_{\epsilon}$
but not covered by the constructed $G$-packing. There are at most
$\epsilon\binom{n}{2}$ many of them.

Therefore, there exists a $G$-packing of $K_{n}$ covering all but $\epsilon
n^{2}$ edges. By the arbitrariness of $\epsilon$, we conclude that $G$ is
packable. ∎

##  6 Final remarks

1\. There is a polynomial time randomized greedy algorithm for the concluded
matching in Theorem 2.2 [18]. It is also well-known that linear programs are
solvable in polynomial time [14, Chapter 7]. Hence there exist polynomial time
randomized algorithms for the packings asserted by our theorems.

2\. We believe our methods could also prove Theorem 1.2 where the interval
partition $\mathcal{P}$ has an odd size. But such a proof probably requires
new constructions like $S_{i}\in\mathcal{I}(K_{m},W)$ in Lemma 4.1.

3\. Is it true that for any cgg $G$ with $\chi_{c}(G)=k\geq 5$, there exist
$G$-packings of $K_{n}$ covering a $(1-o(1))4/k$-fraction of edges? If this is
possible, it is going to be asymptotically tight, by an average length
argument.

Acknowledgement. We want to thank Daniel Cranston, Andrew Suk, Jacques
Verstraëte, Alexandra Wesolek, and Yunkun Zhou for helpful discussions. We
also wish to thank every organizers of Graduate Student Combinatorics
Conference 2022 where this work is initiated.

## References

  * [1] O. Aichholzer, T. Hackl, M. Korman, M. Van Kreveld, M. Löffler, A. Pilz, B. Speckmann, and E. Welzl.  Packing plane spanning trees and paths in complete geometric graphs.  Information Processing Letters, 124:35–41, 2017.
  * [2] N. Alon and J. H. Spencer.  The Probabilistic Method.  John Wiley & Sons, New Jersey, 4th edition, 2016.
  * [3] M. Axenovich, J. Rollin, and T. Ueckerdt.  Chromatic number of ordered graphs with forbidden ordered subgraphs.  Combinatorica, 38(5):1021–1043, 2018.
  * [4] F. Bernhart and P. C. Kainen.  The book thickness of a graph.  Journal of Combinatorial Theory, Series B, 27(3):320–331, 1979\.
  * [5] A. Biniaz and A. García.  Packing plane spanning trees into a point set.  Computational Geometry, 90:101653, 2020.
  * [6] P. Bose, F. Hurtado, E. Rivera-Campo, and D. R. Wood.  Partitions of complete geometric graphs into plane trees.  Computational Geometry, 34(2):116–125, 2006.
  * [7] P. Brass, G. Károlyi, and P. Valtr.  A Turán-type extremal theory of convex geometric graphs.  In Discrete and computational geometry: The Goodman-Pollack Festschrift, pages 275–300. Springer, 2003.
  * [8] D. W. Cranston, J. Nie, J. Verstraëte, and A. Wesolek.  On asymptotic packing of geometric graphs.  arXiv preprint arXiv:2111.03933, 2021.
  * [9] Z. Füredi, A. Kostochka, D. Mubayi, and J. Verstraëte.  Ordered and convex geometric trees with linear extremal function.  Discrete & Computational Geometry, 64(2):324–338, 2020.
  * [10] S. Glock, D. Kühn, A. Lo, and D. Osthus.  The existence of designs via iterative absorption: hypergraph $f$-designs for arbitrary $f$.  arXiv preprint arXiv:1611.06827, 2016.
  * [11] E. Győri, D. Korándi, A. Methuku, I. Tomon, C. Tompkins, and M. Vizer.  On the Turán number of some ordered even cycles.  European Journal of Combinatorics, 73:81–88, 2018.
  * [12] P. Keevash.  The existence of designs.  arXiv preprint arXiv:1401.3665, 2014.
  * [13] T. P. Kirkman.  On a problem in combinations.  Cambridge and Dublin Mathematical Journal, 2:191–204, 1847.
  * [14] J. Matoušek and B. Gärtner.  Understanding and using linear programming.  Springer Science & Business Media, 2006.
  * [15] J. Obenaus and J. Orthaber.  Edge partitions of complete geometric graphs (part 1).  arXiv preprint arXiv:2108.05159, 2021.
  * [16] J. Pach and G. Tardos.  Forbidden paths and cycles in ordered graphs and matrices.  Israel Journal of Mathematics, 155(1):359–380, 2006.
  * [17] N. Pippenger and J. Spencer.  Asymptotic behavior of the chromatic index for hypergraphs.  Journal of Combinatorial Theory, Series A, 51(1):24–42, 1989.
  * [18] V. Rödl and L. Thoma.  Asymptotic packing and the random greedy algorithm.  Random Structures & Algorithms, 8(3):161–177, 1996.
  * [19] V. Rödl.  On a packing and covering problem.  European Journal of Combinatorics, 6(1):69–78, 1985.
  * [20] H. M. Trao, G. L. Chia, N. A. Ali, and A. Kilicman.  On edge-partitioning of complete geometric graphs into plane trees.  arXiv preprint arXiv:1906.05598, 2019.
  * [21] R. M. Wilson.  Decompositions of complete graphs into subgraphs isomorphic to a given graph.  In Proc. 5th British Combinatorial Conf., 1975.
  * [22] R. Yuster.  Combinatorial and computational aspects of graph packing and graph decomposition.  Computer Science Review, 1(1):12–26, 2007.