# The reducibility of optimal 1-planar graphs with respect to the
lexicographic product ††thanks: The work is supported by the National Natural
Science Foundation of China (Grant No. 12271157) and the Natural Science
Foundation of Hunan Province, China (Grant No. 2022JJ30028).

Licheng Zhang, Yuanqiu Huang
College of Mathematics and Statistics
Hunan Normal University, Changsha 410081, P.R China
Email<EMAIL_ADDRESS>author. Email<EMAIL_ADDRESS>
###### Abstract

A graph is called 1-planar if it can be drawn on the plane (or on the sphere)
such that each edge is crossed at most once. A 1-planar graph $G$ is called
optimal if it satisfies $|E(G)|=4|V(G)|-8$. If $G$ and $H$ are graphs, then
the lexicographic product $G\circ H$ has vertex set the Cartesian product
$V(G)\times V(H)$ and edge set $\\{(g_{1},h_{1})(g_{2},h_{2}):g_{1}g_{2}\in
E(G),\,\,\text{or}\,\,g_{1}=g_{2}\,\,\text{and}\,\,h_{1}h_{2}\in E(H)\\}$. A
graph is called reducible if it can be expressed as the lexicographic product
of two smaller non-trivial graphs. In this paper, we prove that an optimal
1-planar graph $G$ is reducible if and only if $G$ is isomorphic to the
complete multipartite graph $K_{2,2,2,2}$. As a corollary, we prove that every
reducible 1-planar graph with $n$ vertices has at most $4n-9$ edges for $n=6$
or $n\geq 9$. We also prove that this bound is tight for infinitely many
values of $n$. Additionally, we give two necessary conditions for a graph
$G\circ 2K_{1}$ to be 1-planar. Keywords: drawing, 1-planar graph, optimal
1-planar graph, lexicographic product, reducibility

AMS Subject Classification: 05C10, 05C62, 05C76

##  1 Introduction

A drawing of a graph $G=(V,E)$ is a mapping $D$ that assigns to each vertex in
$V$ a distinct point in the plane (or on the sphere) and to each edge $uv$ in
$E$ a continuous arc connecting $D(u)$ and $D(v)$. A drawing of a graph is a
$1$-planar drawing if each edge is crossed at most once. A graph is called
$1$-planar if it has a 1-planar drawing. A graph, together with a 1-planar
drawing is called $1$-plane. 1-planar graphs were first studied by Ringel
(1965) [30] in the connection with the problem of the simultaneous coloring of
the vertices and faces of plane graphs. Since then, many properties of
1-planar graphs have been widely investigated; see [1, 6, 9, 14, 23, 24, 37]
for examples, see also [26] for a survey, and see [34] for a more recent book.

A graph is maximal $1$-planar if we cannot add any edge from the complement so
that the resulting graph is still 1-planar and simple. It is well-known every
1-planar graph with $n~{}(\geq 3)$ vertices has at most $4n-8$ edges. A
1-planar graph with $n$ vertices is called optimal if it has exactly $4n-8$
edges. Clearly, any optimal 1-planar graph is a maximal 1-planar graph, but
the inverse may not always be true [3, 11]. Optimal 1-planar graphs have also
been studied extensively due to their interesting properties. Suzuki [32]
proved that every optimal 1-planar graph is obtained by adding a pair of
crossing edges to each face of a 3-connected quadrangulation on the sphere.
Didimo [16] proved that no optimal 1-planar graph has a 1-planar straight-line
drawing. Hudák et al. [25] proved that every optimal 1-planar graph with even
order has a perfect matching. Moreover, the matching extendability of optimal
1-planar graphs was characterized [18, 36]. Suzuki [33] proved that every
optimal 1-planar graph has a $K_{6}$-minor and characterized optimal 1-planar
graphs having no $K_{7}$-minor. Lenhart et al. [28] proved that every optimal
1-plane graph has a red–blue edge coloring such that the blue subgraph is
maximal plane while the red subgraph has vertex degree at most four.

Among studies of 1-planar graphs, determining whether a given graph is
1-planar is a fundamental problem. Unfortunately, it is NP-complete to test
whether a given graph is 1-planar [20, 27], while testing planarity of a given
graph is solvable in linear time. It is easy to see that every graph is a
minor of a 1-planar graph. Suzuki [33] proved that any graph is a topological
minor of an optimal 1-planar graph. These imply that 1-planarity cannot be
characterized in terms of forbidden minors or forbidden topological minors. So
it seems difficult to test whether a given graph is 1-planar. However, there
are results for some special graph classes. Czap and Hudák [13] characterized
1-planatity of complete multipartite graphs. Czap et al. [15] studied
1-planatity of join products of graphs. Binucci et al. [7] investigated the
feasibility of a 1-planarity testing and embedding algorithm based on a
backtracking strategy, and their approach can be successfully applied to some
non-planar graphs with up to 30 vertices. Optimal 1-planar graphs can be
recognized in linear time [10], while general 1-planar graphs are NP-hard to
recognize.

A lexicographic product $G\circ H$ of two graphs $G$ and $H$ is a graph such
that the vertex set of $G\circ H$ is the Cartesian product $V(G)\times V(H)$
and two vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$ are adjacent in $G\circ
H$ if and only if either $g_{1}$ is adjacent to $g_{2}$ in $G$ or
$g_{1}=g_{2}$ and $h_{1}$ is adjacent to $h_{2}$ in $H$. We call $G$ and $H$
the left and right factors of $G\circ H$, respectively. The lexicographic
product is also known as graph substitution, since $G\circ H$ can be obtained
from $G$ by substituting a copy $H_{u}$ of $H$ for every vertex $u$ of $G$ and
then joining all vertices of $H_{u}$ with all vertices of $H_{v}$ if $uv\in
E(G)$. Note that the lexicographic product is not commutative, that is $G\circ
H\neq H\circ G$ in general. A graph is trivial if it has just one vertex or no
vertex. A graph is called reducible if it is the lexicographic product of two
non-trivial graphs, otherwise is called irreducible. In general, it seems not
easy to determine whether a graph is reducible. As Feigenbaum and Schäffer
[17] showed, the problem of recognizing whether a graph is a lexicographic
product is equivalent in complexity to the graph isomorphism problem (the
graph isomorphism problem is the computational problem of determining whether
two finite graphs are isomorphic). The graph isomorphism problem (and so is
the problem of testing reducibility) is not known to be solvable in polynomial
time or to be NP-complete [2, 31].

Let $C_{n}$ and $K_{n}$ denote the cycle and the complete graph with $n$
vertices, respectively. The disjoint union of $k$ copies of a graph $G$ is
denoted by $kG$. A cactus is a connected graph in which every edge belongs to
at most one cycle. In 2015, Bucko and Czap [12] discussed the 1-planarity of
lexicographic products of graphs. The authors arose a conjecture and an open
problem as follows.

######  Conjecture 1 ([12]).

The graph $G\circ K_{2}$ is $1$-planar if and only if $G$ is a cactus.

The “if”-part of the above conjecture was proved in [12]. Recently, Matsumoto
and Suzuki [29] solved the “only if”-part of the conjecture, and thus
Conjecture 1 has been settled. So the study of 1-planarity of the
lexicographic products of graphs only leaves the following open problem.

######  Problem 1 ([12]).

Let $G$ be a connected graph with maximum degree at least $3$. Characterize
the $1$-planarity of $G\circ 2K_{1}$.

So far, Problem 1 remains unsolved. Our main motivations come from the open
problem. In this paper, we characterize the reducibility of optimal 1-planar
graphs. As a corollary, we prove that every reducible 1-planar graph with $n$
vertices has at most $4n-9$ edges for $n=6$ or $n\geq 9$. We also prove that
this bound is tight for infinitely many values of $n$. Also as corollaries, we
shall give two necessary conditions for a graph $G\circ 2K_{1}$ to be
1-planar. We have some other potential motivations, such as finding more
properties of optimal 1-planar graphs because there are many open problems for
optimal 1-planar graphs. For example, Bekos et al. [5] studied experimentally
the book embedding problem from a SAT-solving perspective, and they
conjectured that optimal 1-planar graphs have book thickness four. For general
1-planar graphs, Gollin et al. [19] determined precisely the maximum total
number of cliques as well as the maximum number of cliques of any fixed size.
However, for optimal 1-planar graphs, the sharp upper bounds on the maximum
number of cliques of size 3, size 4 or size 5 are not known [19]. More open
problems for optimal 1-planar graphs can be seen in [26]. Clearly, the
reducibility (i.e. decomposition) of graphs is an inverse process of graph
products. However, in contrast to graph products, not much research has been
done on the reducibility of (beyond planar) graphs to our best knowledge.

Our main results are as follows.

######  Theorem 1.

An optimal $1$-planar graph $G$ is reducible if and only if $G$ is isomorphic
to $K_{2,2,2,2}$.

######  Corollary 1.

Let $G$ be a reducible $1$-planar graph with $n$ vertices and $m$ edges. Then
following statements hold.

  * (i)

$m\leq 24$ for $n=8$, and “ $24$” is tight;

  * (ii)

$m\leq 4n-9$ for $n=6$ or $n\geq 9$, and this bound is tight.

######  Corollary 2.

Let $G$ be a graph with $n\geq 2$ vertices and $m$ edges. If $G\circ 2K_{1}$
is $1$-planar, then following statements hold.

  * (i)

$m\leq 2n-3$ for $n\neq 4$, and $m\leq 6$ for $n=4$;

  * (ii)

for any subgraph of $G$ with $s\geq 2$ vertices has at most $2s-3$ edges for
$s\neq 4$ and has at most $6$ edges for $s=4$.

######  Corollary 3.

Let $G$ be a graph with $n$ vertices. If $G\circ 2K_{1}$ is $1$-planar, then
$G$ is $1$-planar for any $n$ and is not maximal $1$-planar for $n\geq 17$.

The remaining sections of this paper are organized as follows. In Section 2,
we give some terminology and notations. In Section 3, we give some lemmas. In
Section 4, we give proofs of Theorem 1 and Corollaries 1, 2 and 3. In Section
5, we raise some open problems.

##  2 Terminology and notation

Let $V(G)$ and $E(G)$ denote the vertex set and edge set of a graph $G$,
respectively. The notation $|V(G)|$ is also known as the order and $|E(G)|$ as
the size of $G$. All graphs considered here are simple and nontrivial, unless
otherwise stated. A drawing is good if no edge crosses itself, no two edges
cross more than once, and no two incident edges cross. All 1-planar drawings
are good in this paper.

Let $G$ be 1-planar graph with a 1-planar drawing $D$. An edge $e$ of $G$ is
called a crossing edge under $D$ if it crosses with any other edge under the
drawing $D$, and is called a non-crossing edge under $D$ otherwise. A cycle
$C$ of $G$ is called a non-crossing cycle under $D$ if each edge on $C$ is
non-crossing under $D$, and is called a crossing cycle under $D$. The planar
skeleton $\mathcal{S}(D)$ of $D$ is the subgraph of $G$ by removing all
crossing edges of $D$. Let $H$ be a subgraph of $G$. The subdrawing $D|H$ of
$H$ induced by $D$ is called a restricted drawing of $D$. Let $\mathcal{P}$ be
a plane. Similar to planar drawings, the 1-planar drawing $D$ also defines the
faces, which are the connected parts of $\mathcal{P}\setminus D$. Each face
$f$ contains on its boundary a number of vertices and crossings of $D$; these
are called the corners of $f$. A face is uncrossed if all incident corners are
vertices, and is crossed otherwise. A $k$-face is a face whose boundary walk
has a length of exactly $k$. Let $L$ be a closed curve in $\mathcal{P}$ that
does not cross itself. Thus, $L$ separates $\mathcal{P}$ into two open
regions, the bounded one (i.e., the interior of $L$) and the unbounded one
(i.e., the exterior of $L$). We denote by $L_{int}$ and $L_{out}$ the interior
and exterior of $L$, respectively.

