Skewness and the crossing numbers of graphs

1.   Introduction

All graphs considered here are undirected, simple and finite. For graph theory terminology not defined here, we direct the reader to ^[3]. For any graph $G$, let $E(G)$ and $V(G)$ denote its edge set and vertex set, respectively. A drawing of a graph $G$ is a mapping $D$ that assigns to each vertex in $V(G)$ a distinct point in the plane, and to each edge $uv$ in $G$ a continuous arc connecting $D(u)$ and $D(v)$, not passing through the image of any other vertex. For simplicity, we impose the following conditions on a drawing: (a) if two edges share an interior point $p$, then they cross at $p$; (b) any two edges of a drawing have only a finite number of crossings (common interior points); and (c) no three edges have an interior point in common. We call a drawing that meets the above conditions a good drawing.

Let $cr_{D}(G)$ denote the number of crossings in a good drawing $D$ of $G$, and the crossing number of $G$, denoted by $cr(G)$, is the minimum value of $cr_{D}(G)$'s among all possible good drawings $D$. A good drawing is said to be optimal if it minimizes the number of crossings. Computing the crossing number of a graph is an NP-hard problem ^[11], even for small graphs, because $cr(K_{13})$ is still an open problem ^[14]. For more about crossing numbers, see Reference [15]. The skewness of a graph, denoted by $sk(G)$, is the smallest number of edges that need to be removed from $G$ to make it planar. Computing the skewness of a graph is an NP-hard problem ^[13]. For more about skewness, see Reference [12]. Skewness and crossing numbers have drawn much attention in the literature and play important roles in several other areas of mathematics ^[5,7,12]. Skewness appears to be closely related to the crossing number, but they may differ widely for special graphs. The following is readily checked:

Observation 1. For any graph $G$, $sk(G)\leq cr(G)$.

Note that $sk(G)$ is a lower bound for $cr(G)$, but that $cr(G)-sk(G)$ could be very large ^[8]. There are only few results concerning the relationship between the skewness and crossing number of a graph. In ^[10], a nice relationship between $cr(G)$ and $sk(G)$ has been established.

Theorem 1. (^[10]) For the graph $G$ of order $n$,

$G$ is a planar graph {if and only if} $cr(G) = sk(G) = 0$. A graph $G$ is near-planar {if and only if} $sk(G) = 1$. By Theorem 1, for every near-planar graph $G$ of order $n$, $cr(G)\leq\frac{2n-7}{3}$. Near-planarity is a very weak relaxation of planarity; hence, it is natural and interesting to study the properties of near-planar graphs. Graphs embeddable in the torus and apex graphs are superfamilies of near-planar graphs. However, computing the crossing number of a near-planar graph is an NP-hard problem ^[9].

In Section 2 of this work, we construct a new class of near-planar graphs and determine the exact value of the crossing number, which can be arbitrarily large odd numbers. This implies that there exist infinitely many near-planar graphs $G$ such that the upper bound for $cr(G)$ given in Theorem 1 is sharp. In Section 3, we first give a necessary and sufficient condition for a graph to have its skewness equal to the crossing number. Besides, we conclude that some special classes of graphs $G$ satisfy the equality $sk(G) = cr(G)$.

2.   Infinitely many near-planar graphs

In what follows, we construct infinitely many near-planar graphs $G$ such that the upper bound for $cr(G)$ given in Theorem 1 is sharp.

The Cartesian product $G_{1}\Box G_{2}$ of the graphs $G_{1}$ and $G_{2}$ has the vertex set $V(G_{1}\Box G_{2}) = V(G_{1})\times V(G_{2})$, and two vertices $(u, u^{\prime})$ and $(v, v^{\prime})$ are adjacent in $G_{1}\Box G_{2}$ if and only if either $u = v$ and $u^{\prime}$ is adjacent with $v^{\prime}$ in $G_{2}$, or if $u^{\prime} = v^{\prime}$ and $u$ is adjacent with $v$ in $G_{1}$. Let $C_{n}$ be the cycle of length $n$, and let $P_{n}$ be the path of order $n$. The vertex set and edge set of the Cartesian product $C_3\Box P_k$ can be represented as follows:

and

Let $G_k$ denote the graph obtained from $C_3\Box P_k$ by adding two new vertices $x$ and $y$ and adding new edges in the following set:

A drawing of $G_k$ is shown in Figure 1. Clearly, $sk(G_{k}) = 1$ for $k\geq1$. The following result determines $cr(G_k)$ for $k\ge 1$.

Theorem 2. For $k\ge 1$, $cr(G_k) = 2k-1$.

Proof. Consider the subgraph $H$ of $G_{k}$ as shown in Figure 2(1). Simultaneously smoothing all vertices in $H$ with degree two, we get the graph shown in Figure 2(2), denoted by $H^*$.

Let $G-V$ refer to the graph obtained from $G$ by removing the vertex set $V$, and let $G \backslash E$ refer to the graph obtained from $G$ by removing the edge set $E$. For convenience, let $G\backslash\{e\}$ = $G\backslash e$ and $G- \{u\}$ = $G- u$. We first prove the following claims for any good drawing $D$ of $H^{*}$.

Claim 1. For any $e\in E(H^{*}-y)$, $H^*\backslash e$ is not planar.

Proof. For the graph $H^{*}-y$, we need to consider the following cases.

Case 1: Let $e$ be an edge of the 3-cycle $a_{1}b_{1}c_{1}$. Without loss of generality, assume that $e = b_{1}c_{1}$; then, the graph $H^{*}\setminus e$ contains a subgraph which is homeomorphic to $K_{3, 3}$. Let $(X, Y)$ be the partition of $K_{3, 3}$, where $X = \{x, a_{2}, b_{2}\}$ and $Y = \{y, a_{1}, b_{1}\}$.

Case 2: Let $e\in \{xa_{1}, xb_{1}, xc_{1}\}$. Without loss of generality, assume that $e = xc_{1}$; then, the graph $H^{*}\setminus e$ contains a subgraph which is homeomorphic to $K_{3, 3}$. Let $(X, Y)$ be the partition of $K_{3, 3}$, where $X = \{x, a_{2}, c_{2}\}$ and $Y = \{y, a_{1}, b_{1}\}$.

Case 3: Let $e\in \{a_{2}a_{1}, a_{2}b_{1}, b_{2}b_{1}, b_{2}c_{1}, c_{2}c_{1}, c_{2}a_{1}\}.$ Without loss of generality, assume that $e = a_{2}b_{1}$; then, the graph $H^{*}\setminus e$ contains a subgraph which is homeomorphic to $K_{5}$, where the vertex set is $\{x, y, a_{1}, b_{1}, c_{1}\}$.

Thus, Claim 1 follows. □

For any good drawing $D$ of $H^{*}$ and any edge $e$ in $H^*$, let ${{\cal CR}}_D(e)$ denote the set of crossings of $D$ that happens on $e$.

Claim 2. For any good drawing $D$ of $H^{*}$, there exist two different edges $e_{1}, e_{2} \in E(H^{*}-y)$ such that

(a) ${{\cal CR}}_D(e_i)\not\subseteq {{\cal CR}}_D(e_{3-i})$ for $i = 1, 2$;

(b) $\{e_{1}, e_{2}\}\neq \{a_{2}a_{1}, a_{2} b_{1}\}$, $\{b_{2}b_{1}, b_{2} c_{1}\}$ or $\{c_{2}c_{1}, c_{2} a_{1}\}$.

Proof. Since $D$ is a good drawing of $H^{*}$, the four edges in $H^*$ incident with vertex $y$ do not cross each other, implying that each crossing of $D$ belongs to ${{\cal CR}}_D(e)$ for some $e\in E(H^{*}-y)$.

Let $S = \{e_1, \cdots, e_k\}$ be a set of edges in $E(H^{*}-y)$ with the minimum size such that each crossing of $D$ is contained in ${{\cal CR}}_D(e_i)$ for some $i$, implying that $H^*\backslash S$ is planar. By Claim 1, $k\ge 2$. By the minimality of $S$, each pair of edges in $S$ has the property (a).

