Skip to main content
edited body
Source Link

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)-2$$e(G)\leq 2v(G)-4$. Nevertheless, this is not a contradiciton to complete the proof.

So how can I move on?

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)-2$. Nevertheless, this is not a contradiciton to complete the proof.

So how can I move on?

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?

Source Link

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)-2$. Nevertheless, this is not a contradiciton to complete the proof.

So how can I move on?