Let $G$ be a graph. We call a cycle $C$ of $G$ an even cycle if $C$ contains
an even number of edges. If $S$ is a set of vertices of $G$, the vertex-
induced subgraph $G[S]$ is the subgraph of $G$ that has $S$ as its set of
vertices and contains all the edges of $G$ that have both end-vertices in $S$.
We denote by $G\cong H$ that graphs $G$ and $H$ are isomorphic. We denoted by
$K_{n_{1},n_{2},\cdots,n_{k}}$ a complete multipartite graph with $k$
partition classes of sizes $n_{1},n_{2},\cdots,n_{k}$, respectively.

The terms not defined here can be found in [35].

##  3 Preliminary results

In this section we give some lemmas. For making the structure clear, we divide
these lemmas into three groups.

###  3.1  Properties for lexicographic products of graphs

We begin with two simple lemmas.

######  Lemma 1 ([21]).

The number of edges of a graph $G\circ H$ is
$|V(G)|\times|E(H)|+|V(H)|^{2}\times|E(G)|.$

######  Lemma 2 ([21]).

A graph $G\circ H$ is connected if and only if $G$ is connected.

The following Lemma 3 is obtained based on the definition of lexicographic
products, which will be a useful tool in Section 4.

######  Lemma 3.

Let $G$ and $H$ be graphs with vertex set $\\{g_{1},g_{2},\cdots,g_{s}\\}$ and
vertex set $\\{h_{1},h_{2},\cdots h_{l}\\}$, respectively, where $s=|V(G)|$
and $l=|V(H)|$. Let $G^{\prime}=G\circ H$. Then the following statements are
hold.

  * (i)

For $1\leq i\neq j\leq s$, both
$G^{\prime}[(g_{i},h_{1}),(g_{i},h_{2}),\cdots,(g_{i},h_{l})]$ and
$G^{\prime}[(g_{j},h_{1}),(g_{j},h_{2}),\cdots,\\\ (g_{j},h_{l})]$ are
isomorphic to $H$.

  * (ii)

If a vertex $u$ in $G^{\prime}$ is adjacent to $(g_{k},h_{i})$ where $1\leq
k\leq s$ and $1\leq i\leq l$, then $u$ is adjacent to every vertex in
$\\{(g_{k},h_{1}),(g_{k},h_{2}),\cdots,(g_{k},h_{i}),\cdots,(g_{k},h_{l})\\}$.

###### Proof.

For (i), by the definition of lexicographic products,
$G^{\prime}[(g_{i},h_{1}),(g_{i},h_{2}),\cdots,(g_{i},h_{l})]$ and
$G^{\prime}[(g_{j},h_{1}),(g_{j},h_{2}),\cdots,(g_{j},h_{l})]$ are copies of
$H$ corresponding to $g_{i}$ and $g_{j}$, respectively. Clearly, they are both
isomorphic to $H$.

For (ii), we first note that the vertex set
$\\{(g_{k},h_{1}),(g_{k},h_{2}),\cdots,(g_{k},h_{i}),\cdots,(g_{k},h_{l})\\}$
in $V(G^{\prime})$ corresponds to the vertex $g_{k}$ of $G$ ($g_{k}$ is
substituted by a copy of $H$ in $V(G^{\prime})$). Clearly, by the definition
of lexicographic products, $u$ is adjacent to all vertices in
$\\{(g_{k},h_{1}),(g_{k},h_{2}),\cdots,(g_{k},h_{i}),\cdots,(g_{k},h_{l})\\}$,
since $u$ is adjacent to $(g_{k},h_{i})$ in $G^{\prime}$. ∎

###  3.2  Results for the 1-planarity of lexicographical products of graphs

We collect some results related to the 1-planarity of lexicographical products
of graphs, which will be used in the upcoming proof.

######  Lemma 4 ([12]).

Let $G$ be a connected graph with at least $3$ vertices and let $H$ be a graph
with at least $4$ vertices. Then $G\circ H$ is not $1$-planar.

######  Lemma 5 ([12]).

Let $G=K_{2}$ and let $H$ be a graph with at least $5$ vertices. Then $G\circ
H$ is not $1$-planar.

######  Lemma 6 ([12]).

Let $G=K_{2}$ and let $H$ be a graph with at most $4$ vertices. Then $G\circ
H$ is $1$-planar if and only if $H$ is a subgraph of $C_{4}$ or $H$ is a
subgraph of $C_{3}$.

######  Lemma 7 ([12, 29]).

Let $G$ be a graph. Then $G\circ K_{2}$ is $1$-planar if and only if $G$ is a
cactus.

###  3.3 Properties for 1-planar graphs

We now present some properties of 1-planar graphs (including optimal 1-planar
graphs).

######  Lemma 8 ([8, 32]).

Let $G$ be a $1$-planar graph with $n$ vertices. Then the maximum number of
edges of $G$ is given by

$\begin{cases}\binom{n}{2}&\textnormal{ if }n\leq 6,\\\ 4n-9&\textnormal{ if
}n\in\\{7,9\\},\\\ 4n-8&\textnormal{ otherwise. }\end{cases}$

Barát and Tóth [3] gave a lower bound on the size of maximal 1-planar graphs.

######  Lemma 9 ([3]).

Let $G$ be a maximal $1$-planar graph with $n\geq 4$ vertices and $m$ edges.
Then $m\geq\frac{20}{9}n-\frac{10}{3}$ edges.

The following lemma is well known and is given as an exercise in the textbook
[35] (see page 160). We ignore its proof here.

######  Lemma 10 ([35]).

Let $G$ be a cactus. Then
$|E(G)|\leq\Bigl{\lfloor}\frac{3(|V(G)|-1)}{2}\Bigl{\rfloor}$.

We say that two 1-planar drawings of a graph are isomorphic if there is a
homeomorphism of the sphere that maps one drawing to the other.

######  Lemma 11.

There are exactly two non-isomorphic $1$-planar drawings $D^{\prime}$ and
$D^{\prime\prime}$ of $K_{3,3}$, as shown in Fig. 1.

(2) $D^{\prime\prime}$(1) $D^{\prime}$ Figure 1: Two non-isomorphic 1-planar
drawings of $K_{3,3}$.

###### Proof.

As seen in Fig. 1, $D^{\prime}$ and $D^{\prime\prime}$ are two non-isomorphic
1-planar drawings of $K_{3,3}$. In what follows, we prove that $K_{3,3}$ has
exactly two 1-planar drawings $D^{\prime}$ and $D^{\prime\prime}$ up to
isomorphic. Let $\\{x,y,z\\}$ and $\\{u,v,w\\}$ be the different partial sets
of $K_{3,3}$, respectively. Clearly, $K_{3,3}$ contains a subgraph, namely
$H$, isomorphic to $K_{2,3}$. Without loss of generality, we denote the vertex
set of $H$ by $\\{x,y,z,u,v\\}$. From [22], we know that $H$ (i.e. $K_{2,3}$)
has three non-isomorphic 1-planar drawings, namely, $D_{1}$, $D_{2}$ and
$D_{3}$, as shown in Fig. 2.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$ Figure 2: Three non-
isomorphic 1-planar drawings of $H$.

We note here that $w$ in $K_{3,3}$ is adjacent to all the three vertices $x,y$
and $z$. First, we claim that any 1-planar drawing of $K_{3,3}$, namely $D$,
does not contain $D_{3}$ as a subdrawing. Otherwise no matter which region $w$
is placed in, one of $wx$, $wy$ and $wz$ will cause some edge in $D_{3}$ to be
crossed at least twice, which contradicts that $D$ is 1-planar.

If a 1-planar drawing of $K_{3,3}$ contains $D_{1}$ as a subdrawing, then $w$
can be placed in $(uxvyu)_{int}$, $(uyvzu)_{int}$, or $(uxvzu)_{out}$. If $w$
is placed in $(uxvyu)_{int}$, then $wx$ and $wy$ must lie in $(uxvyu)_{int}$,
and they do not cross each other (since 1-planar drawings are good). The edge
$wz$ can be chosen to cross one of $ux$, $vx$, $vy$ and $uy$, but no matter
what we choose, the resulting 1-planar drawing of $K_{3,3}$ is isomorphic to
$D^{\prime}$. Similarly, when $w$ is placed in $(uyvzu)_{int}$ or
$(uxvzu)_{out}$, we can see that any resulting 1-planar drawing of $K_{3,3}$
obtained from $D_{1}$ by adding $wx,wy$, and $wz$ is also isomorphic to
$D^{\prime}$.

If a 1-planar drawing, namely $D$, of $K_{3,3}$ contains the subdrawing
$D_{2}$, then clearly $w$ can only be placed in $(ucvxu)_{int}$ or
$(uzcyvxu)_{out}$ where $c$ is the crossing point caused by $uy$ and $vz$. If
$w$ is placed in $(ucvxu)_{int}$, then $wx$ will not cross any other edges.
Furthermore, $wy$ must cross $vx$. If not, then $wy$ will cross $ux$, but now
$wz$ can not be added such that $D$ is 1-planar, a contradiction. We then see
that $wz$ will cross $ux$. By check, the final 1-planar drawing of $K_{3,3}$
is isomorphic to $D^{\prime\prime}$. For if $w$ is placed in
$(uzcyvxu)_{out}$, then $wx$, $wy$ and $wz$ will be non-crossing under $D$,
and thus we get a unique 1-planar drawing (up to non-isomorphic) of $K_{3,3}$
that is isomorphic to $D^{\prime}$.

Therefore, $K_{3,3}$ has exactly two non-isomorphic 1-planar drawings
$D^{\prime}$ and $D^{\prime\prime}$, as desired. ∎

######  Lemma 12.

Let $G$ be an optimal $1$-planar graph. If $G=G_{1}\circ G_{2}$, then $G_{1}$
is connected.

###### Proof.

As any optimal 1-planar graph is clearly connected, $G_{1}$ is a connected
graph by Lemma 2. ∎

######  Lemma 13 ([32]).

Let $G$ be an optimal $1$-planar graph. Then $G$ has a unique $1$-planar
drawing into the sphere, up to isomorphism.

A plane graph is known as a quadrangulation if every face is a 4-face. In [8]
or [32], the authors gave a relationship between optimal 1-planar graphs and
3-connected quadrangulations.

######  Lemma 14 ([8],[32]).

Let $D$ be a $1$-planar drawing of an optimal $1$-planar graph. Then $D$ is
obtained by adding a pair of crossing edges to each face of a $3$-connected
quadrangulation.

By Lemma 13 and Lemma 14, we can see that optimal 1-planar graphs and
3-connected quadrangulations have the one-to-one correspondence.

######  Lemma 15.

Let $G$ be an optimal $1$-planar graph with a $1$-planar drawing $D$. For any
vertex $v$ of $G$, the adjacent edges of $v$ under $D$ alternate between
crossing and non-crossing edges.

###### Proof.

Without loss of generality, we assume that the neighbors of $v$ in clockwise
order under $D$ are $v_{0},v_{1},\cdots,v_{k-1}$. By Lemma 14, only one of
$vv_{i}$ and $vv_{i+1}$ belongs to $E(\mathcal{S}(D))$ where indices are taken
modulo $k$, as desired. ∎

######  Lemma 16.

Let $G$ be an optimal $1$-planar graph and $D$ be a $1$-planar drawing of $G$.
If $v_{0}v_{2}$ crosses $v_{1}v_{3}$ at a crossing point $c$ under $D$, then
the following two statements hold.

  * (i)

$G[v_{0},v_{1},v_{2},v_{3}]\cong K_{4}$ and $v_{0}v_{1},v_{1}v_{2},v_{2}v_{3}$
and $v_{3}v_{1}$ are non-crossing under $D$;

  * (ii)

$cv_{i}v_{i+1}$ bounds a crossed face of $D$ with indices taken modulo $4$.

###### Proof.

For (i), it is clear to see that $v_{0}v_{1}v_{2}v_{3}v_{0}$ is a 4 cycle in
the planar skeleton $\mathcal{S}(D)$ by Lemma 14. So (i) holds.

