Defective Linear Layouts of Graphs

Let $ℒ$ be a $k$-defective $h$-queue layout of a graph $G$ with $n$ vertices and $m$ edges. Classes with at most $h(k+2)$ edges are small, otherwise are large. Let $n_l$ be the number of large classes, and $m_s$ the number of edges in small classes. We claim $m\le n_{l}h(k+2)+m_s$. Suppose, for contradiction, that $m>n_{l}h(k+2)+m_s$. Then some large class must have more than $h(k+2)$ edges, implying a queue with more than $k+2$ edges from that class, contradicting Lemma 1. Since each class has at most $i$ edges, we have $n_l=n-1-h(k+2)$, and $m_s\le {\sum }_{i=1}^{h(k+2)}i=\frac{h(k+2)(h(k+2)+1)}{2}$. Therefore, $m\le (n-1-h(k+2))h(k+2)+\frac{h(k+2)(h(k+2)+1)}{2}=h(k+2)\left(n-\frac{h(k+2)+1}{2}\right)$. Finally, $h(k+2)\left(n-\frac{h(k+2)+1}{2}\right)\le \frac{n(n-1)}{2}$ for $n\ge h(k+2)+1$. $◀$ We next consider defectiveness and queue number. In this content, outerplanar graphs have queue number 2 [7], but not all admit $1$-queue layouts with bounded defectiveness. Outer $1$-planar graphs have queue number at most 42 [2]; we show that their $1$-defective queue number is 2, so their queue number is at most 3.
For general planar graphs, we can prove an upper bound of $33$ on their $1$-defective queue number by adapting a well-known technique by Dujmovic et al. [4].
We next establish bounds on the $k$-defective queue number of $K_n$ that are tight for $k=1$.

For the lower bound, consider a $k$-defective queue layout $ℒ$ of $K_n$. The edges can be partitioned into classes $C_1,\mathrm{\dots },C_{n-1}$. Since $C_{n-1}$ has $n-1$ edges and at most $k+2$ edges can share a defective queue (Lemma 1), at least $\lceil \frac{n-1}{k+2}\rceil$ queues are needed. We prove the upper bound via an explicit construction. For $h$ to be specified, assign to each defective queue $q_a$ (for $0\le a\le h$) all edges with hop-size $al+i$ for $1\le i\le l$. The edges with the most nestings are the $(al+l)$-hop edges, each nesting $\frac{1}{2}(l-2)(l-1)$ edges, ensuring the layout is $k$-defective. To cover all $\frac{n(n-1)}{2}$ edges of $K_n$, note that each $q_a$ contains ${\sum }_{i=1}^l(n-(al+i))$ edges. For $h=\lceil \frac{n-1}{l}\rceil$, the total edges assigned satisfy ${\sum }_{a=0}^{h-1}{\sum }_{i=1}^l(n-(al+i))\ge \frac{n(n-1)}{2}$. $◀$ We give bounds on the $k$-defective queue number of $K_{n,n}$, considering both the general case and the separated setting, where one part precedes the other [1].