If $k\ge 3$, the result follows by choosing two suitable edges in $S$. Now, assume that $k = 2$. By the assumption on $S$, $H^*\backslash \{e_1, e_2\}$ is planar. It is routine to verify that, if $\{e_1, e_2\}$ is any one of the sets $\{a_{2}a_{1}, a_{2} b_{1}\}$, $\{b_{2}b_{1}, b_{2} c_{1}\}$ or $\{c_{2}c_{1}, c_{2} a_{1}\}$, then $H^*\backslash \{e_1, e_2\}$ contains a subdivision of $K_{3, 3}$. Without loss of generality, consider that $\{e_{1}, e_{2}\} = \{a_{2}a_{1}, a_{2} b_{1}\}$; then, the graph $H^{*}\setminus \{e_{1}, e_{2}\}$ contains a subgraph which is homeomorphic to $K_{3, 3}$. Let $(X, Y)$ be the partition of $K_{3, 3}$, where $X = \{x, b_{2}, c_{2}\}$ and $Y = \{y, b_{1}, c_{1}\}$. This implies that $H^*\backslash \{e_1, e_2\}$ is not planar, which is a contradiction.

Thus, Claim 2 holds. □

We now proceed to prove Theorem 2 by applying Claim 2. The result is true for $k = 1$, as $G_{1}$ is actually the complete graph $K_{5}$.

Suppose that $k\ge 2$, and that for any $l < k$, $cr(G_{l})\geq 2l -1$ holds. Note that Figure 1 shows that $cr(G_{k})\le 2k -1$. Thus, it suffices to show that $cr_{\phi}(G_{k})\geq 2k-1$ holds for any good drawing $\phi$ of $G_{k}$.

Let $\phi'$ denote the restricted drawing of the subgraph $H$ induced by $\phi$, as shown in Figure 2(1). There are three paths in $H$: $P_{1} = ya_{k}a_{k-1}...a_{2}, P_{2} = yb_{k}b_{k-1}...b_{2}$ and $P_{3} = yc_{k}c_{k-1}...c_{2}$. We can "smooth" all of the 2-degree vertices in $H$ and modify the drawing $\phi^{'}$ to a good drawing $\phi^{*}$ of $H^*$.

Assume that Claim 2 holds for edges $e_1$ and $e_2$ in $E(H^*-y)$. So, $\{e_1, e_2\}$ is a $2$-element subset of

but $\{e_{1}, e_{2}\}\neq \{a_{2}a_{1}, a_{2} b_{1}\}$, $\{b_{2}b_{1}, b_{2} c_{1}\}$ or $\{c_{2}c_{1}, c_{2} a_{1}\}$. Thus, $e_1$ and $e_2$ are actually edges in $H$ and none of them are in paths $P_1, P_2$ or $P_3$.

Note that $G_{k}\setminus\{e_{1}, e_{2}\}$ contains a subgraph of $G_k$ which is homeomorphic to $G_{k-1}$. Thus, $cr_{\phi}(G_{k}\setminus\{e_{1}, e_{2}\})\geq cr(G_{k-1})\geq2(k-1)-1$ by the induction hypothesis, implying that $cr_{\phi}(G_{k})\geq cr_{\phi}(G_{k}\setminus\{e_{1}, e_{2}\})+2\geq2(k-1)-1+2 = 2k-1$. □

Because $|V(G_{k})| = 3k+2$, $sk(G_k) = 1$ and $cr(G_k) = 2k-1$, it is routine to verify that the equality given in Theorem 1 holds.

3.   Characterizing graphs with $sk(G)=cr(G)$

A drawing of a graph is 1-planar if each of its edges is crossed at most once. If a graph has a 1-planar drawing, then it is 1-planar. We now give a necessary and sufficient condition for a graph to have its skewness equal to the crossing number.

Theorem 3. Let $G$ be a graph; then, $sk(G) = cr(G)$ {if and only if} any optimal drawing of $G$ is a 1-planar drawing.

Proof. Assume that $sk(G) = cr(G)$. Suppose that there exists an optimal drawing $D$ of $G$ that is not a 1-planar drawing. According to the definition of a 1-planar drawing, there exists an edge $e\in E(G)$ that is crossed at least twice in $D$. Since $D$ is an optimal drawing of $G$, then $cr(D) = cr(G)$. It is readily checked that $cr(D\setminus e)\leq cr(G)-2$. Thus, $sk(G)\leq sk(D)\leq sk(D\setminus e)+1 \leq cr(D\setminus e)+1\leq cr(G)-2+1 = cr(G)-1$, which is a contradiction.