For (ii), by Lemma 14, $v_{0}v_{1}v_{2}v_{3}v_{0}$ bounds a 4-face in
$\mathcal{S}(D)$ that only contains the pair of crossing edges $v_{0}v_{2}$
and $v_{1}v_{3}$. Hence, the region bounded by $v_{i}v_{i+1}$, $cv_{i}$ and
$cv_{i+1}$ where $1\leq i\leq 4$ cannot contain any vertex. So (ii) holds. ∎

######  Lemma 17.

Let $G$ be an optimal $1$-planar graph with a $1$-planar drawing $D$. Let $C$
be a cycle of $G$. If $C$ is non-crossing under $D$, then $C$ is an even
cycle.

###### Proof.

By Lemma 14, the planar skeleton $\mathcal{S}(D)$ is a quadrangulation.
Clearly, any cycle of $\mathcal{S}(D)$ is even. Since $C$ is non-crossing
under $D$, $C$ is a cycle in $\mathcal{S}(D)$, and thus $C$ is an even cycle
of $G$, as desired. ∎

##  4 Proof of main results

In this section, we prove Theorem 1 and three corollaries.

Proof of Theorem 1. First, the “if” part is easily proved. We can check easily
that $K_{2,2,2,2}$ is optimal 1-planar (see Fig. 3) and $K_{2,2,2,2}$ is
reducible since clearly $K_{2,2,2,2}=K_{4}\circ 2K_{1}$ or
$K_{2,2,2,2}=K_{2}\circ C_{4}$.

We now prove the “only if” part. We assume that $G=G_{1}\circ G_{2}$ where
$G_{1}$ and $G_{2}$ are two graphs such that $|V(G_{1})|\geq 2$ and
$|V(G_{2})|\geq 2$. Furthermore, we discuss the reducibility of $G$ in terms
of the number of vertices of (the possible) left factor $G_{1}$ and right
factor $G_{2}$, which corresponds to the following Case 1, Case 2 and Case 3,
respectively.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$ Figure 3: A 1-planar
drawing of $K_{2,2,2,2}$.

######  Case 1.

$|V(G_{1})|=2$ and $|V(G_{2})|\geq 2$.

In this case, we claim that $G\cong K_{2,2,2,2}$. As $G_{1}$ is connected by
Lemma 12 and $G_{1}$ has exactly 2 vertices, $G_{1}$ is isomorphic to $K_{2}$.
By Lemma 5, $G_{2}$ has at most $4$ vertices. As $G$ has at least 8 vertices
by Lemma 8 and $G_{1}\cong K_{2}$, $G_{2}$ has at least 4 vertices. So $G_{2}$
has exactly 4 vertices, and hence $G$ has exactly 8 vertices. By “optimality”
of $G$, $G$ has 24 ($=4\times 8-8$) edges. Hence, $G_{2}$ has 4 edges by Lemma
1. So $G_{2}$ is isomorphic to $C_{4}$ or a $C_{3}$ with a pendant edge.
Furthermore, $G_{2}$ must be isomorphic to $C_{4}$ by Lemma 6, and thus
$G\cong K_{2,2,2,2}$. Note that $K_{2,2,2,2}$ is optimal 1-planar and
$K_{2,2,2,2}=K_{2}\circ C_{4}$. Thus, the claim holds.

######  Case 2.

$|V(G_{1})|\geq 3$ and $|V(G_{2})|\geq 3$.

In this case, we will prove that $G$ is not the lexicographic product of
$G_{1}$ and $G_{2}$. Suppose for a contradiction that $G=G_{1}\circ G_{2}$. If
$|V(G_{2})|\geq 4$, then $G_{1}\circ G_{2}$ is not 1-planar by Lemma 4, a
contradiction. Hence, we shall consider $|V(G_{2})|=3$.

Let $\\{u_{1},u_{2},\cdots,u_{k}\\}$ where $k\geq 3$ and
$\\{v_{1},v_{2},v_{3}\\}$ be vertex sets of $G_{1}$ and $G_{2}$, respectively.
By Lemma 12, $G_{1}$ is connected. Hence, there is an edge $u_{i}u_{j}$ for
$1\leq i\neq j\leq k$ in $G_{1}$. Since $|V(G_{2})|\geq 3$, then $G$ contains
a subgraph $T$ isomorphic to $K_{3,3}$ where two parts of $T$ are
$X:=\\{(u_{i},v_{1}),(u_{i},v_{2}),(u_{i},v_{3}$)} and
$Y:=\\{(u_{j},v_{1}),(u_{j},v_{2}),(u_{j},v_{3})\\}$. For brevity, in the
following we relabel the vertices of $X$ as $u,v,w$, and relabel the vertices
of $Y$ as $x,y,z$.

The following two claims are obtained directly from Lemma 3.

######  Claim 1.

If a vertex $p$ of $G$ is adjacent to one vertex of $X$ (resp. $Y$), then $p$
is adjacent to all vertices of $X$ (resp. $Y$).

######  Claim 2.

The induced graph $G[\\{x,y,z\\}]\cong G[\\{u,v,w\\}]$.

By Lemma 11, there are two possible restricted drawings (A1) and (A2) of $D|T$
as shown in Fig. 4.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)
Figure 4: Two possible restricted 1-planar drawings of $D|T$.

First, we claim that the drawing $D$ does not contain (A2) as a subdrawing.
Otherwise by Lemma 16 (i), $xyzx$ will be a non-crossing 3-cycle in $D$, which
contradicts to Lemma 17. Hence, $D$ contains (A1) as a subdrawing.
Furthermore, since $xv$ crosses $uy$ in $D|H$, $uv$ and $xy$ are edges of $G$,
and they are non-crossing under $D$ by Lemma 16 (i). Similarly, $ux$ and $vy$
are also non-crossing under $D$.

Let $H$ be the subgraph of $G$ obtained from $T$ by adding two edges $xy$ and
$uv$. Based on the analysis above, $D$ contains the restricted drawing $D|H$
as shown in Fig 5.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$
Figure 5: The subdrawing $D|H$.

Combing Lemma 16 (i) with the fact that $uv$ is non-crossing under $D$, at
least one of $uz$ and $vz$ is crossing under $D$. Since $uz$ and $vz$ are
symmetrical in $D|H$, we assume without loss of generality that $uz$ is
crossed by some edge, denoted by $st$, under $D$.

By symmetry of the vertex-ends $s$ and $t$, we discuss 5 cases according to
whether $s$ and $t$ are vertices of $H$. Based on the assumption that $D$ is a
1-planar drawing, we observe that if $s$ or $t$ is in $V(H)$, then they may
only be $v$, $w$ or $x$.

Case 2.1. $s\notin V(H)$ and $t\notin V(H)$. We may assume that $s$ lies in
$(uvzu)_{int}$ and $t$ lies in $(uvzu)_{out}$, see Fig. 6 (1). As $st$ crosses
$uz$, $su$ will be a non-crossing edge under $D$ by Lemma 16 (i). By Claim 1,
$sw$ and $sv$ are edges of $G$. Since $uv$ is non-crossing under $D$ and $uz$
has been crossed by $st$, $sw$ must cross $vz$, and hence $sv$ is non-crossing
under $D$ by Lemma 16. Thus, edges $uv$, $su$ and $sv$ form a non-crossing
3-cycle under $D$; this contradicts to Lemma 17.

Case 2.2. $s\notin V(H)$ and $t=w$.

In this case, $s$ must lie in $(uvzu)_{int}$, see Fig. 6 (2). The vertex $s$
is adjacent to $z$ in $G$ by Lemma 16 (i), since $sw$ is crossed by $uz$. By
Claim 1, $sx$ is an edge of $G$. But clearly $sx$ will be crossed twice or
will cause at least one edge on $D|H$ to be crossed at least twice; this
contradicts that $D$ is 1-planar.

Case 2.3. $s\notin V(H)$ and $t=x$.

In this case, $s$ lies in $(uvzu)_{int}$, see Fig. 6 (3). Since $sx$ crosses
$uz$, $sz$ and $su$ is an edge of $G$ by Lemma 16 (i). By Claim 1, $sy$ and
$sw$ are edges of $G$. As $uz$ has been crossed and $uv$ is non-crossing under
$D$, one of $sy$ and $sw$, say $sy$, must cross $vz$, and hence the other edge
$sw$ will be crossed twice or will cause at least one edge on $D|H$ to be
crossed at least twice; this contradicts that $D$ is 1-planar.

Case 2.4. $s=v$ and $t\notin V(H)$.

In this case, $uz$ is crossed by $tv$, and $t$ must lie in $(uxwzu)_{out}$. By
Lemma 16 (i), $tz$ and $tu$ are edges of $G$, and both $vz$ and $tu$ are non-
crossing under $D$. Furthermore, by Claim 1, $ty$ is an edge of $G$. We then
see that $sy$ crosses $wz$ or $wx$. If $ty$ crosses $wz$, then $yz$ is a non-
crossing edge under $D$ by Lemma 16 (i), and hence $vy$, $vz$ and $yz$ form a
non-crossing 3-cycle under $D$, see Fig.6 (4); this contradicts to Lemma 17.
If $ty$ crosses $wz$, then $tx$ are a non-crossing edge under $D$ by Lemma 16
(i), see Fig.6 (5). But now $tu$, $ux$ and $tx$ form a non-crossing 3-cycle
under $D$; this contradicts to Lemma 17.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$
Figure 6: The possible six subdrawings involving the crossing edge $uz$.

Case 2.5. $s=v$ and $t=w$.

In this case, since $vw$ crosses $uz$, $uw$ is an edge of $G$ and $vz$ is non-
crossing under $D$ by Lemma 16 (i), see Fig. 6 (6). Now we observe that
$G[\\{u,v,w\\}]\cong C_{3}$, and thus $G[\\{x,y,z\\}]$ is also isomorphic to
$C_{3}$ by Claim 2. Hence, $yz$ and $xy$ are edges of $G$. We see that $xz$
must cross $wy$, and thus $yz$ is non-crossing under $D$ by Lemma 16. Recall
that $vy$ is also non-crossing under $D$. Thus, $yvzy$ is a non-crossing
3-cycle under $D$; this contradicts to Lemma 17.

So far, we have discussed all possible cases, and they all derive
contradictions. Therefore, $G$ is not the lexicographic product of $G_{1}$ and
$G_{2}$, as desired.

######  Case 3.

$|V(G_{1})|\geq 3$ and $|V(G_{2})|=2$.

In this case, we shall prove that $G\cong K_{2,2,2,2}$ if $G=G_{1}\circ
G_{2}$. Since $|V(G)|\geq 8$ by Lemma 8 and $|V(G_{2})|=2$, we have
$|V(G_{1})|\geq 4$. First we claim that $G_{2}$ is not isomorphic to $K_{2}$.
If $G_{2}\cong K_{2}$, then combing Lemma 1 with the optimality of $G$, we
have $|V(G_{1})|+4\times|E(G_{1})|=|E(G)|=4\times(2\times|V(G_{1})|)-8$, which
implies that

$|E(G_{1})|=\frac{7}{4}|V(G_{1})|-2.$ (4.1)

By Lemma 7, $G_{1}$ must be a cactus. Then, by Lemma 10, we have

$|E(G_{1})|\leq\Bigl{\lfloor}\frac{3(|V(G_{1})|-1)}{2}\Bigl{\rfloor}.$ (4.2)

Combing (4.1) with (4.2), we have $|V(G_{1})|\leq 2,$ a contradiction to that
$|V(G_{1})|\geq 4$. Hence, $G_{2}\cong 2K_{1}$.

Let $V(G_{1}):=\\{u_{1},u_{2},\cdots,u_{n}\\}$ where $n\geq 4$ and
$V(G_{2}):=\\{v_{1},v_{2}\\}$. By Lemma 2, $G_{1}$ is connected. Hence,
$G_{1}$ has an edge $u_{i}u_{j}$ for $1\leq i\neq j\leq n$. Then vertices
$u_{i}$ (resp. $u_{j}$) is substituted with two vertices $(u_{i},v_{1})$ and
$(u_{i},v_{2})$ in $G$ (resp. $(u_{j},v_{1})$ and $(u_{j},v_{2})$ in $G$). For
simplicity, we set $u:=(u_{i},v_{1})$, $v:=(u_{i},v_{2})$, $x:=(u_{j},v_{1})$
and $y:=(u_{j},v_{2})$. Denote the vertices of $V(G)\setminus\\{u,v,x,y\\}$ by
$\\{w_{1},w_{2},\cdots,w_{2n-4}\\}$.

