Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?

Question

A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are mutually crossed.

Let $\mathcal{D}$ be a 1-planar drawing of a 1-planar graph $G$ that has the minimum number of crossings, i.e, the number of crossings in $\mathcal{D}$ is exactly the crossing number of $G$. Is it possible that every edge of $\mathcal{D}$ is crossed?

I think this is impossible, however, didn't find any proof to support this. My try is to prove this by a contradiciton argument.

Suppose every edge of $\mathcal{D}$ is crossed. It follows that the number of edges is twice of the number of crossings. So $e(G)=2cr(G)$. I know that $cr(G)\leq v(G)-2$, and thus $e(G)\leq 2v(G)-4$. Nevertheless, this is not a contradiciton to complete the proof.

So how can I move on?

Answer 1

It is not possible that in an optimal drawing of a 1-planar graph, every edge is crossed. Here is a proof.

Suppose not and let $G$ be a smallest counterexample. I claim that $G$ is 2-connected. If not, then $G$ has edge-disjoint subgraphs $G_1$ and $G_2$ with $G_1 \cup G_2=G$, $|V(G_1) \cap V(G_2)| \leq 1$, and $|V(G_1)|, |V(G_2)| < |V(G)|$. By the minimality of $G$, $G_1$ and $G_2$ have 1-planar drawings $D_1$ and $D_2$ such that at least one edge of $G_1$ and at least one edge of $G_2$ is not crossed. If $V(G_1) \cap V(G_2):=\{v\}$, let $F$ be a face of $D_1$ which contains $v$. Otherwise, let $F$ be an arbitrary face of $D_1$. Placing $D_2$ inside $F$ gives a 1-planar drawing of $G$ where at least two edges are not crossed, which is a contradiction.

Now let $D$ be a drawing of $G$ where every edge is crossed exactly once. Place a dummy vertex at each crossing to produce a planar graph $D^\times$. I claim that $D^\times$ is also 2-connected. Clearly, removing a non-dummy vertex cannot disconnect $D^\times$, since $G$ is 2-connected. Suppose $D^\times - x$ is disconnected for some dummy vertex $x$. Let $e$ and $f$ be the edges of $G$ which cross at $x$. Thus, $D-\{e,f\}$ is disconnected. Thus, we can redraw $e$ and $f$ in $D$ so that they do not cross, which is a contradiction.

Since $D^\times$ is 2-connected, the outerface $O$ of $D^\times$ is bounded by a cycle $C$. Note that $D^\times$ is bipartite since every edge of $G$ is crossed exactly once. Therefore, half the vertices of $C$ are dummy vertices. However, this is clearly impossible, since if $y$ is a dummy vertex on $C$, then there must be some vertex of $D^\times$ inside $O$.

Edit. The last sentence of the proof is incorrect as pointed out by Xin Xhang below. I'll leave the rest of the proof here in case it can be fixed.

Answer 2

Concerning the above answer, I do not quite agree with the last sentence. Why is there some vertex of $D^\times$ outside $O$ if $y$ is a dummy vertex on $C$? I draw a figure, where $y$ is a dummy vertex and the cycle $C$ is marked in blue. Now it may be possible that $uu'$ crosses $ww'$ at $y$ in $D$, however, each of $u,u',w,w'$ are on $C$.

Answer 3

The following sentence in the above question seems to need to be made more clear.

Let $\mathcal{D}$ be a 1-planar drawing of a 1-planar graph $G$ that has the minimum number of crossings, i.e, the number of crossings in $\mathcal{D}$ is exactly the crossing number of $G$.

Does the crossing number here refer to the concept of the link below?

• crossing number

Definition. The crossing number ${\rm cr} (G)$ of a graph $G$ is the minimum number of crossing pairs of edges, over all drawings of $G$ in the plane.

That is, when we consider the crosssing number of a 1-planar graph $G$, all drawings of $G$ need to be considered, including its non- 1-plane drawings. Thus the crossing number of an optimal 1-planar drawing (a 1 -planar drawing with minimum crossings) of $G$ may not be equal to crossing number of $G$.

---

Notice that there are many 1-planar graphs whose any optimal 1-planar drawing have least a non-crossing edge, such as $K_5$, $K_6$, and any optimal 1-planar graph. Note that they have an unique 1- planar drawing up to weak equivalence. Their crossing number are $1$, $3$ and $n-2$, respectively.

See the following two papers for details.

• Suzuki Y. Re-embeddings of maximum 1-planar graphs[J]. SIAM Journal on Discrete Mathematics, 2010, 24(4): 1527-1540.
• Ouyang, Z., Huang, Y. & Dong, F. The Maximal 1-Planarity and Crossing Numbers of Graphs. Graphs and Combinatorics 37, 1333–1344 (2021).

The unique 1-planar drawing of $K_5$ on the left, of $K_6$ on the middle, and of an optimal 1-planar graph with $8$ vertices.

---

More generally, any maximal 1-planar graph will not be considered.

Fact.([a]) If $ab$ and $cd$ are crossing edges in $G$, then $a$, $b$, $c$, $d$ span a $K_4$ in $G$.

-[a] Barát J, Tóth G. Improvements on the density of maximal 1‐planar graphs[J]. Journal of Graph Theory, 2018, 88(1): 101-109.

The crossing point of $ab$ and $cd$ is called $x$. Thus, $ac$ is an edge in $G$ which is a non-crossing edge otherwise, we can redraw $ac$ so that it's infinitely close the line $axc$ without crossing.