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

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?

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.

• I have a question above your argument and describe it below as I need insert a picture. Apr 19, 2022 at 13:23
• While placing $D_2$ inside $F$, how can you guaranteen that the cut vertex $v$ lies on the outer boudary of the drawing of $D_2$? It can be true but is it trivial? I am worry about the case that the uncrossed edge of $D_1$ crosses the uncrossed edge of $D_2$ under the drawing of $D$. Apr 20, 2022 at 13:34
• It doesn't matter if $v$ is on the outerface. We just have to draw $D_2$ inside $F$ so that it only meets $D_1$ at $v$. If you like, we can assume the drawing is on the sphere instead of the plane. Then every face is the outerface. Apr 21, 2022 at 2:12
• I cannot understand the final contradiction. What’s bad in a vertex outside $O$? Apr 29, 2022 at 8:26
• That should have read 'inside' $O$, but is incorrect as pointed out by Xin Xhang below. I edited the answer to make it clear that there is a mistake. Apr 29, 2022 at 14:12

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$$.

• Good point. Your picture cannot happen though, since we may draw the edge $uu'$ outside of the cycle to remove the crossing $y$. It could be that that $w$ and $u$' are not on $C$ though. I'll try to think of an argument for that case too. Apr 19, 2022 at 15:01

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?

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.

• I don't understand your objection. The question seems clear to me as written. Apr 29, 2022 at 14:02
• @SamHopkins I mean that any 1-planar graph $G$ has a 1-planar drawing with the minimum number of crossings $s$ , but $s$ is not necessarily equal to the crossing number of $G$. By the way, I'm just trying to figure out what the questioner's intentions are and not object to it Apr 29, 2022 at 14:35
• Ah I see. Indeed I think the question-asker intends to ask about the smallest number of crossings in a 1-planar drawing, so technically not the “crossing number” as usually defined. Apr 29, 2022 at 14:39
• At any rate, this should be a comment rather than an answer. Apr 29, 2022 at 16:08
• Indeed, I think it fits as a comment. But I'd like to insert above picture. I haven't looked carefully at the proof of Huynh and once I'm done, I’d like to try to add a proof. This is a good question. Apr 29, 2022 at 16:35