Below, we give three simple claims.

######  Claim 3.

If a vertex $p$ of $G$ is adjacent to one vertex of $\\{u,v\\}$ (resp. of
$\\{x,y\\}$), then $p$ is also adjacent to the other vertex of $\\{u,v\\}$
(resp. of $\\{x,y\\}$).

###### Proof.

This claim follows directly from Lemma 3 (ii). ∎

######  Claim 4.

The edge $uv\notin E(G)$ and $xy\notin E(G)$.

###### Proof.

By Lemma 3 (i), both $G[u,v]$ and $G[x,y]$ are isomorphic to $2K_{1}$, as
desired. ∎

######  Claim 5.

The graph $G[u,v,x,y]\cong C_{4}$.

###### Proof.

By the definition of lexicographic products, $ux$, $xv$, $vy$ and $yu$ are
edges of $G$. So these edges form a 4-cycle of $G$. By Claim 4, both $uv$ and
$xy$ are not edges of $G$. Hence $G[u,v,x,y]\cong C_{4}$, as desired. ∎

Hence, we denote the 4-cycle $uxvyu$ of $G$ by $C$. Below our attention is
directed toward the cycle $C$.

First we show that $C$ will not cross itself under $D$. Since $D$ is good, any
two successive edges of $C$ will not cross each other. For if two non-
successive edges of $C$ cross each other, then $G[u,v,x,y]\cong K_{4}$ by
Lemma 16 (i), and thus $uv$ is an edge of $G$; this contradicts to Claim 4.

We now show that $C$ is crossing under $D$. Suppose that $C$ is non-crossing
under $D$. We choose an adjacent edge of $u$, namely $uw_{1}$, such that
$uw_{1}$ is closest to $ux$ in cyclic order (clockwise). By Lemma 15, $uw_{1}$
is crossing under $D$, and thus $w_{1}\neq y$ (since $C$ is non-crossing under
$D$). Furthermore, Claim 4 implies that $w_{1}$ is not $v$. So $w_{1}$ lies in
$C_{int}$, see Fig 7 (a). Without loss of generality, we assume that $uw_{1}$
is crossed by $w_{2}w_{3}$. We notice that any one of vertex-ends of
$w_{2}w_{3}$ is not $v$; otherwise, $uv$ will be an edge by Lemma 16 (i),
which contradicts to Claim 4. Furthermore, we discuss the following three
possible cases, all of which will yield contradictions

Case 3.1. $w_{i}\neq x$ and $w_{i}\neq y$ for $i=2,3$.

We denote by $c$ the crossing point created by $uw_{1}$ and $w_{2}w_{3}$. By
Lemma 16 (i), $uw_{2}$ and $ww_{3}$ are non-crossing edges under $D$. If one
of $uw_{2}$ and $uw_{3}$, say $w_{2}$, is drawn between $uw_{1}$ and $ux$ in
clockwise, then $uw_{2}$ is closer to $ux$ in clockwise order, which
contradicts the choice of $uw_{1}$, see Fig. 7 (b). If both $uw_{2}$ and
$uw_{3}$ are not drawn between $uw_{1}$ and $ux$ in clockwise, then
$(uw_{2}cu)_{out}$ (or $(uw_{3}cu)_{out}$) contains the vertex $x$; see Fig 7
(b), and thus $(uw_{2}cu)_{out}$ (or $(uw_{3}cu)_{out}$) will not be a crossed
3-face of $D$, and this contradicts to Lemma 16 (ii).

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$
Figure 7:  The non-crossing $4$-cycle $C$ involving the crossing edge $uw_{1}$
under $D$.

Case 3.2. $w_{i}\neq x$ and $w_{j}=y$ for $2\leq i\neq j\leq 3$.

Similar to Case 3.1, it will also lead a contradiction. We leave the readers
to prove it.

Case 3.3. $w_{2}=x$ or $w_{3}=x$.

Without loss of generality, we assume that $w_{2}=x$. By Claim 4, $w_{3}\neq
y$, and thus $w_{3}$ must lie in $C_{int}$, see Fig. 7 (d). By Lemma 16 (i),
$uw_{3}$ and $xw_{1}$ are non-crossing edges under $D$. By Claim 3, $w_{1}y$,
$w_{3}v$ and $w_{3}y$ are edges of $G$. As $C$ is non-crossing under $D$,
$w_{1}y$ must cross $w_{3}v$, and thus $w_{3}y$ is non-crossing under $D$ by
Lemma 16 (i). Observe that $uyw_{3}u$ is a non-crossing 3-cycle under $D$,
which contradicts Lemma 17.

From the analysis above, we have seen that all possible cases derive
contradictions. Therefore, $C$ is crossing under $D$. That is to say, there
exists some edge of $C$ that is crossing under $D$. Without loss of
generality, we assume that $ux$ is crossed by some edge, namely $w_{1}w_{2}$.
Furthermore, we claim that $w_{i}\notin V(C)$ for $i=1,2$. As $D$ is good,
$w_{i}\neq u$ and $w_{i}\neq x$ for $i=1,2$. If some end-vertex of
$w_{1}w_{2}$, says $w_{1}$, is $v$, then $w_{2}\neq y$, otherwise $C$ is self-
crossing under $D$, a contradiction (earlier, we have proved that $C$ is not
self-crossing under $D$). Thus, $w_{2}\notin V(C)$, but now $uv$ must be an
edge of $G$ by Lemma 16 (i), since $v(=w_{1})w_{2}$ crosses $ux$; this
contradicts to Claim 3. By symmetry of $w_{1}$ and $w_{2}$, we also have
$w_{2}\neq v$. Similarly, $w_{i}\neq y$ for $i=1,2$. So $w_{i}\notin V(C)$ for
$i=1,2$. Thus, we may assume that $w_{1}$ and $w_{2}$ lie in the exterior and
in the interior of $C$, respectively. We immediately get the following claim.

######  Claim 6.

The $1$-planar drawing $D$ contains the subdrawing $F$, as shown in Fig. 8.

###### Proof.

By Lemma 16 (i), $w_{1}u$, $w_{1}x$, $w_{2}u$ and $w_{2}x$ are non-crossing
edges under $D$. By Claim 3, $w_{1}y$, $w_{1}v$ $w_{2}v$ and $w_{2}y$ are
edges of $G$. The edge $w_{2}v$ cannot cross $vx$ or $vy$ since $D$ is good,
and $w_{2}v$ also cannot cross $uy$ otherwise $uv$ will be an edge of $G$ by
Lemma 16 (i), which contradicts Claim 4. So $w_{2}v$ must be placed in
$C_{int}$. Similarly, $w_{2}y$ is also placed in $C_{int}$. Now we observe
that both $w_{1}y$ and $w_{1}v$ cannot cross by any one edge of $uy$, $vx$ and
$vy$, and thus they lie in $(w_{1}uyvw_{1})_{out}$. Thus, $D$ contains the
subdrawing $F$ as shown in Fig. 8. ∎

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$
Figure 8: The subdrawing $F$.

######  Remark 1.

Notice that the $1$-planar drawing $F$ in Claim 6 may also be drawn as $F^{1}$
or $F^{2}$ as shown in Fig 9, but they are isomorphic to $F$. If we consider
$F^{1}$ or $F^{2}$, then some insignificant details in the following proof
need to be adjusted. For example, if we consider $F^{1}$, then $v$ is in the
“interior” of $w_{1}uyw_{1}$ whereas $v$ is in the “exterior” of
$w_{1}uyw_{1}$ if we consider $F$. But it does not affect the correctness of
our proof. So in the following we only consider $F$.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$
Figure 9: Two subdrawings $F^{1}$ and $F^{2}$.

We now show that the cycle $C$ has at least two crossing edges under $D$.
Suppose that $C$ has the unique crossing edge $ux$ under $D$. That is to say,
$uy$, $vx$ and $vy$ are non-crossing under $D$. First, by Claim 6, $D$
contains $F$ as a subdrawing. We claim that $w_{2}y$ is crossed by some edge,
say $w_{3}w_{4}$; otherwise, $uw_{2}yu$ is a non-crossing 3-cycle under $D$
(note that $uy$ and $uw_{2}$ are non-crossing), a contradiction to Lemma 17.
Furthermore, we claim that one of $w_{3}$ and $w_{4}$ is $u$. If not, then one
of $w_{3}$ and $w_{4}$, say $w_{3}$, lies in $(uw_{2}yu)_{int}$. By Lemma 16
(i), $w_{3}y$ is an edge, and thus $w_{3}x$ will be an edge of $G$. But
$w_{3}x$ will cross at least two times; this contradicts that $D$ is 1-planar.
Thus, $w_{3}=u$ or $w_{4}=u$. Without loss generality, we assume that
$w_{3}=u$. By Claim 3, $w_{4}\neq v$, and thus $w_{4}$ must lie in
$(w_{2}yvw_{2})_{int}$, see Fig. 10. Furthermore, $w_{4}y$ is a non-crossing
edge under $D$ by Lemma 16 (i), and thus $w_{4}x$ is also an edge by Claim 3.
Now we see that $w_{4}x$ must cross $w_{2}v$, and hence $w_{4}v$ is a non-
crossing edge under $D$ by Lemma 16 (i). Note that $vy$ is also non-crossing
under $D$. So $yvw_{4}y$ is a non-crossing 3-cycle under $D$, which
contradicts Lemma 17. Therefore, $C$ has at least two crossing edges under
$D$.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$
Figure 10: The edge $w_{2}y$ is crossed by $uw_{4}$.

Now, we will prove that both the two edges $vx$ and $uy$ (on $C$) are non-
crossing under $D$. Note that $D$ contains the subdrawing $F$. As $vx$ and
$uy$ are symmetric in $F$, we need only consider $vx$. We assume that $vx$ is
crossed by some edge, namely $w_{3}w_{4}$, see Fig. 11. We can observe that if
$w_{i}\in V(F)$ for $i=3$ or $i=4$, then they can only be $w_{1}$ or $w_{2}$.
In the following, it is sufficient to consider three cases.

Case 3.4. $w_{3}\notin V(F)$ and $w_{4}\notin V(F)$.

Without loss of generality, we may assume that $w_{3}$ and $w_{4}$ lie in
$(xvw_{2}x)_{int}$ and $(xvw_{2}x)_{out}$, respectively; see Fig 11 (a). Since
$w_{3}w_{4}$ crosses $vx$, $w_{3}v$ is an edge of $G$ by Lemma 16 (i), and
thus $w_{3}u$ is an edge of $G$ by Claim 3. But now $u_{3}u$ will be crossed
at least two times, a contradiction.

Case 3.5. $w_{3}\notin V(F)$ and $w_{4}=w_{1}$.

Similar to Case 3.3, $u_{3}u$ will also be crossed at least two times, a
contradiction; see Fig 11 (b).

Case 3.6. $w_{3}=w_{2}$.

In this case, $w_{4}\notin V(F)$, otherwise $G$ will have multiedges. Since
$D$ is 1-planar, $w_{4}$ must lie in $(xvw_{1}x)_{int}$, see Fig 11 (c). Since
$w_{2}~{}(=w_{3})w_{4}$ crosses $vx$, $w_{4}v$ is an edge of $G$ by Lemma 16
(i), and thus $w_{4}u$ is an edge of $G$ by Claim 3. But $u_{4}u$ will be
crossed at least two times, a contradiction.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)$w_{4}$$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$(c)$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$(b)$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$
Figure 11: Three 1-planar drawings involving the crossing edge $xv$.

Thus, $xv$ is non-crossing under $D$. Similarly, $uy$ is also non-crossing
under $D$.

