Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Minimal obstructions for 1-immersions and hardness of 1-planarity
  testing   A graph is 1-planar if it can be drawn on the plane so that each edge is
crossed by no more than one other edge (and any pair of crossing edges cross
only once). A non-1-planar graph $G$ is minimal if the graph $G-e$ is 1-planar
for every edge $e$ of $G$. We construct two infinite families of minimal
non-1-planar graphs and show that for every integer $n > 62$, there are at
least $2^{(n-54)/4}$ nonisomorphic minimal non-1-planar graphs of order $n$. It
is also proved that testing 1-planarity is NP-complete.

35
The categories of this paper are: mtrl-th
12
The categories of this paper are: nucl-th
10
The categories of this paper are: q-bio
1
The categories of this paper are: cs
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
16
The categories of this paper are: stat
20
The categories of this paper are: acc-phys
7
The categories of this paper are: hep-th
15
The categories of this paper are: nucl-ex
23
The categories of this paper are: solv-int
21
The categories of this paper are: adap-org
34
The categories of this paper are: chem-ph
11
The categories of this paper are: hep-lat
32
The categories of this paper are: atom-ph