9
$\begingroup$

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?

$\endgroup$

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I have a question above your argument and describe it below as I need insert a picture. $\endgroup$
    – Xin Zhang
    Apr 19, 2022 at 13:23
  • 2
    $\begingroup$ 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$. $\endgroup$ Apr 20, 2022 at 13:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Apr 21, 2022 at 2:12
  • $\begingroup$ I cannot understand the final contradiction. What’s bad in a vertex outside $O$? $\endgroup$ Apr 29, 2022 at 8:26
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Apr 29, 2022 at 14:12
4
$\begingroup$

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

enter image description here

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Apr 19, 2022 at 15:01
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I don't understand your objection. The question seems clear to me as written. $\endgroup$ Apr 29, 2022 at 14:02
  • 1
    $\begingroup$ @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 $\endgroup$
    – L.C. Zhang
    Apr 29, 2022 at 14:35
  • $\begingroup$ 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. $\endgroup$ Apr 29, 2022 at 14:39
  • $\begingroup$ At any rate, this should be a comment rather than an answer. $\endgroup$ Apr 29, 2022 at 16:08
  • $\begingroup$ 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. $\endgroup$
    – L.C. Zhang
    Apr 29, 2022 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.