Note that earlier we proved that at least two edges of $C$ are crossing under
$D$. Hence, the edge $vy$ on $C$ must be crossed by some edge, namely
$w_{3}w_{4}$. We now prove that $w_{3}\notin V(F)$ and $w_{4}\notin V(F)$.
Since $w_{3}w_{4}$ has been crossed by $vy$, we see that if $w_{3}$ or $w_{4}$
belongs $V(F)$, then they can only be $w_{1}$ or $w_{2}$. Without loss of
generality, we may assume that $w_{3}=w_{1}$, and thus $w_{4}\neq w_{2}$ by
simplify of $G$. Thus, $w_{4}$ must lie in $(w_{2}vyw_{2})_{int}$, see Fig. 12
(a). By Lemma 16 (i), $w_{1}v$ will be a non-crossing edge under $D$. Note
that we have proved that $w_{1}x$ and $uy$ are non-crossing under $D$. So the
cycle $vw_{1}yv$ is a non-crossing 3-cycle under $D$, which contradicts Lemma
17. As for if $w_{3}=w_{2}$, then similarly, we will similarly find a non-
crossing 3-cycle $w_{2}uyw_{2}$ under $D$, a contradiction; see Fig. 12 (b).
By symmetry, $w_{4}\neq w_{i}$ for $i=1,2$. Therefore, $w_{3}\notin V(F)$ and
$w_{4}\notin V(F)$.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)$w_{4}$$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$(c)$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$(b)$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)(b)
Figure 12: (a) The vertex $w_{3}=w_{1}$. (b) The vertex $w_{3}=w_{2}$.

So we may assume that $w_{3}$ and $w_{4}$ lie in $(w_{2}vyw_{2})_{out}$ and
$(w_{2}yvw_{2})_{int}$, respectively. Furthermore, $w_{3}$ must lie in
$(w_{1}yvw_{1})_{out}$, since $D$ is 1-planar and $w_{3}w_{4}$ has been
crossed by $vy$.

Finally, we prove that $G\cong K_{2,2,2,2}$. Similar to Claim 6, all vertices
of $C$, together with $w_{3}$ and $w_{4}$ and their edges will also form a
subdrawing of $D$ isomorphic to $F$. So $D$ contains a 1-planar drawing
$F^{\prime}$ as shown in Fig. 13.

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)$w_{4}$$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$(c)$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$(b)$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)(b)$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$$w_{3}$
Figure 13:  The 1-planar drawing $F^{\prime}$.

In $F^{\prime}$, since $w_{1}v$ crosses $w_{3}x$, $w_{1}w_{3}$ will be a non-
crossing edge under $D$ by Lemma16 (i). Similarly, $w_{2}w_{4}$ is also a non-
crossing edge under $D$. We called final 1-planar drawing $F^{\prime\prime}$
obtained from $F^{\prime}$ by adding two non-crossing edges $w_{1}w_{3}$ and
$w_{2}w_{4}$. We notice that every face of $F^{\prime}$ is a crossed 3-face.
Hence, $G$ does not have any other new vertex by Lemma 16 (ii), and obviously
we also cannot add any new edge in $F^{\prime\prime}$. So $D$ is isomorphic to
$F^{\prime\prime}$, and thus $G$ is isomorphic to $K_{2,2,2,2}$. Finally, it
is easy to see that $K_{2,2,2,2}=K_{4}\circ 2K_{1}$, $|V(K_{4})|=4\geq 3$ and
$|V(2K_{1})|=2$. Therefore, we complete the proof of Case 3.

The “only if” part of Theorem 1 follows directly from Case 1, Case 2 and Case
3.

Therefore, we have proved Theorem 1. $\Box$

Here, we prove Corollaries 1, 2 and 3.

Proof of Corollary 1. For (i), if $n=8$, then $m\leq 4\times 8-8=24$ by Lemma
8. By Theorem 1, $K_{2,2,2,2}$ is a reducible 1-planar graph with $8$ vertices
and $24$ edges, and thus “24” is tight.

For (ii), if $n\geq 10$, then $m\leq 4n-8$ by Lemma 8. Theorem 1 implies that
any optimal $1$-planar graph is irreducible if it has at least $10$ vertices,
and thus $m\leq 4n-9$ for $n\geq 10$ (since $G$ is reducible). For if $n=9$,
then any 1-planar graph with $9$ vertices has at most $4\times 9-9$ edges, and
thus $m\leq 4\times 9-9$ by Lemma 8. As for $n=6$, we have
$m\leq\binom{6}{2}=15=4\times 6-9$ by Lemma 8. Below we show that the bound
$4n-9$ is tight. Let $P_{\frac{n}{3}}$ be a path with $\frac{n}{3}$ vertices
where $n\geq 3$ and $n\equiv 0~{}(\mod 3)$. We denote the vertex set of
$P_{\frac{n}{3}}$ by $\\{u_{1},u_{2},\cdots,u_{\frac{n}{3}}\\}$. Let
$H=P_{\frac{n}{3}}\circ C_{3}$. Clearly, $H$ is reducible and has $4n-9$
edges. We demonstrate a construction of 1-planar drawing of $H$ in Fig. 14. In
Fig. 14, $C_{u_{i}}$ is a 3-cycle in $H$ that corresponds to the vertex
$u_{i}$ in $P_{\frac{n}{3}}$ for $1\leq i\leq\frac{n}{3}$. Thus, the bound
$4n-9$ is tight for every $k\geq 2$ and $n=3k$. $\Box$

(2) $D^{\prime\prime}$(1) $D^{\prime}$(a) $D_{1}$(b) $D_{2}$(c)
$D_{3}$$u$$v$$x$$y$$z$$x$$y$$z$$u$$v$$x$$y$$z$$u$$v$$c$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(A1)(A2)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(1)$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$$u$$v$$w$$x$$y$$z$(4)(5)(2)(3)(6)$s$$t$$t$$t$$c$$c$$c$$c$$c$$c$$s$$s$$u$$x$$y$$v$$w_{1}$$w_{3}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$u$$x$$y$$v$$w_{1}$$w_{3}$$w_{2}$$c$$u$$x$$y$$v$$w_{1}$(a)(b)(c)(d)$c$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$F^{1}$$F^{2}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)$w_{4}$$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$(c)$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$(b)$w_{3}$$u$$x$$y$$v$$w_{2}$$w_{1}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$(a)(b)$u$$x$$y$$v$$w_{2}$$w_{1}$$w_{4}$$w_{3}$$\vdots$$C_{u_{1}}$$C_{u_{2}}$$C_{u_{3}}$$\vdots$$C_{u_{1}}$$C_{u_{2}}$$C_{u_{3}}$$\rightarrow$
Figure 14:  A planar drawing of $\frac{n}{3}$ disjoint copies of $C_{3}$ on
the left and a 1-planar drawing of $H$ on the right.

Proof of Corollary 2. For (i), from the proof in Theorem 1, $K_{4}\circ
2K_{1}\cong K_{2,2,2,2}$ and $K_{2,2,2,2}$ is 1-planar, and thus $K_{4}\circ
2K_{1}$ is 1-planar. So for any subgraph $H$ of $K_{4}$, $H\circ 2K_{1}$ is
1-planar. Hence, for any graph $G$ with exactly $2$ vertices or $3$ vertices,
we have $m\leq 2n-3$, and for any graph $G$ with exactly $4$ vertices, we have
$m\leq 6.$ For $n\geq 5$, by Theorem 1, $G\circ 2K_{1}$ is not optimal a
1-planar graph. Thus, $|E(G\circ 2K_{1})|\leq 4\times(2n)-9$. Note that
$|E(G\circ 2K_{1})|=4m$ by Lemma 1. Therefore, we have $4m\leq 8n-9$, and thus
$m\leq\lfloor\frac{8n-9}{4}\rfloor=2n-3$, as desired.

For (ii), note that any subgraph of a 1-planar graph is 1-planar, and thus
(ii) follows directly from (i). $\Box$

Proof of Corollary 3. Clearly, $G\circ 2K_{1}$ contains $G$ as a subgraph by
the definition of the lexicographic products. So if $G\circ 2K_{1}$ is
1-planar, then $G$ is 1-planar (any subgraph of a 1-planar graph is also
1-planar). Suppose $G$ is maximal 1-planar with $n\geq 17$ vertices. Then
$|E(G)|\geq\frac{20}{9}n-\frac{10}{3}$ by Lemma 9. But
$\frac{20}{9}n-\frac{10}{3}>2n-3$ for any integer $n\geq 17$, a contradiction
to Corollary 2. So $G$ can not be a maximal 1-planar graph for $n\geq 17$.
$\Box$

##  5  Further problems

In this article, we characterize the reducibility of optimal 1-planar graphs.
Let $G$ be a graph with $n$ vertices and $m$ edges. As a result, we prove that
if $G\circ 2K_{1}$ is 1-planar, then $m\leq 2n-3$ for $n\geq 2$ and $n\neq 4$
and $m\leq 6~{}(=2n-2)$ for $n=4$. Clearly, when $n=2$ or $n=3$, the upper
bound $2n-3$ can be achieved. However, for $n\geq 5$, the following problem
remains:

######  Problem 2.

In Corollary 2, is the upper bound “ $2n-3$” for $n\geq 5$ tight?

From the viewpoint of the reverse process of lexicographic products, the above
problem is equivalent to asking whether there exist some 1-planar graphs with
even $n$ vertices and $4n-12$ edges that can be written as the lexicographic
product of a graph and $2K_{1}$.

Corollary 3 shows us that for $n\geq 17$, $G$ is not maximal 1-planar if
$G\circ 2K_{1}$ is 1-planar. As for $n\leq 4$, $G$ can be a complete graph by
Corollary 2 if $G\circ 2K_{1}$ is 1-planar, and thus $G$ can be maximal
1-planar if $G\circ 2K_{1}$ is 1-planar. Then the following problem is
natural.

######  Problem 3.

For an integer $n$ where $5\leq n\leq 16$, is there a maximal $1$-planar graph
$G$ with $n$ vertices such that $G\circ 2K_{1}$ is $1$-planar?

In another direction, it is natural to consider extending our results (the
reducibility of optimal $1$-planar graphs) to optimal $k$-planar graphs for
$k\geq 2$. In particular, the structure of optimal 2-planar graphs and optimal
3-planar graphs are somewhat clear, see [4]. Their reducibility might be
characterized in the future. It is also interesting to characterize the
reducibility of optimal $k$-planar graphs with respect to other three standard
graph products namely, the Cartesian product, the direct product and the
strong product.

##  6 Acknowledgment

We claim that there is no conflict of interest in our paper. No data was used
for the research described in the article.