Suppose that any optimal drawing of $G$ is a 1-planar drawing. Note that $sk(G)\leq cr(G)$. We now prove that $sk(G)\geq cr(G)$. Suppose that $sk(G)\leq cr(G)-1$. Let $D$ be any optimal drawing of $G$, namely, $cr(D) = cr(G)$. We note that $sk(G)\leq cr(G)-1 = cr(D)-1$; thus, there exists one edge $e\in E(G)$ that is crossed at least twice in $D$, which is a contradiction. □

A drawing of a 1-planar graph partitions the plane into empty regions called faces. A face is defined by the cyclic sequence of edges and edge segments that forms its boundary, which is described by vertices and crossings. A face is a triangle if its size is three. A graph $G$ is called maximal in a graph class if no edge can be added to $G$ without violating the defining class. Any maximal 1-planar graph $G$ and its 1-planar drawing $D$ have the following Properties 1–3, from ^[4].

Property 1. In $G$, the smallest degree is at least two. If $deg_{G}(u) = 2$, $uv_{1}$ and $uv_{2}$ are edges; then, $uv_{1}$ and $uv_{2}$ are not crossed in $D$.

Property 2. If $ab$ and $cd$ are edges which cross each other; then, $\{a, b, c, d\}$ spans a $K_{4}$ in $D$.

Remove all vertices of degree two from $D$. The resulting $\hat{D}$ is the skeleton of $D$. Notice that each vertex of $\hat{D}$ has a degree of at least three.

Property 3. If one edge is not part of a $K_{4}$ in $\hat{D}$, then the edge is called exceptional. Assume that the edge $uv$ of $\hat{D}$ is exceptional. Let $f_{1}$ and $f_{2}$ be the faces bounded by $uv$ in $\hat{D}$. Then, the following holds:

(i) $f_{1} \neq f_{2}$;

(ii) For $i = 1, 2,$ $f_{i}$ has exactly three vertices on its boundary, and let $v_{i}$ denote the third vertex. Furthermore, $v_{1} = v_{2}$;

(iii) Both $uv_{i}$ and $vv_{i}$ are not exceptional in $\hat{D}$.

Property 4. Let $G$ be a maximal 1-planar graph; there exists a 1-planar drawing $D$ of $G$. The following are equivalent:

(i) Every face of $D$ is a triangle; and

(ii) $G$ is 3-connected.

Proof. $(i)\Rightarrow (ii)$: Let $D^{P}$ be the planarization of $D$ obtained by turning all crossings of D into new vertices. Since every face of $D$ is a triangle, it follows that $D^{P}$ is maximal planar, and that is 3-connected.

Suppose that $G$ is not 3-connected; then, there exist $u, v\in V(G)$ such that $G-\{u, v\}$ is not connected. Consider that the vertex $a, b\in V(G)$ and are in separate components of $G-\{u, v\}$. Since $D^{P}$ was 3-connected, $D^{P}-\{u, v\}$ is still connected; thus, there exists paths from $a$ to $b$ in $D^{P}-\{u, v\}$. Let $P$ be a path from $a$ to $b$ in $D^{P}-\{u, v\}$ that uses the smallest number of crossings. We know that $P$ must contain at least one crossing; otherwise, it is as desired. Furthermore, we know that $P$ cannot contain two consecutive crossings due to the 1-planar drawing of $D$.

If the subpath ($v_{1}, c, v_{2}$) is in $P$, where $c$ is a crossing, in view of every face of $D$ being a triangle, then we can construct a path from $a$ to $b$ in $G-\{u, v\}$ that uses fewer crossings than in $P$ by replacing the subpath ($v_{1}, c, v_{2}$) with $(v_{1}, w, v_{2})$, where $w$ is not a crossing; this is in contradiction with $P$ being a path with smallest number of crossings.

$(ii)\Rightarrow (i)$: Assume that $G$ is a 3-connected maximal 1-planar graph. By Properties 1–3, there exists a 1-planar drawing $D$ of $G$, $D$ has no vertices of degree two and each edge of $D$ is part of a $K_{4}$. Thus, every face of $D$ is a triangle. Otherwise, $D$ has a face $f$ with a size of at least four, as $D$ is a 1-planar drawing and there cannot be two consecutive incident crossings. Then, there exist at least two vertices on the boundary of $f$, and they are adjacent, denoted by $e = uv\in E(G)$. In $D$, the edge $e$ can be introduced through $f$, splitting $f$ into two faces. If not, $G-\{u, v\}$ is disconnected, which is a contradiction. □

