Reeb Lobsters Are 1-Planar

Consider the lobster $G$ shown in Figure 1(a). Assume that $G$ admits a crossing-free drawing $\mathrm{\Gamma }$. Let $G^{\prime }$ be the graph we obtain from $G$ by adding two new independent vertices $x,y$ with $h(x)>h(v)$ and for every $v\in V$ such that $x$ is adjacent exactly to the three vertices with greatest heights and $y$ is adjacent exactly to the three vertices with lowest heights; see Figure 1(b). Then it is easy to extend $\mathrm{\Gamma }$ to a crossing-free drawing of $G^{\prime }$ but $G^{\prime }$ is a $K_{3,3}$-subdivision and thus non-planar; a contradiction. $◀$

Next we show that the local crossing-number of a layered lobster may be arbitrarily large.

For a fixed $k\in \mathbb{N}$ consider the lobster $L$ sketched in Figure 2$(a)$. We call a set $F$ of $l$ edges an $l$-fan if all edges in $F$ share a common endpoint $c$, the remaining endpoints have degree 1 and the heights of these degree-1 endpoints lie either all above $h(c)$ or all below $h(c)$. For each of the four fans in $L$ the heights of the corresponding degree-1 vertices are chosen such that each other vertex either lies below all of them or above all of them. Assume for the sake of contradiction that there exists a drawing $\mathrm{\Gamma }$ of $L$ with at most $k$ crossings per edge. Let $u^{\prime }$ be a degree-1 vertex adjacent to $u$, whose incident edge does not cross an edge incident to $z$; such a vertex exists as there are $3k+1$ degree-1 vertices adjacent to $u$ and the edges incident to $z$ have at most $3k$ crossings. Analogously, there exists a degree-1 vertex $w^{\prime }$ adjacent to $w$ with $h(w^{\prime })>h(w)$, whose incident edge does not cross an edge incident to $z$. Similarly, we can find sets $V^{\prime \prime }$ and $W^{\prime \prime }$ each consisting of $2k+1$ degree-1 vertices adjacent to $v$ and $w$, respectively, that lie below $w$ and whose incident edges do not cross an edge incident to $z$. Let ${\mathrm{\Gamma }}^{\prime }$ denote the drawing induced by $\{u,u^{\prime },v,w,w^{\prime },z\}\cup V^{\prime \prime }\cup W^{\prime \prime }$, where we possibly reroute $zu$ and $zw$ so that they do not cross each other. Note that all edges incident to $z$ are crossing-free in ${\mathrm{\Gamma }}^{\prime }$. Consider the edges $e=u{u}^{\prime }$ and $f=w{w}^{\prime }$. Without loss of generality assume that $zu$ crosses ${\mathrm{\ell }}_w$ left of $w$. Since the path $uzw$ is crossing-free, $f$ crosses ${\mathrm{\ell }}_z$ to the right of $z$ and since $zv$ is crossing-free, $f$ crosses ${\mathrm{\ell }}_v$ to the right of $v$. We distinguish two cases based on whether $e$ crosses ${\mathrm{\ell }}_v$ on the left or on the right side of $v$.

Assume that $e$ crosses ${\mathrm{\ell }}_v$ on the left side of $v$; see Figure 2$(b)$. As $v$ lies between $e$ and $f$ on ${\mathrm{\ell }}_v$ and the edges incident to $z$ are crossing-free in ${\mathrm{\Gamma }}^{\prime }$, each edge connecting $v$ to $V^{\prime \prime }$ crosses $e$ or $f$. Since $|V^{\prime \prime }|=2k+1$, $e$ or $f$ has more than $k$ crossings; a contradiction.

It remains to consider the case where $e$ crosses ${\mathrm{\ell }}_v$ on the right side of $v$; see Figure 2$(c)$. Note that in this case $e$ crosses the horizontal line ${\mathrm{\ell }}_w$ to the right of $w$ since the path $wzv$ is uncrossed. Since the path $zu{u}^{\prime }$ starts and ends above $w$, crosses ${\mathrm{\ell }}_w$ once to the left of $w$ and once to the right of $w$, and $zu$ is crossing-free, all edges connecting $w$ to $W^{\prime \prime }$ cross $e$. Since $|W^{\prime \prime }|=2k+1$ it follows that $e$ has more than $k$ crossings; a contradiction. $◀$

Finally we show that Reeb lobsters admit a drawing with at most one crossing per edge.

Let $L$ be a Reeb graph. We consider an extended spine of $L$; i.e, a path between degree-1 vertices of $L$ that contains the spine. Let $\{v_0,\mathrm{\dots },v_k\}$ be an extended spine of $L$ such that for every the two neighbors of $v_i$ are $v_{i-1}$ and $v_{i+1}$. We start by drawing the extended spine $x$-monotone; see Figure 3 for an illustration. Next we insert all vertices of $L$ that are adjacent to the extended spine crossing-free by assigning each such vertex $u$ an $x$-coordinate close to the $x$-coordinate of its neighbor $v$ on the extended spine. It remains to add the missing leaves of $L$ that have a neighbor that is not adjacent to a vertex on the extended spine. Let $w$ be such a leaf of $L$ with neighbor $u$. Let $v_i$ be the neighbor of $u$ on the extended spine. If $h(v_i)$ does not lie between $h(w)$ and $h(u)$, then we can easily insert $w$ crossing-free by assigning it an $x$-coordinate close to or equal to the $x$-coordinate of $u$. This does not result in a crossing. Hence assume that or $h(w)>h(v_i)>h(u)$. Now we assign $w$ an $x$-coordinate between the $x$-coordinates of $v_i$ and $v_{i-1}$. Then $wu$ crosses the edge $v_i{v}_{i-1}$. Hence by construction for every such leaf $w$, the edge $wu$ receives at most one crossing. Recall that ${\mathrm{deg}}_{\downarrow }(u)\le 2$, ${\mathrm{deg}}_{\uparrow }(u)\le 2$. Thus every $u$ that is neither a leaf of $L$ nor part of the extended spine has at most one neighbor $w$ with or $h(w)>h(v_i)>h(u)$. Hence for every also $v_i{v}_{i-1}$ receives at most one crossing. Thus the construction described above yields a 1-planar drawing of $L$. $◀$