## References

  * [1] E. Ackerman, A note on 1-planar graphs, Discrete Appl. Math. 175 (2014), 104–108.
  * [2] L. Babai, Graph isomorphism in quasipolynomial time, in: Proc. 48th Annu. ACM Symp. Theory Comput., pp. 684–697.
  * [3] J. Barát, G. Tóth, Improvements on the density of maximal 1-planar graphs, J. Graph Theory 88 (2018), 101–109.
  * [4] M. A. Bekos, M. Kaufmann, C. N. Raftopoulou, On optimal 2- and 3-planar graphs, in: SoCG 2017, in: LIPIcs, vol. 77, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017, pp. 16:1–16:16.
  * [5] M. A. Bekos, M. Kaufmann, C. Zielke, The book embedding problem from a SAT-solving perspective, in: Proc. 23rd Intl. Symp. on Graph Drawing and Network Visualization, in: LNCS, vol. 9411, Springer Verlag, 2015, pp. 125–138.
  * [6] T. Biedl, J. Wittnebel, Matchings in 1-planar graphs with large minimum degree, J. Graph Theory 99 (2022), 217–230.
  * [7] C. Binucci, W. Didimo, F. Montecchiani, 1-planarity testing and embedding: An experimental study, Comput. Geom. 108 (2023).
  * [8] R. Bodendiek, H. Schumacher, K. Wagner, Bemerkungen zu einem Sechsfarbenproblem von G. Ringel, Abh. Math. Semin. Univ. Hamb. 53 (1983), 41–52.
  * [9] O. V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995), 507–521.
  * [10] F. J. Brandenburg, Recognizing optimal 1-planar graphs in linear time, Algorithmica 80 (2018), 1–28.
  * [11] F. J. Brandenburg, D. Eppstein, A. Gleißner, M. T. Goodrich, K. Hanauer, J. Reislhuber, On the density of maximal 1-planar graphs, in: International Symposium on Graph Drawing, Springer, 2012, pp. 327–338.
  * [12] J. Bucko, J. Czap, 1-planar lexicographic products of graphs, Appl. Math. Sci. 9 (2015), 5441–5449.
  * [13] J. Czap, D. Hudák, 1-planarity of complete multipartite graphs, Discrete Appl. Math. 160 (2012), 505–512.
  * [14] J. Czap, D. Hudák, On drawings and decompositions of 1-planar graphs, Electron. J. Comb. 20 (2013), P54.
  * [15] J. Czap, D. Hudák, T. Madaras, Joins of 1-planar graphs, Acta Math. Sin., Engl. Ser. 30 (2014), 1867–1876.
  * [16] W. Didimo, Density of straight-line 1-planar graph drawings, Inf. Process. Lett. 113 (2013), 236–240.
  * [17] J. Feigenbaum, A. A. Schäffer, Recognizing composite graphs is equivalent to testing graph isomorphism, SIAM J. Comput. 15 (1986), 619–627.
  * [18] J. Fujisawa, K. Segawa, Y. Suzuki, The matching extendability of optimal 1-planar graphs, Graphs Combin. 34 (2018), 1089–1099.
  * [19] J. P. Gollin, K. Hendrey, A. Methuku, C. Tompkins, X. Zhang, Counting cliques in $1$-planar graphs, arXiv preprint, arXiv:2109.02906.
  * [20] A. Grigoriev, H. L. Bodlaender, Algorithms for graphs embeddable with few crossings per edge, Algorithmica 49 (2007), 1–11.
  * [21] R. H. Hammack, W. Imrich, S. Klavžar, W. Imrich, S. Klavžar, Handbook of Product Graphs, Vol. 2, CRC press Boca Raton, 2011.
  * [22] H. Harborth, Parity of numbers of crossings for complete $n$-partite graphs, Math. Slovaca 26 (1976), 77–95.
  * [23] Y. Huang, Z. Ouyang, F. Dong, On the size of matchings in 1-planar graph with high minimum degree, SIAM J. Discrete Math. 36 (2022), 2570–2584.
  * [24] Y. Huang, L. Zhang, Y. Wang, The matching extendability of 7-connected maximal 1-plane graphs, Discuss. Math. Graph Theory (2022).
  * [25] D. Hudák, T. Madaras, Y. Suzuki, On properties of maximal 1-planar graphs, Discuss. Math. Graph Theory 32 (2012), 737–747.
  * [26] S. G. Kobourov, G. Liotta, F. Montecchiani, An annotated bibliography on 1-planarity, Comput. Sci. Rev. 25 (2017), 49–67.
  * [27] V. P. Korzhik, B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory 72 (2013), 30–71.
  * [28] W. J. Lenhart, G. Liotta, F. Montecchiani, On partitioning the edges of 1-plane graphs, Theoret. Comput. Sci. 662 (2017), 59–65.
  * [29] N. Matsumoto, Y. Suzuki, Non-1-planarity of lexicographic products of graphs, Discuss. Math. Graph Theory 41 (4), 1103–1114.
  * [30] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965), 107–117.
  * [31] U. Schöning, Graph isomorphism is in the low hierarchy, J. Comput. System Sci. 37 (1988), 312–323.
  * [32] Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010), 1527–1540.
  * [33] Y. Suzuki, $K_{7}$-minors in optimal 1-planar graphs, Discrete Math. 340 (2017), 1227–1234.
  * [34] Y. Suzuki, 1-Planar Graphs, in: Beyond Planar Graphs, S.-H. Hong and T. Tokuyama (Ed(s)), Springer, (2020), 47–68.
  * [35] D. B. West, Introduction to Graph Theory (second edition), Prentice Hall, 2001\.
  * [36] J. Zhang, Y. Wu, H. Zhang, The maximum matching extendability and factor-criticality of 1-planar graphs, arXiv preprint, arXiv:2205.12122.
  * [37] X. Zhang, The edge chromatic number of outer-1-planar graphs, Discrete Math. 339 (2016), 1393–1399.


# The Effect Of The Phase-Space Noncommutativity On The Nonrelativistic Limit
Of The Dirac Equation

Ilyas HAOUAM1■ 1Department of physics, University of Constantine 1, Algeria
<EMAIL_ADDRESS>
###### Abstract

In this paper we are interested in the effect of the phase-space
noncommutativity on the nonreltivistic limit of the Dirac equation in
intereaction with an electromagnetic potential, the nonreltivistic limit is
done by the large and small wavefunction components approach, knowing that the
nonrelativistic limit gives the Schrödinger-pauli equation.

###### pacs:

03.65.Ge Solutions of wave equations: bound states – 03.65.Pm Relativistic
wave equations – 0 02.40.Gh Noncommutative geometry– 03.65.Fd Algebraic
methods

Keywords: Schrödinger-Pauli equation, Nonrelativistic limit, noncommutativity
of phase space, Dirac equation, Moyal product, Bopp-shift

##  1 Introduction

In the last years there has been much interstes in the study of physics in
non-commutative space, knowing that the study of noncommutative geometry has a
long history [1, 2], the studies of noncommutativity in phase-space and their
involvement for quantum field theories play an important role in various
fields of physics especially in the theory of strings, and in the matrix model
of M-theory [3], also in the description of quantum gravity (quantum gravity).

The common method for studying the noncommutativity of Quantum mechanics(NCQM)
is the correspondence between commutative space and the noncommutative space
using the method of translation which known as Bopp-shift, or using the Moyal
star product [4, 5, 6, 7].

In the quantum-mechanical description of particles, there are various
relativistic or non-relativistic wave equations as the usual Schrödinger
equation applies to the spin-0 particles in the non-relativistic domainin, and
the Klein–Gordon equation is the relativistic equation appropriate for spin-0
particles [8, 9, 10], in this paper we are interested in the spin-1/2
particles which are governed by the relativistic Dirac equation which, in the
non-relativistic limit, leads to the Schrödinger–Pauli equation [11, 12, 13] ,
but in the case of particles with spin 1 or higher, only relativistic
equations are usually considered [14].

##  2 Phase-Space Noncommutativity

It is well known that in the commutative space the coordinates $x_{i}$ and
momentum $p_{i}$ satisfy the usual canonical commutation relations:

$\left[x_{i},x_{j}\right]=0,\,\left[p_{i},p_{j}\right]=0,\,\left[x_{i},p_{j}\right]=i\delta_{ij}\qquad(i,j=1,2)$
(1)

In the recent study results on the phase-space noncommutativity(NCPS) show
that at very tiny scales(string scales) the space may not commute anymore, let
us consider the operators of coordinates and momentum in the noncommutative
phase-space $x_{i}^{(NC)}$and $p_{i}^{(NC)}$respectivly, then consider a
noncommutative algebra satisfying the commutation relations

$\left[x_{i}^{(NC)},x_{j}^{(NC)}\right]=i\theta_{ij},\,\left[p_{i}^{(NC)},p_{j}^{(NC)}\right]=i\eta_{ij},\,\left[x_{i}^{(NC)},p_{i}^{(NC)}\right]=i\hbar^{eff}\delta_{ij}\>(i,j=1,2)$
(2)

with the effective plank constant being

$\hbar^{eff}=\hbar(1+\frac{\theta\eta}{4\hbar^{2}})$ (3)

Where
$\theta_{ij}=\epsilon_{ijk}\theta_{k}\,,\>\theta_{k}=(0,0,\theta)\,,\,\eta_{ij}=\epsilon_{ijk}\eta_{k}\,,\>\eta_{k}=(0,0,\eta)$,
$\theta\,,\>\eta$ are noncommutative parameters and they are antisymmetric
constant matrices with dimension of $(lenght)^{2}$and $(momentum)^{2}$,
respectively.

So the NCPS parameters are related to the commutative space parameters (the
mapping between NCPS and CPS) through the linear transformations (Bopp-shift)
[15, 16]

$\begin{array}[]{cc}x^{(NC)}=x-\frac{1}{2\hbar}\theta
p_{y}&y^{(NC)}=y-\frac{1}{2\hbar}\theta p_{x}\\\
p_{x}^{(NC)}=p_{x}+\frac{1}{2\hbar}\eta
y&p_{y}^{(NC)}=p_{y}-\frac{1}{2\hbar}\eta x\end{array}$ (4)

When$\theta=\eta=0$ the noncommutative phase-sapce reduces to commutative
space.

The noncommutativity in space can be realized in terms of Moyal product( star
product) which means that the noncommutativity information is encoded in moyal
product, [17, 18, 19] in fact

$\begin{array}[]{c}(f\star
g)(x^{(NC)})=\exp[\frac{i}{2}\theta_{ab}\partial_{x_{a}}\partial_{x_{b}}]f\left(x_{a}\right)g\left(x_{b}\right)=f(x)g(x)\\\
+\sum_{n=1}\left(\frac{1}{n!}\right)\left(\frac{i}{2}\right)^{n}\theta^{a_{1}b_{1}}...\theta^{a_{n}b_{n}}\partial_{a_{1}}...\partial_{a_{k}}f(x)\partial_{b_{1}}...\partial_{b_{k}}g(x),\end{array}$
(5)

in other term we have

$\left(A,\star\right)\cong\left(\hat{A}^{(NC)},\cdot\right)$ (6)

##  3 Nonrelativistic limit of The Dirac equation

It is possible to define the Nonrelativistic limit of the Dirac equation,
using several wayes, including that, there is the FOLDY-WOUTHUYSEN [20,
21]transformation, and the classical opproach which is in the standard
representation the upper two components of the Dirac wavefunction $\psi$are
much larger than the lower two components [22] , using this property we can
derive the nonrelativistic limit in a simple way.

The Dirac Equation is given by:

$i\hbar\frac{\partial\psi}{\partial
t}=c\overrightarrow{\alpha}\hat{\overrightarrow{p}}\psi+\hat{\beta}mc^{2}\psi$
(7)

where the momentum $\overrightarrow{p}$ is given by
$\overrightarrow{p}=-i\hbar\overrightarrow{\nabla}$ and the matrices
$\overrightarrow{\alpha}$and $\beta$ satisfy the anticommutation relations

$\left\\{\alpha_{i},\alpha_{j}\right\\}=2\delta_{ij}\>,\;\left\\{\alpha_{i},\beta\right\\}=0\>,\;\alpha_{i}^{2}=\beta^{2}=1$
(8)

First we study the case of an electron at rest, in this case we obtain the
Dirac equation by setting $\hat{\overrightarrow{p}}\psi=0$ in Eq.(1)

$i\hbar\frac{\partial\psi}{\partial t}=\hat{\beta}m_{0}c^{2}\psi$ (9)

this system of equations is solved simply and leads to four solutions linearly
independentes:

$\begin{array}[]{cc}\psi^{(1)}=\left(\begin{array}[]{c}1\\\ 0\\\ 0\\\
0\end{array}\right)e^{-i(\frac{m_{0}c^{2}}{\hbar})t}&\psi^{(2)}=\left(\begin{array}[]{c}0\\\
1\\\ 0\\\ 0\end{array}\right)e^{-i(\frac{m_{0}c^{2}}{\hbar})t}\\\
\psi^{(3)}=\left(\begin{array}[]{c}0\\\ 0\\\ 1\\\
0\end{array}\right)e^{+i(\frac{m_{0}c^{2}}{\hbar})t}&\psi^{(4)}=\left(\begin{array}[]{c}0\\\
0\\\ 0\\\ 1\end{array}\right)e^{+i(\frac{m_{0}c^{2}}{\hbar})t}.\end{array}$
(10)

$\psi^{(1)}$and $\psi^{(2)}$correspond to positive energy value and
$\psi^{(3)}$, $\psi^{(4)}$with negative one.

At first therefore we restrict ourselves to solutions of positive energy. In
order to show that the Dirac equation reproduces the two component pauli
equation in the nonrelativisric limit, we inroduce the electromagnetic four-
potential