The girth of a graph is the length of its shortest cycle, or infinity, if the graph does not contain any cycles (i.e., an acyclic graph). All girths considered in this paper are finite without special indication. Below, we give the lower bound of the skewness for a connected graph from ^[6].

Lemma 1. (^[6]) Let $G$ be a connected graph on $n$ vertices and $m$ edges with girth $g$. Then, $sk(G)\geq \lceil m-\frac{g}{g-2}(n-2)\rceil$.

A graph is called NIC-planar if it has a 1-planar drawing so that two pairs of crossed edges share at most one vertex ^[16], and a graph is called IC-planar if it has a 1-planar drawing so that each vertex is incident to at most one crossed edge ^[1]. Bachmaier et al. ^[2] has showed that an NIC-planar drawing of any maximal NIC-planar graph with at least five vertices is a triangulation. Moreover, the result also holds for any maximal IC-planar graph by a similar argument. Let $M$ denote the set of any maximal NIC-planar (or IC-planar) graph with at least five vertices and any 3-connected maximal 1-planar graph.

Observation 2. Let $G\in {M}$; then, there is a 1-planar drawing $D$ of $G$ such that every face of $D$ is a triangle and $sk(G) = cr(G).$ Moreover, $D$ is also an optimal drawing of $G$.

Proof. Combining this with Property 4, there exists a 1-planar drawing $D$ of $G$ such that every face of $D$ is a triangle. Let $X$ be the set of crossings in $D$; then, $sk(G)\leq cr(G)\leq cr(D) = |X|$ due to Observation 1. Recall that $D^{P}$ is the planarization of $D$. Observe that, since every face of $D$ is a triangle, $D^{P}$ is a triangulated plane graph. It follows that $D^{P}$ has $2|V(D^{P})|-4 = 2n+2|X|-4$ faces. Further, the number of faces in $D^{P}$ is equal to the number of faces in $D$, so $D$ has $2n +2|X|-4$ faces. Since every face of $D$ is a triangle, every crossing has four incident crossed faces. Also note that every crossed face must be incident to exactly one crossing. It follows that $D$ has $4|X|$ crossed faces and, as a result, has $2n-2|X|-4$ uncrossed faces. Then, $|E(D^{P})| = |V (D^{P})| + |F(D^{P})| - 2 = n + |X| + 2n + 2|X| - 4- 2 = 3n +3|X|-6$, which implies that $|E(G)| = |E(D^{P})|-2|X| = 3n +|X|-6$. Each face of $D$ is a triangle, which is either a 3-cycle or incident to exactly one crossing, and this crossing is also associated with four triangles. Thus, $G$ has a girth of three. By Lemma 1, we have that $sk(G)\geq|X|$. Then, $sk(G) = cr(G) = |X|$ and $D$ is an optimal drawing of $G$. □

Call a face whose boundary is a simple cycle of length four a quadrangle. We have the following results, which are also clearly demonstrable.

Observation 3. Let $G$ be a simple plane graph with $l$ quadrangles, and let each remaining face of $G$ be a triangle. A new graph $G^{*}$ is obtained as follows: connect two new diagonal edges inside each of these $l$ quadrangles. Then, $sk(G^{*}) = cr(G^{*}) = l$.

Observation 4. Let $G$ be a connected graph with $m$ edges. If $k$ is the maximum number of edges in a planar subgraph of $G$ and there exists a drawing $D$ of $G$ with $m-k$ crossings, then $sk(G) = cr(G) = m-k$.

4.   Conclusions

The main accomplishment of this research is to construct infinitely many near-planar graphs with $n$ vertices such that the inequality $cr(G)\le \frac{3 sk(G)^2+(4n-17)sk(G)}{6}$ is equal. In addition, we give a necessary and sufficient condition for a graph to have its skewness equal to the crossing number.

Use of AI tools declaration

The author declares that he/she has not used artificial intelligence tools in the creation of this article.

Acknowledgments

The work was supported by the National Natural Science Foundation of China (No. 11871206), Hunan Provincial Natural Science Foundation of China (No. 2023JJ30178) and the Scientific Research Fund of the Hunan Provincial Education Department (No. 22A0637).

Conflict of interest

The author declare that there is no conflict of interest regarding the publication of this paper.