$A^{\mu}=\left\\{A_{0}(x),\overrightarrow{A}(x)\right\\}$ (11)

the Dirac equation Eq.(1) in the interaction with Eq.(11 ) knowing that the
minimal coupling

$\hat{p}^{\mu}\rightarrow\hat{p}^{\mu}-\frac{e}{c}A^{\mu}\equiv\hat{\Pi}^{\mu}$
(12)

where $\hat{\Pi}^{\mu}$ is the kinetic momentum and $\hat{p}^{\mu}$the
canonical momentum.

$i\hbar\frac{\partial}{\partial
t}\psi=c\overrightarrow{\alpha}(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})\psi+eA_{0}\psi+\hat{\beta}mc^{2}\psi.$
(13)

The nonrelativistic limit of Eq.(6) can be most efficiently studied in the
representation

$\psi=\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right).$ (14)

Where the four-component spinor $\psi$is decomposed into two two-component
spinors $\tilde{\varphi}$and $\tilde{\chi}$. Then the Dirac equation Eq.(6)
becomes

$i\hbar\frac{\partial}{\partial t}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)=c\overrightarrow{\alpha}\underset{\hat{\overrightarrow{\Pi}}}{\underbrace{(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})}}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)+\hat{\beta}mc^{2}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)$ (15)

according to

$\hat{\overrightarrow{\alpha}}=\left(\begin{array}[]{cc}0&\hat{\overrightarrow{\sigma}}\\\
\hat{\overrightarrow{\sigma}}&0\end{array}\right)\beta=\left(\begin{array}[]{cc}1&0\\\
0&-1\end{array}\right),$ (16)

into Eq.(15 ) then

$i\hbar\frac{\partial}{\partial t}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)=\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\tilde{\chi}\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\tilde{\varphi}\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)+mc^{2}\left(\begin{array}[]{c}\tilde{\varphi}\\\
-\tilde{\chi}\end{array}\right),$ (17)

if the rest energy $m_{0}c^{2},$as the largest occuring energy, is
additionally separated by

$\left(\begin{array}[]{c}\tilde{\varphi}\\\
\tilde{\chi}\end{array}\right)=\left(\begin{array}[]{c}\varphi\\\
\chi\end{array}\right)e^{-i(\frac{m_{0}c^{2}}{\hbar})t}$ (18)

then Eq.(17) takes the forme

$i\hbar\frac{\partial}{\partial t}\left(\begin{array}[]{c}\varphi\\\
\chi\end{array}\right)=\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\chi\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\varphi\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\varphi\\\
\chi\end{array}\right)-2m_{0}c^{2}\left(\begin{array}[]{c}0\\\
\chi\end{array}\right).$ (19)

Let us consider first the lower of the above equation. For the conditions
$\left|i\hbar\frac{\partial\chi}{\partial
t}\right|\ll\left|m_{0}c^{2}\chi\right|$and
$\left|eA_{0}\chi\right|\ll\left|m_{0}c^{2}\chi\right|$111$E_{0}\gg
i\hbar\frac{\partial}{\partial t}$, slow time dependence and $E_{0}\gg
eA_{0}$weak coupling of the electromagnetic potential if the kinetic energy as
well as the potential energy are small compared to the rest energy, we find
from the lower component of Eq.(19)

$\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\chi\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\varphi\end{array}\right)-2m_{0}c^{2}\left(\begin{array}[]{c}0\\\
\chi\end{array}\right)=0$ (20)

Eq.(20) leads to

$\chi=\frac{c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}}{2mc^{2}}\varphi.$
(21)

This means that $\chi$represents the small components of the wave
function$\psi$and $\varphi$represents the large components. Insertion of
Eq.(21) into the Eq.(19) results in a nonrelativistic wave function for
$\varphi$

$i\hbar\frac{\partial}{\partial
t}\varphi=\frac{(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})}{2m_{0}}\varphi+eA_{0}\varphi.$
(22)

With the help
of$(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{A}})(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{B}})=\hat{\overrightarrow{A}}.\hat{\overrightarrow{B}}+i\hat{\overrightarrow{\sigma}}.(\hat{\overrightarrow{A}}\times\hat{\overrightarrow{B}})$,
(see Appendix for the proof) we continue the calculation

$(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})=\hat{\overrightarrow{\Pi}}^{2}+i\hat{\overrightarrow{\sigma}}.(\hat{\overrightarrow{\Pi}}\times\hat{\overrightarrow{\Pi}})$
$=(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})^{2}+i\hat{\overrightarrow{\sigma}}\left[(-i\hbar\overrightarrow{\nabla}-\frac{e}{c}\overrightarrow{A})\times(-i\hbar\overrightarrow{\nabla}-\frac{e}{c}\overrightarrow{A})\right]$
$=(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})^{2}-\frac{e}{c}\hbar\hat{\overrightarrow{\sigma}}.(\overrightarrow{\nabla}\times\overrightarrow{A})$
$=(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})^{2}-\frac{e}{c}\hbar\hat{\overrightarrow{\sigma}}.\overrightarrow{B}$
(23)

Finallay Eq.(22) becomes

$i\hbar\frac{\partial}{\partial
t}\varphi=\frac{(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})^{2}}{2m_{0}}\varphi-\frac{e\hbar\hat{\overrightarrow{\sigma}}.\overrightarrow{B}}{2m_{0}c}\varphi+eA_{0}\varphi.$
(24)

This is as it should be, The Schrödinger-Pauli equation[22, 23]

###  3.1 Gyromagnetic Factor of The Electron(g=2)

According to
$\overrightarrow{B}=\overrightarrow{\nabla}\times\overrightarrow{A}$,
$\overrightarrow{A}=\frac{1}{2}\overrightarrow{B}\times\overrightarrow{x}$

$(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})^{2}=(\hat{\overrightarrow{p}}-\frac{e}{2c}\overrightarrow{B}\times\overrightarrow{x})^{2}\approx\hat{\overrightarrow{p}}^{2}-\frac{e}{c}\overrightarrow{B}.\overrightarrow{L},$
(25)

where$\overrightarrow{L}=\overrightarrow{x}\times\hat{\overrightarrow{p}}$ and
$\hat{\overrightarrow{S}}=\frac{1}{2}\hbar\hat{\overrightarrow{\sigma}}$are
the operator of orbital angular momentum and the spin operator respectively.

So that Eq.(23) finally takes the form of

$i\hbar\frac{\partial}{\partial
t}\varphi=\left[\frac{\hat{\overrightarrow{p}}^{2}}{2m_{0}}-\frac{e}{2m_{0}c}(\overrightarrow{L}+2\hat{\overrightarrow{S}}).\overrightarrow{B}+eA_{0}\right]\varphi$
(26)

This form of Schrödinger-Pauli equation shows explicitly the g facor 2.

The most important result is that in the nonrelativistic limit, the Dirac
equation transforms into the Schrödinger-Pauli equation

##  4 Nonrelativistic limit of The Noncommutative Dirac equation

The Dirac equation in the Noncommutative phase-space is given by [18, 24]

$H(x^{(NC)},p^{(NC)})\star\psi(x^{(NC)})=E\psi.$ (27)

knowing that the Dirac equation in interaction with electromagnetic potential
in commutative space-phase is

$E\psi=\left[c\alpha_{i}(\hat{p_{i}}-\frac{e}{c}A_{i}(x))+eA_{0}(x)+\hat{\beta}mc^{2}\right]\psi,$
(28)

so in the first step we make the mapping between the coordinates $x^{(NC)}$and
$x$ using the moyal product, with the help of Eq.(5), the Dirac equation
Eq.(27) becomes

$H(x^{(NC)},p^{(NC)})\star\psi(x^{(NC)})=\left[c\alpha_{i}(\hat{p_{i}}-\frac{e}{c}A_{i}(x))+eA_{0}(x)+\hat{\beta}mc^{2}\right]\star\psi(x),$
(29)

assuming that the electromagnetic potential is written as $A(x)=hx$ so that
the derivation in the Eq.(5) will automatically stop in the first ordre, then
we find

$(f\star
g)(x^{(NC)})=f(x)g(x)+\frac{i}{2}\theta^{ab}\partial_{a}f\partial_{b}g+\mathcal{O}(\theta^{2}).$
(30)

then Eq.(29) can be written as follows

$\begin{array}[]{c}H(x^{(NC)},p^{(NC)})\star\psi(x^{(NC)})=H(x,p^{(NC)})\psi(x)\\\
+\frac{i}{2}\theta_{ab}\partial_{a}\left(c\alpha_{i}(\hat{p_{i}}-\frac{e}{c}A_{i}(x))+eA_{0}(x)+\hat{\beta}mc^{2}\right)\partial_{b}\psi(x)=E\psi(x).\end{array}$
(31)

where $\partial_{a}(c\alpha_{i}\hat{p_{i}})=\partial_{a}(\hat{\beta}mc^{2})=0$
Eq.(28) becomes

$H(x,p^{(NC)})\psi(x)-\frac{ie}{2}\theta_{ab}\partial_{a}\left(\alpha_{i}A_{i}(x))+A_{0}(x)\right)\partial_{b}\psi(x)=E\psi(x).$
(32)

in the second step we make the mapping between the momentum $p^{(NC)}$and $p$
using Eq.(4) to get full Dirac equation in noncommutative phase-space.

$\begin{array}[]{c}H_{(NC\text{)}}(x,p)\psi(x)=\left[c\alpha_{i}\left(p_{i}+\frac{1}{2\hbar}\eta_{ij}x_{j}-\frac{e}{c}A_{i}(x)\right)+eA_{0}(x)\right.\\\
\left.+\hat{\beta}mc^{2}-\frac{ie}{2}\theta_{ab}\partial_{a}\left(\alpha_{i}A_{i}(x)+A_{0}(x)\right)\partial_{b}\right]\psi(x)=E\psi(x),\end{array}$
(33)

we rewrite Eq.(33) in a more compact form (see Appendix for the proof):

$\begin{array}[]{c}H_{(NC\text{)}}\psi_{(NC)}=\left[c\overrightarrow{\alpha}\left(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A}\right)+eA_{0}+\hat{\beta}mc^{2}\right.\\\
\left.+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta}+\frac{e}{\hbar}\left(\overrightarrow{\nabla}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\times\overrightarrow{p}\right).\overrightarrow{\theta}\right]\psi_{(NC)}=E\psi_{(NC)}.\end{array}$
(34)

To define a Nonrelativistic limit of the Dirac equation in NCPS, we have
firstly to study the case of an electron at rest and without electromagnetic
interaction, so by setting $\hat{\overrightarrow{p}}\psi=0$, $A^{\mu}=0$ at
Eq.(34)

$H_{(NC\text{)}}\psi_{(NC)}=\left[\hat{\beta}m_{0}c^{2}+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta}\right]\psi_{(NC)}=i\hbar\frac{\partial\psi_{(NC)}}{\partial
t}.$ (35)

this system of equations is simply solved as in Eq.(9) and leads to the
following four-solutions

$\begin{array}[]{cc}\psi_{(NC)}^{(1)}=\left(\begin{array}[]{c}1\\\ 0\\\ 0\\\
0\end{array}\right)e^{-\frac{i}{\hbar}(m_{0}c^{2}+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta})t}&\psi_{(NC)}^{(2)}=\left(\begin{array}[]{c}0\\\
1\\\ 0\\\
0\end{array}\right)e^{-\frac{i}{\hbar}(m_{0}c^{2}+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta})t}\\\
\psi_{(NC)}^{(3)}=\left(\begin{array}[]{c}0\\\ 0\\\ 1\\\
0\end{array}\right)e^{+\frac{i}{\hbar}(m_{0}c^{2}+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta})t}&\psi_{(NC)}^{(4)}=\left(\begin{array}[]{c}0\\\
0\\\ 0\\\
1\end{array}\right)e^{+\frac{i}{\hbar}(m_{0}c^{2}+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta})t}\end{array}$
(36)

with the same steps used in the nonrelativistic limiting in the case of
commutative space, where
$\psi_{(NC)}=\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)$, then the Dirac equation Eq.(34)
becomes

$\begin{array}[]{c}i\hbar\frac{\partial}{\partial
t}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)=c\overrightarrow{\alpha}\underset{\hat{\overrightarrow{\Pi}}}{\underbrace{(\hat{\overrightarrow{p}}-\frac{e}{c}\overrightarrow{A})}}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)+\hat{\beta}m_{0}c^{2}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)\\\
+\frac{c}{\hbar}(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)+\frac{e}{\hbar}\left(\overrightarrow{\nabla}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\times\overrightarrow{p}\right).\overrightarrow{\theta}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right),\end{array}$ (37)

using Eq.(16), and setting
$\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\eta}}=(\overrightarrow{\alpha}\times\overrightarrow{x}).\overrightarrow{\eta}\,and\,\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}=\left(\overrightarrow{\nabla}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\times\overrightarrow{p}\right).\overrightarrow{\theta}\>$it
comes

$\begin{array}[]{c}i\hbar\frac{\partial}{\partial
t}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)=\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\tilde{\chi}_{(NC)}\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\tilde{\varphi}_{(NC)}\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)+m_{0}c^{2}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
-\tilde{\chi}_{(NC)}\end{array}\right)\\\
+\frac{c}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\eta}}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)+\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right),\end{array}$ (38)

with $\left(\begin{array}[]{c}\tilde{\varphi}_{(NC)}\\\
\tilde{\chi}_{(NC)}\end{array}\right)=\left(\begin{array}[]{c}\varphi_{(NC)}\\\
\chi_{(NC)}\end{array}\right)e^{-\frac{i}{\hbar}(m_{0}c^{2}+\frac{c}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\eta}})t}\>$
then Eq.(38) takes the forme

$i\hbar\frac{\partial}{\partial t}\left(\begin{array}[]{c}\varphi_{(NC)}\\\
\chi_{(NC)}\end{array}\right)=\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\chi_{(NC)}\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\varphi_{(NC)}\end{array}\right)+eA_{0}\left(\begin{array}[]{c}\varphi_{(NC)}\\\
\chi_{(NC)}\end{array}\right)-2m_{0}c^{2}\left(\begin{array}[]{c}0\\\
\chi_{(NC)}\end{array}\right)+\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\left(\begin{array}[]{c}\varphi_{(NC)}\\\
\chi_{(NC)}\end{array}\right).$ (39)

using the slow time dependence $E_{0}\gg i\hbar\frac{\partial}{\partial t}$,
and weak coupling of the electromagnetic potential $E_{0}\gg eA_{0}$ approach,
Eq.(39) goes to

$\left(\begin{array}[]{c}c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\chi_{(NC)}\\\
c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}\varphi_{(NC)}\end{array}\right)-2m_{0}c^{2}\left(\begin{array}[]{c}0\\\
\chi_{(NC)}\end{array}\right)+\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\left(\begin{array}[]{c}\varphi_{(NC)}\\\
\chi_{(NC)}\end{array}\right)=0.$ (40)

Let us use the second equation of the above system Eq.(40) then we obtain

$\chi_{(NC)}=\frac{c\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}}}{\left(2m_{0}c^{2}-\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right)}\varphi_{(NC)}$
(41)

where $\chi_{(NC)}$ represent the small components of the wave function
$\psi_{(NC)}$ . Insertion of Eq.(42) into the first equation of Eq.(39)
results in a nonrelativistic wave function for $\varphi_{(NC)}$

$i\hbar\frac{\partial}{\partial
t}\varphi_{(NC)}=\frac{(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})(\hat{\overrightarrow{\sigma}}\hat{\overrightarrow{\Pi}})}{\left(2m_{0}-\frac{e}{\hbar
c^{2}}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right)}\varphi_{(NC)}+eA_{0}\varphi_{(NC)}+\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\varphi_{(NC)}.$
(42)

using Eq.(23) and Eq.(25) we find

$i\hbar\frac{\partial}{\partial
t}\varphi_{(NC)}=\left[\frac{\hat{\overrightarrow{p}}^{2}}{\left(2m_{0}-\frac{e}{\hbar
c^{2}}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right)}-\frac{e}{c\left(2m_{0}-\frac{e}{\hbar
c^{2}}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right)}(\overrightarrow{L}+2\hat{\overrightarrow{S}}).\overrightarrow{B}+eA_{0}+\frac{e}{\hbar}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right]\varphi_{(NC)}.$
(43)

Where$\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}=\left(\overrightarrow{\nabla}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\times\overrightarrow{p}\right).\overrightarrow{\theta}$

for $\theta=0$$\Rightarrow\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}=0$
and Eq.(43) becomes Eq.(26)

while we are in very tiny sapce scales, so the Nc
term$\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\ll 1$ , it is possible
to use the Maclaurin series, by changing the variable

$\frac{e}{2m_{0}\hbar
c^{2}}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}=\mathbf{\mathbf{\Theta_{\theta}}}$
(44) $\frac{1}{2m_{0}\left(1-\frac{e}{2m_{0}\hbar
c^{2}}\boldsymbol{\boldsymbol{\boldsymbol{Q}}_{\theta}}\right)}\backsimeq\frac{1}{2m_{0}}\overset{n}{\underset{j=0}{\sum}}\Theta_{\theta}^{j},$
(45)

we find that Eq.(43) goes to

$i\hbar\frac{\partial}{\partial
t}\varphi_{(NC)}=\left[\frac{\hat{\overrightarrow{p}}^{2}}{2m_{0}}\overset{n}{\underset{j=0}{\sum}}\Theta_{\theta}^{j}-\frac{e}{2m_{0}c}\overset{n}{\underset{j=0}{\sum}}\Theta_{\theta}^{j}.(\overrightarrow{L}+2\hat{\overrightarrow{S}}).\overrightarrow{B}+eA_{0}+2m_{0}c\Theta_{\theta}\right]\varphi_{(NC)}.$
(46)

Eq.(46) represents The Schrödinger-Pauli equation in the Noncommutative space,

##  5 Conclusion

In conclusion, the nonrelativistic limit of the Dirac equation with
electromagnetic potential has been studied in non-commutative phase-space.
Using the large and small wavefunction components approach. we find that the
effect of the noncommutativity in phase on the nonrelativistic limit is
vanished, but the effect of the noncommutativity in space appear widely and it
is reduced in the $\Theta_{\theta}$. Under the condition that space-space and
momentum-momentum are all commutative (namely, η= 0, ϑ= 0) the results return
to that of usual quantum mechanic.

The author would like to thank Pr Lyazid CHETOUANI for interesting comments
and suggestions.

## Appendix A.

the proof of the formula used in Eq.(23)

$(\sigma_{i}\Pi^{i})(\sigma_{j}\Pi^{j})f=\sigma_{i}\sigma_{j}\Pi^{i}\Pi^{j}f$

$=\left(\delta_{ij}+i\epsilon_{ijk}\sigma_{k}\right)\Pi^{i}\Pi^{j}f$

$=\overrightarrow{\Pi}^{2}f+i\epsilon_{ijk}\sigma_{k}\left(\partial_{i}-eA_{i}\right)\left(\partial_{j}-eA_{j}\right)f$

$=\overrightarrow{\Pi}^{2}f+i\epsilon_{ijk}\sigma_{k}\left(\partial_{i}\partial_{j}f-e^{2}A_{i}A_{j}-ie\partial_{i}\left(A_{j}f\right)-ieA_{i}\partial_{j}f\right)$

$=\overrightarrow{\Pi}^{2}f-e\overrightarrow{\sigma}\left(\overrightarrow{\nabla}\times\overrightarrow{A}\right)f=\overrightarrow{\Pi}^{2}f-e\overrightarrow{\sigma}.\overrightarrow{B}f$

calculations between moving from the relation Eq.(33) to the relation Eq.(34)

using $\eta_{ij}=\eta\epsilon_{ij}$ and
$\eta_{k}=\frac{1}{2}\epsilon_{kij}\eta_{ij}$

$c\alpha_{i}\frac{1}{2\hbar}\eta_{ij}x_{j}=c2\frac{1}{2\hbar}\eta_{k}\epsilon_{kij}^{-1}\alpha_{i}x_{j}=c\frac{1}{\hbar}\eta_{k}\epsilon_{kij}\alpha_{i}x_{j}$
/ $\epsilon_{kij}=\epsilon_{ijk}$

we know that $\left(u\times
v\right)_{\mu}=\epsilon_{\mu\nu\lambda}u_{\nu}.v_{\lambda}$so

$c\frac{1}{\hbar}\eta_{k}\epsilon_{kij}\alpha_{i}x_{j}=\frac{c}{\hbar}\left(\overrightarrow{\alpha}\times\overrightarrow{x}\right)_{k}.\eta_{k}=\frac{c}{\hbar}\left(\overrightarrow{\alpha}\times\overrightarrow{x}\right).\overrightarrow{\eta}$

with the same manner we prove that

$-ie\theta_{k}\epsilon_{abk}\partial_{a}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\partial_{b}=-ie\frac{\hbar}{\hbar}\theta_{k}\epsilon_{abk}\partial_{a}\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)=\frac{e}{\hbar}\left(\overrightarrow{\nabla}.\left(\overrightarrow{\alpha}\overrightarrow{A}-A_{0}\right)\times\overrightarrow{p}\right)\times\overrightarrow{\theta}$

## References

  * [1] H.S. Snyder, Phys. Rev. 71, 38 (1946)
  * [2] C.N. Yang, Phys. Rev. 72, 874 (1947).
  * [3] T. Banks, W. Fischler, S. Shenker and L. Susskind, Phys. Rev. D55 (1997) 5112
  * [4] M. R. Douglas and N. A. Nekrasov, Rev. Mod. Phys. 73(2001)977-1029.
  * [5] A. Connes, M. R. Douglas and A.Schwarz, JHEP 9802 (1998) 003.
  * [6] N. Seiberg and E. Witten, JHEP 9909 (1999) 032.
  * [7] M. Chaichian, A. Demichev, P. Presnajder, Nucl. Phys. B567 360 (2000).
  * [8] Duffin, R.J.: Phys. Rev.54, 1114 (1938)
  * [9] Kemmer, N.: Proc. R. Soc. A166, 127 (1938)
  * [10] Kemmer, N.: Proc. R. Soc. A173, 91 (1939)
  * [11] J.D. Bjorken and S.D. Drell, Relativistic Quantum Mechanics (McGraw-Hill, New York, 1964).
  * [12] A.S. Davydov, Quantum Mechanics, 2nd ed., (Pergamon, Ox-ford, 1965)§63.
  * [13] A. Messiah, Quantum Mechanics, Vol. II, (Wiley, New York, 1968). 4. V.B.
  * [14] V.B. Berestetskii, E.M. Lifshitz, and L.P. Pitaevskii, Quantum Electrodynamics, 2nd ed., (Pergamon, Oxford, 1989).
  * [15] X. Jiang, C. Long and S. Qin, Rev. Mod. Phys, (2013)4.940-944.
  * [16] H. Hassanabadi, Z. Molaee and S.Zarrinkamar, Advances in High Energy Phys, vol. 2014, Article ID 459345, 6 pages, 2014.
  * [17] B.Mirza, M.Mohadesi, Theor. Phys. Vol. 42, No. 5 (2014)664-668.
  * [18] W. Jiang Hua, L. Kang, Chin. Phys. Lett, Vol. 24, No. 1 (2007)5.
  * [19] V.G. Kupriyanov, J.Phys. A46 (2013) 245303.
  * [20] Foldy L L and Wouthuysen S 1950Phys. Rev.5829
  * [21] A G Nikitin, J. Phys. A: Math. Gen.31(1998) 3297–3300
  * [22] W. Greiner, Quantum Mechanics, 3rd ed,(Springer, Berlin, Heidelberg, 1994)
  * [23] G.F. Torres del Castillo, J. Velazquez Castro, Rev. Mex. Fis. 50(3) (2004) 306–310
  * [24] O. Bertolamia, R. Queirozb, Phys. Lett. A Vol. 375, 7 (2011) 4116–4119