IMFM
Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia
Preprint series Vol. 50 (2012), 1172
ISSN 2232-2094
ADDING ONE EDGE TO PLANAR GRAPHS MAKES CROSSING NUMBER AND 1-PLANARITY HARD
Sergio Cabello Bojan Mohar
Ljubljana, March 30, 2012
Adding one edge to planar graphs makes crossing number
and 1-planarity hard*
00
Sergio Cabello^	Bojan Mohar*§
Department of Mathematics	Department of Mathematics
FMF, University of Ljubljana	Simon Fraser University
Slovenia	Burnaby, B.C. V5A 1S6
email: sergio.cabello@fmf.uni-lj.si	email: mohar@sfu.ca

March 27, 2012
IN
Abstract
o
A graph is near-planar if it can be obtained from a planar graph by adding an edge. We show the surprising fact that it is NP-hard to compute the crossing number of near-planar graphs. A graph is 1-planar if it has a drawing where every edge is crossed by at most one other edge. We show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The main idea in both reductions is to consider the problem of simultaneously drawing two planar graphs inside a disk, with some of its vertices fixed at the boundary of the disk. This leads to the concept of anchored embedding, which is of independent interest. As an interesting consequence we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. This resolves a question of Hlineny.
CM
1 Introduction
O
CM
i
CO CO
A drawing of a graph G in the plane is a representation of G where vertices are represented by distinct points of R2, edges are represented by simple polygonal arcs in R2 joining points that correspond to their endvertices, and the interior of every arc representing an edge contains no points representing the vertices of G. A crossing of a drawing D is a pair ({e, e'},p), where e and e' are distinct edges and p e R2 is a point that belongs to the interiors of both arcs representing e and e' in the drawing D. The number of crossings of a drawing D is denoted by cr(D) and is called the crossing number of the drawing. The crossing number cr(G) of a graph G is the minimum cr(D) taken over all drawings D of G. A planar graph is a graph whose crossing number is 0. A drawing D with cr(D) = 0 is called an embedding of G (in the plane). A drawing D is a 1-drawing if each edge participates in at most 1 crossing. A 1-planar graph is a graph that has some 1-drawing.
A graph is near-planar if it can be obtained from a planar graph G by adding an extra edge xy between vertices x and y of G. We denote such near-planar graph by G + xy. (The
CO CD
■ i-H J-H
CD
*A preliminary version of this work was presented at the 26th Annual Symposium on Computational Geometry [2].
^Supported in part by the Slovenian Research Agency, program P1-0297, projects J1-7218 and J1-4106, and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation.
^Supported in part by the ARRS, Research Program P1-0297, by an NSERC Discovery Grant, and by the Canada Research Chair Program.
§On leave from IMFM & FMF, Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia.
term almost planar has also been used for the same concept [13, 17].) Near-planarity is a very weak relaxation of planarity, and hence it is natural to study properties of near-planar graphs. Graphs embeddable in the torus and apex graphs are superfamilies of near-planar graphs.
We show that it is NP-hard to compute the crossing number of near-planar graphs. We also show that it is NP-hard to decide whether a given near-planar graph is 1-planar, even when the graph has bounded degree. These results are not only surprising but also fundamental. They provide evidence that computing crossing numbers is an extremely challenging task, even for the simplest families of non-planar graphs.
In the course of developing our NP-hardness reductions, we introduce a new notion of anchored drawings and anchored embeddings, whose study is of independent interest. We also prove various related hardness results for rectilinear crossing number, anchored crossing number, and crossing number with rotations.
We show that these problems are NP-hard using a reduction from satisfiability (SAT). Our reductions are based on considering drawings of two planar graphs inside a disk with some of its vertices at prescribed positions of the boundary. The reductions are inspired by the work of Werner [21], although the details in our proofs are essentially different. We can then use a technique from [17] to relate these drawings to drawings of near-planar graphs.
Our approach is geometric, and in particular we obtain a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. Hardness of the crossing number problem for cubic graphs was established by Hlineny [11], who asked if one can prove this result by a reduction from an NP-complete geometric problem instead of the Linear Arrangement problem used in his proof.
cm
r
o
00
Related work. It has been known for quite some time that it is NP-hard to compute crossing numbers of graphs. Previous proofs involved reductions from the problem Linear Arrangement [8, 11, 18]. The spirit of our reduction is completely different from previous proofs and 00 hence of interest in its own right. In particular, we provide an alternative proof that computing crossing numbers is NP-hard (even when restricted to cubic graphs). Our NP-hardness proof is more complicated, but it provides the additional bonus of having control over the structure of the graph and henceforth working for near-planar graphs.
The study of crossing numbers for near-planar graphs was initiated by Riskin [20], who showed that if G is a planar 3-connected cubic graph, then the crossing number of G + xy is equal to the length of a shortest path in the geometric dual graph of the planar subgraph G — x — y. A consequence of his result it that the crossing number of a 3-connected cubic near-planar graph can be computed in polynomial time. Riskin asked if a similar result holds in more general situations. This was disproved by Mohar [17] and Gutwenger, Mutzel, and Weiskircher [10]. In fact, the result cannot be extended even assuming 5-connectivity.
For near-planar graphs of maximum degree A, Hlineny and Salazar [13] provided a Aapproximation algorithm for the crossing number. Later, we [3] improved the approximation factor of this algorithm to [A/2J using combinatorial bounds that relate the crossing number of G + xy to the number of vertex-disjoint and edge-disjoint cycles in G that separate x and y. This separation has to be defined in a certain strong sense over all planar embeddings of G. Approximation algorithms for the crossing number have been provided for some superfamilies of near-planar graphs [4, 5, 12]. However, it should be noted that it was not known if computing the crossing number in any of those families is NP-hard. Combinatorial bounds have also been studied in [1, 7].
a	Our previous paper [3] contained a closely related result: namely, we showed that computing
the crossing number of near-planar graphs is NP-hard for weighted graphs. Unfortunately, our reduction was from Partition, and hence required weights that are not polynomially bounded in the size of the graph. Moreover, the planarizing edge xy needed large weight, so G + xy could
m
CD Jh
CM
r
o
00
not be transformed into an unweighted near-planar graph. See the discussion below. In this paper we use completely different techniques.
Kawarabayashi and Reed [14], improving upon a result of Grohe [9], have shown that for each constant k0 there is a linear-time algorithm that decides if the crossing number of an input graph is at most k0. Hence, it is clear that in our reduction the crossing number has to be an increasing function in the number of vertices. The currently best approximation to the crossing number of general graphs is by Chuzhoy [6].
The concept of 1-planar graphs was introduced by Ringel [19]. The concept of 1-planarity is more subtle and because of this, the results are scarcer. There is a lack of fundamental basic tools needed to tackle problems about 1-planarity. Some of them are provided by Korzhik and Mohar in [16] (preliminary version in [15]), where they studied minimal non-1-planar graphs and, in particular, showed that recognizing 1-planar graphs is NP-complete. Our proof that recognizing 1-planar graphs is hard even for near-planar graphs is completely different from their proof and is also much more transparent.
IN
Weighted vs. unweighted edges. Our discussion for crossing numbers will be simplified by using weighted edges. When each edge e of G has a weight we e N, the crossing number of a drawing D is defined as ^ we ■ we/, the sum taken over all crossings ({e, e'},p) in D. The crossing number of G is then defined again as the minimum cr(D) taken over all drawings D of G.
Let G be a weighted graph. Consider the unweighted graph HG with V(HG) = V(G), in which there are wuv subdivided "parallel" edges between u and v in HG, for each edge uv e E(G). It is easy to see that cr(HG) = cr(G). If the weights of G are polynomially bounded in |V(G)|, then HG can be constructed in polynomial time. Hence, in our reduction it will be enough to describe a weighted planar graph G whose weights are polynomially bounded, and then describe which extra edge xy we add. The resulting unweighted near-planar graph is 00 Hg + xy. The additional edge xy that we add must have unit weight, as otherwise the resulting graph HG+xy would not be near-planar.
Anchored graphs. The main idea in our proof is considering a concept of anchored graphs, and studying the crossing number and 1-planarity of such objects. Although this seems to be a fundamental notion, we are not aware of any previous work considering anchored graphs.
An anchored graph is a triple (G, AG,nG), where G is a graph, AG is a subset of vertices of G, and nG is a cyclic ordering of AG. For reasons that will become evident soon, we call the vertices AG anchors. With a slight abuse of notation, we will sometimes use G to denote an anchored graph when the anchor set Ag and the ordering ig are implicit.
Let Q C R2 be a topological disk whose boundary is a closed polygonal line. An anchored drawing of an anchored graph (G, Ag,^g) is a drawing of G in Q such that the vertices of Ag are represented by points on the boundary of the disk Q, and the cyclic ordering of the anchors AG along the boundary of Q is nG. An anchored drawing without crossings is an anchored embedding. An anchored planar graph is an anchored graph that has an anchored embedding. The anchored crossing number acr(G, Ag, ig), or simply acr(G), of an anchored graph G is the minimum number of crossings over all anchored drawings of G. An anchored 1-drawing is an anchored drawing where each edge participates in at most one crossing. An anchored 1-planar graph is an anchored graph that has an anchored 1-drawing.
Let (G, Ag, ^g) be an anchored graph. Any subgraph H of G naturally defines the anchored a subgraph (H, AH, ), where AH = AG n V(H) and is the restriction of nG to the vertices in Ah. We say that an anchored graph (G, Ag,^g) can be decomposed into two anchored
o
CM
i
CD U
graphs if there are two anchored subgraphs (R, AR, nR) and (B, AB, ) such that R U B = G
and E(R) n E(B) = 0. The decomposition is vertex-disjoint when V(R) n V(B) = 0. For helping with the exposition we will refer to R as "red" graph and to B as "blue" graph. We will use the notation [m] = {0,1,..., m}.
o
cm
2 Crossing number
CD
In this section we consider the crossing number of anchored graphs and near-planar graphs. In Section 2.1 we show that computing the crossing number of anchored graphs is NP-hard. In Section 2.2 we show that computing the crossing number of near-planar graphs is NP-hard. In Section 2.3 we provide some extensions implied by our construction.
2.1 Crossing number of anchored graphs
o
cm
The problem of minimizing the number of crossings in drawings of anchored graphs is of independent interest. In this section we show that computing the crossing number of anchored graphs is hard even in a very special case when the anchored graph is decomposed into two vertex-disjoint planar anchored subgraphs.
Theorem 2.1. Computing the anchored crossing number of anchored graphs is NP-hard, even if the input graph is decomposed into two vertex-disjoint planar anchored subgraphs (and the decomposition is part of the input).
The rest of this section is devoted the proof of Theorem 2.1. The reduction will be from the decision problem of satisfiability:
SAT.
Input: A set of n variables x1;..., xn and a set of m disjunctive clauses Ci,..., Cm.
Output: Can we assign boolean values T/F to the variables such that the formula
C1 A ■ ■ ■ A Cm is satisfied?
cm
£ CO CO
Consider an instance I to SAT. Henceforth, we will use n to denote the number of variables and use m to denote the number of clauses. Let w = 30nm. It is convenient to think of w as a sufficiently large weight to make the reduction work. Let k = (6nm + 6n + 2m + 1)w3 — m(w2 + w — 1). The upper bound
k < (6nm + 6n + 2m + 1)w3 < 15nmw3 < (w2 — 1)2 will be useful in our discussion.
Overview. We next provide an overview of our reduction. Our aim at this point is to provide intuition. An example showing how the whole reduction works is given in Figure 1. It may help getting the global picture through the discussion. We will describe an anchored blue planar graph B = B(I) and an anchored red planar graph R = R(I). The graphs B and R will be vertex-disjoint. We will then construct an anchored graph G = G(I) that has a decomposition into R and B; the graph G is determined by R, B and by specifying the circular ordering of the anchors AB U AR. The weights of the edges are controlled by a parameter w = w(n, m). It will turn out from the construction that, for a certain value k = k(n, m), the anchored crossing number of G is at least k, and that it is equal to k if and only if the instance I can be satisfied.
The blue graph B has a grid-like structure. In an optimal drawing there are no blue-blue crossings. The weights of the blue edges are used to encode the clauses of the instance I. The cu red graph has the following structure. For each variable xi, there is a pair of 'vertical paths' in the red graph; they connect anchor r(xi) to anchor r'(xi) in Figure 1. The construction will
r'(xi)
r'(x2)
r'(xs)
r'(x4)
i-H
o o
CO
¿2 o u
IN
0 o
1
CO ^
CO CO
CO CD
$H
CD CO
$H
a
CD U
>
1—1
r
>
r(0,5)
r(0,4)
r(0,3)
r
>
r
>
CO
r
>
i-H
r
r(0,2)
r(0,1)
	// +1	r , +1	+2	f , +1	+0 ,	+2	\ + 1 ,	+1	
1 ■ 1		i----^		i 1----	i ----L		|----L		I I r 1 i i
1 1 1	/ - f- / Hi	i----^	II---1	i 1----	1 ----L 1	II---1 h	hi	■I—i	i i i--------1 i i
1 ■ 1				• i i	1 1		T ^		i i i i i i
1 1 1		j !	/ - -/ - / il	i 1---- 4---- i i	1 ----L ----4 1 1	II---II-	bj	II---1 h	i i i--------1 i i
1 1	HI---1	i—^							i i i i i i
1 1 1				i i i	1 1 1 ----L	II---1 h	bj	/ -f - / if	i i r 1 i i
1 1	HI---1	i—^	II---1	1----					i i i i i i
1 1 1			---	i i i -*---- ■	1 1 1 ----4 l		! !		i i
						J1" / -/ - /		- -	r 1 i i
1		"* "T							i i i i i i
J 1 1				i	1				
		I	\	I	I	1/	i		
r(2n+1,5)
r(2n+1,4)
r(2n+1,3)
r(2n+1,2)
r(2n+1,1)
r(x1)	r(x2)	r(x3)	r(x4)
x1
X2
X3
x4
Figure 1: Example of the resulting reduction for the formula on 4 variables x1;x2,x3, x4 and clauses -x1 V-x3 Vx4, -x2 V-x4, x2 V-x3, xi Vx2. The optimal drawing in the figure corresponds to the boolean assignment x1 = x2 = T and x3 = x4 = F. The thickest (red or blue) edges have weight w4; the (blue) edges of middle thickness without annotation have weight w2 if solid and w2 — 1 if dashed; each solid (blue) edge of middle thickness with annotation +t has weight w2 +1; the thinnest (red) edges have weight w if solid and w — 1 if dashed.
enforce that in an optimal drawing such a pair will be drawn either to the left or to the right of the middle line, that is, in the lighter shaded or the darker shaded region shown in the left part of Figure 3. Each such option corresponds to an assignment of the variable x» as T or F. For each clause Cj, there is a 'horizontal path'; it connects anchor r(0j) to anchor r(2n+1j-) in Figure 1. Such path must cross a 'horizontal line' of the blue grid once. The number of crossings with such horizontal path depends on where it crosses the 'blue line', and tells if the clause is satisfied with the assignment of the variables or not.
Formal proof. We next proceed with the formal proof. The blue graph B = B(I) is constructed as follows (see Figure 2):
(i)	Take a grid-like graph with vertices &(«.£), (a, ,0) e [2n + 2] x [2m + 3], and an edge between vertices and	if and only if |a — a'| + — P= 1.
(ii)	Remove the vertices b(2i.0) and b(2i.2m+3) for each i e [n + 1].
CM
(iii)	Define as anchors the vertices b(2i+i)0) and b(2i+12m+3) for each i e [n], and the vertices &(o,/3) and b(2n+2,^) for each £ e [2m + 2] \ {0}.
00
(iv)	Remove the edges between any two anchors.
(v)	The weights of the edges are defined as follows:
Jh
-	Each edge adjacent to an anchor has weight w4; in Figure 1 these edges are thicker.
-	If the literal xi appears in clause Cj, then the edge 6(2i-1)2j)6(2i)2j) has weight w2 — 1; in Figure 1 these edges are dashed.
-	If the literal —xi appears in clause Cj, then the edge b(2i,2j)b(2i+1,2j) has weight w2 — 1; in Figure 1 these edges are dashed.
-	The edge b(2i—1.2m+2)b(2i.2m+2) has weight w2 + |{j | literal Xi appears in Cj}|; in Figure 1 these edges are annotated.
-	The edge b(2i.2m+2)b(2i+1.2m+2) has weight w2 + |{j | literal — Xi appears in Cj}|; in Figure 1 these edges are annotated.
-	all other edges have weight w2.
cK	2
Note that each edge in the blue graph B has weight at least w2 — 1. Hence, independently of the red graph R to be defined below, a drawing of B with crossing number at most k < (w2 — 1)2 has to be an embedding of B. Henceforth, we will assume that B is anchored embedded. Note that the graph B has a unique combinatorial embedding with anchors because of 3-connectivity. For each variable xi, we define two columns; see Figure 3. The column CiT is the region of the disk enclosed between the paths
cm IN
O
b(2i—1,0) b(2i—1,1) • • • b(2i-1,2m+3) and
oo	w^.« wm« • • • b(2i.2m+2)b(2i+,2m+2)b(2i+1,m+3).
and the column CF is the region of the disk enclosed between the paths
b(2i—1,0)b(2i—1,1)b(2i.1)b(2i,2) • • • b(2i,2m+2)b(2i— 1,2m+2)b(2i— 1,2m+3) and b(2i+1,0)b(2i+1,1) • • • b(2i+1,2m+3) •
The blue edges of the form 6(a.^)b(a+1.^) are called horizontal. The blue edges of the form b(a.^)b(a.^+1) are called vertical. The weights of the horizontal edges b(2i—1.^)b(2i.^) contained in the column CT have been chosen so that they add up to 2(m + 1)w2: each time we have a —1 in the weight of b(2i—1.2j)b(2i,2j) we have a +1 in the weight of b(2i—1.2m+2)b(2i,2m+2). A similar statement holds for the column CF: the weights of the horizontal edges 6(2i.^)6(2i+1.^) contained in the column CF add up to 2(m + 1)w2.
For each clause Cj, we define two rows; see Figure 3. The upper row Uj is the region of the disk enclosed between the paths
Jh
b(0,2j)b(1,2j) • • • b(2n+2,2j) and b(0,2j+1)b(1,2j+1) • • • b(2n+2,2j+1),
CD
and the lower row Lj is the region of the disk enclosed between the paths
b(0,2j— 1)b(1,2j— 1) • • • b(2n+2,2j — 1) and b(0,2j)b(1,2j) • • • b(2n+2,2j)-
i-H
o o
CO
¿2 o u
IN
0 o
1
CO
£ CO CO
m
CD
$h
CD
m
u
a
CD U
6
(0,2m+2)
b(0,2j+1)
b(0,2j) r(0,j) b(0,2j-1)
(0,1)
		b(2i—1,2m+2)	b(2i,2m+2)	
		! ^b(2i,2j+1)		
	jb(1,2j)	b(2i—1,2j)± b(2i ,2j)	b(2 i+1,2j)	
	b(1,2j—1 )	\b(2i,2j—1)		
		b(2i—1,1) ^b(2i,1)		
				
b(2n+2,2m+2)
b(2n+2,2j+1) r(2n+1,j)
(2n+2,2j)
(2n+2,2j—1)
(2n+2,1)
6
(2i—1,0)
r(xi)
6,
(2i+1,0)
Figure 2: The graph B = B(I). Anchors of the red graph are included to show the cyclic ordering of AB U AR. The thick edges have weight w4. The other edges have weights between w2 and w2 — m depending on the instance I.
There is an additional row, called enforcing row and denoted by Renf, which is the region of the disk enclosed between the paths
b(0,2m+1)b(1,2m+1) • • • b(2n+2,2m+1) and b(0,2m+2)b(1,2m+2) • • • b(2n+2,2m+2) •
The role of the enforcing row Renf is to reduce the number of possible drawings to a well-structured subset of drawings. We will use the columns and the rows as some sort of coordinate system to tell where some red vertices go. For example, we may refer to the face CT n Lj.
The red graph R = R(I) is constructed as follows (see Figure 4):
(i)	Take a grid-like graph with vertices r(a>@), (a, ft) e [2n +1] x [m + 2], and an edge between vertices r(a>@) and r^/,^) if and only if |a — a'| + |ft — ft= 1.
(ii)	Remove the four vertices r^o), r^m+2), r(2n+1,o), and r(2„+1;m+2).
(iii)	For each variable Xi, identify the vertices r(2i-1,0) and r(2i,0) into a new vertex called r(xj), and identify the vertices r(2i-1m+2) and r(2i m+2) into a new vertex called r'(xi). For each variable xi, the vertices r(xi), r'(xi) are anchors for R. The vertices r(0 j) and r(2ra+1j) are also anchors for R, for every j e [m + 1] \ {0}.
(iv)	Remove the edges between any two anchors.
(v)	The weights of the edges are defined as follows:
i-H
o o
CO
¿2 o u
IN
0 o
1
CO
£ CO CO
b(2i-1,2m+3) r'(xi) b(2i+1,2m+3) r'(xi+i) b(2i+3,2m+3)
r— 1 1 1		b(2i-1,2m+2)				b(2i+3 ,2m+2)	i i i i i i i
1 1 1 1				b(2i,2m+2)			
1 1 1						1 1 1 1 1 1	
1 1 1						t t 1 1 1 1	
1 1 1 1		b(2i-1,1)	b(2i,1)			1 1 1 1 b(2i+3 ,1 ) i i	
1 1 1						!	
"(0,2j+1)
b(0,2j) r(0,j) b(0,2j-1)
i 1					n 1 1 1
i i i			b(2i,2j+1)		1 1
i					1 1
i i	b(1,2j-1 )		b(2i,2j-1)		1 1 1
i i i i					1
i i i L				l i	
b(2i-1,0) r(xi) b(2i+1,0) r(xi+1) b(2i+3,0)
Figure 3: Left: columns Cf (lighter shading) and (darker shading). Right: the upper row Uj (darker shading) and the lower row Lj (lighter shading).
-	For each variable xi the edge r(2j_1)m+1)r(2j,m+1) has weight w4; in Figures 1 and 4 these edges are thicker.
-	For each variable xi and each clause Cj the edge r(2i-1,j)r(2i,j) has weight w — 1; in Figures 1 and 4 these edges are dashed.
-	All other edges have weight w.
For each variable xi the following two vertical paths are important:
r(xi)r(2i-1,1)^(21-1,2)... r(2i-1,m+1)r/(xi) and r(xi)r(2i,1)r(2i,2)... r(2i,m+1)r/(xi).
We will use Vi to denote their union. For each clause Cj, we will consider the horizontal path Hj defined by
r(0,j)r(1,j) . . . r(2n+1,j).
We also define the horizontal enforcing path Henf as
CO CD
Jh
CD CO
u
a
CD U
r(0,m+1)r(1,m+1) . . . r(2n+1,m+1).
The role of the horizontal enforcing path Henf will be to reduce the number of possible drawings to a well-structured subset of drawings.
It is important to note that the paths V1, V2,..., Vn, H1,H2 ..., Hm, Henf form a partition of the edge set of the red graph R. Hence, we can add the number of crossings that each of them contributes separately to obtain the crossing number of a drawing. Note also, that the intersection of a vertical pair of paths Vi and a horizontal path Hj (or Henf) always consists of two vertices.
Let G = G(I) be the anchored graph obtained by joining the red graph R and the blue graph B. The (clockwise) circular ordering of the anchors along the boundary of the disk is as follows:
• For each clause Cj we have the sequence of anchors b(0,2j-1), r(0 j), b(0 2j), b(0,2j+1), and the sequence b(2n+2,2j+1), r(2n+1,j), b(2n+2,2j), b(2n+2,2j-1). Hence, the anchor r(0,j) is in the lower row Lj and anchor r(2n+1,j) is in the upper row Uj.
CM
i-H
o
cm
o
oo
o u d
CM IN
0 o
cm
1
cm 00 cm cm
£ CO CO
Cfl CD
u
CD Cfl
a
CD U
b(0,2m+2) r(0,m+1) b(0,2m+1)
b(0,2j+1)
b(0,2j) r(0,j) b(0,2j-1)
b
(0,3)
b(0,2) r(0,1) b(0,1)
b(2n+2,2m+2) r(2n+1,m+1)
b(2n+2,2m+1)
b(2n+2,2j+1)
r(2n+1j)
b(2n+2,2j)
b(2n+2,2j—1)
b(2n+2,3) r(2n+1,1)
(2n+2,2)
(2n+2,1)
b(2i—1,0) r(Xi) b(2i+1,0) r(Xi+1) b(2i+3,0)
Figure 4: The graph R = R(I). Anchors of the blue graph are also included to show the cyclic order of AB U AR. Thick edges have weight w4; dashed edges have weight w — 1; the remaining edges have weight w.
•	For each variable Xj, the anchor r(xj) is between b(2i-i,o) and b(2i+10), and the anchor r'(xj) is between b(2i-i,2m+3) and b(2i+i;2m+3). Hence, r(xj) and r'(xj) are in both columns Cf and Cf.
•	Anchor r(o,m+i) is between b(o,2m+i) and b(o,2m+2), anchor r(2n+i,m+i) is between 6(2n+2,2m+2) and b(2n+2 2m+i). Hence, anchors r(0,m+i) and r(2n+i,m+i) are in the enforcing row Renf.
•	Anchor b(0)i) comes immediately after b(i)0), anchor b(i)2m+3) comes immediately after b(o,2m+2), anchor 6(2n+2,2m+2) comes immediately after b(2n+i,2m+3), and anchor b(2n+i,o) comes immediately after b(2n+2)i).
This completes the description of the anchored graph G. We first show the easy direction of the proof, which will also give an idea of how the reduction works. Recall that we have defined k = (6nm + 6n + 2m + 1)w3 — m(w2 + w — 1).
Lemma 2.2. If the instance I is satisfiable, then there is an anchored drawing of G with k crossings. Moreover, the restriction of the drawing to R or to B is an embedding.
Proof. We draw the blue graph B without crossings. The corresponding embedding is unique. The red graph R is also going to be drawn without crossings. Hence, it is enough to describe in which face of B is each red vertex and (when not obvious) where the red edges cross the blue edges. See Figure 1 for a particular example. Let bi e {T, F} be an assignment for each
variable x of I that satisfies all clauses. We draw the two red vertical paths of Vi inside the column Cbi. For each clause Cj we proceed as follows. Let xt, where t = t(j), be a variable whose value bt makes the clause Cj true. We then draw the horizontal path Hj as follows: the subpath of Hj between r(0j) and r(2t-1,j) is drawn in the lower row Lj, the edge T(2t-i,j)r(2t,j) crosses from Lj to Uj through the blue edge in Lj n Uj n C^4, and the subpath of Hj between r(2t j) and r(2ra+1j) is drawn in the upper row Uj. The path Henf is drawn inside the row Renf. Note that this description implicitly assigns to each non-anchor vertex of R a face of B. The drawing can be extended to a planar embedding of R in such a way that no red edge crosses twice any blue edge.
Let us now compute the crossing number of the drawing we have described. There are no monochromatic crossings in the construction; hence we only need to count the red-blue crossings. Each of the two paths in Vi contributes 2(m + 1)w3 to the crossing number of the drawing: edges in Vi have weight w, and each path in Vi crosses all the horizontal blue edges contained in Cbi, whose weights add to 2(m + 1)w2. Each horizontal path Hj contributes (2n + 1)w3 + (w — 1)(w2 — 1) to the crossing number of the drawing: the edges on the horizontal path Hj connecting V¿ to Vi+1 have weight w and cross 2n + 1 blue vertical edges whose weight is w2; there is only one red edge in Hj, namely r(2t(j)-1;j)r(2t(j)j) with weight w — 1, that crosses
O tí
CO CO
the boundary between rows Li and U, namely at the edge of Lj n Uj n Ct4 with weight w2 — 1 because the corresponding literal xi or —xi makes Cj satisfied. (Note that if the literal xi or —xi would not satisfy Cj, the weight of the crossed blue edge would be w2, which would mean an increment of cr(D) by w — 1. We will use this fact to prove the opposite statement of the Lemma below.) The horizontal path Henf contributes (2n + 1)w3 to the crossing number of the
drawing: the edges of Hj connecting Vj to Vj+1 have weight w and cross 2n + 1 blue edges whose weight is w2.
The crossing number of the drawing is thus
CM
n ■ 2 ■ 2(m + 1)w3 + m ■ ((2n + 1)w3 + (w — 1)(w2 — 1)) + (2n + 1)w3
CM cm
which is
(6nm + 6n + 2m + 1)w3 — m(w2 + w — 1) = k.	□
We next have to show the reverse implication: if the anchored crossing number of G is at most k, then the formula I is satisfiable. Henceforth, let us assume for the rest of this section that acr(G) < k, and let us fix an anchored drawing D of G with at most k crossings. As mentioned before, D cannot have any blue-blue crossing because otherwise cr(D) > k. In principle, D could contain red-red crossings; we will show below that in fact this is not possible, and hence all crossings are red-blue. It will be convenient to look at the number of red-blue crossings without taking into account the weights. We refer to such crossings as unweighted crossings. Simple arithmetic shows the following two properties.
W
Lemma 2.3. The drawing D has at most 6nm + 6n + 2m + 1 unweighted red-blue crossings.
• i
Proof. Each blue edge has weight at least w2 — 1 and each red edge has weight at least w — 1. Thus each red-blue crossing contributes weight at least (w — 1)(w2 — 1) towards the crossing number of D. If there were strictly more than 6nm + 6n + 2m + 1 red-blue crossings, then the
cm i—i
O
cm
weighted crossing number of the drawing would be at least
(6nm + 6n + 2m + 2)(w — 1)(w2 — 1)
= (6nm + 6n + 2m + 2)(w3 — w2 — w + 1) = (6nm + 6n + 2m + 1)(w3 — w2 — w + 1) + (w3 — w2 — w + 1) = k — (6nm + 6n + m + 1)(w2 + w — 1) + (w3 — w2 — w + 1) = k + w3 — (6nm + 6n + m + 2)(w2 + w — 1)
>	k + w3 — 28nmw2
>	k.

co
Hence there are at most 6nm + 6n + 2m + 1 red-blue unweighted crossings.	□
Using Lemma 2.3 and the properties of the enforcing row Renf and the horizontal path Henf we can show that the drawing D has the following structure.
IN
Lemma 2.4. If cr(D) < k, then:
(i)	For each clause Cj, the horizontal path Hj is inside the rows Uj U Lj and crosses precisely 2n + 2 blue edges.
(ii)	The horizontal path Henf is drawn inside the row Renf.
(iii)	For each variable xi, both vertical paths of V are inside the column CT or both are inside the column CiF.
Proof. As mentioned before, D cannot have any blue-blue crossing because otherwise cr(D) > k. Moreover, no blue edge incident to an anchor crosses any other edge because it has weight w4.
Through this proof, we use crunw(X) to denote the number of unweighted red-blue crossings of a red subgraph X with the blue graph. Each of the two red vertical paths in V crosses each cm of the horizontal rows Renf and Uj, Lj. Therefore
cm
crUnw(Vi) > 2 ■ (2m + 2).
Any horizontal path Hj crosses each of the columns CT, CiF and crosses the boundary between rows Lj and Uj. (Here we need that edges incident to the anchors do not participate in any crossing, as otherwise H1 could go below L1.) Therefore
crunw (Hj) > 2n + 2.
Similarly, for the horizontal path Henf it holds
crUnw(Henf) > 2n + 1.
We conclude that
n	m
crunw (R) = crunw (Vi) + crunw (Hj ) + crunw (Henf) i=1 j=1 > 2n(2m + 2) + m(2n + 2) + 2n + 1 = 6nm + 6n + 2m + 1.
Since by Lemma 2.3 we have crunw(R) < 6nm + 6n + 2m + 1, we conclude that
&
crunw (Vi) = 4m + 4, crunw (Hj) = 2n + 2, crunw (Henf) = 2n + 1.
Since no blue edge adjacent to an anchor can be crossed by any other edge, these equalities imply that each one of the paths in V is contained in the column Cf or in Cf, that the path Hj is contained in the rows Lj U Uj, and that the path Henf is contained in the row Renf.
We next argue that both paths in V are in Cf or both are in Cf. For this, consider the edge ej of the horizontal enforcing path Henf that connects the two paths of V. Since this edge ej has weight w4 it cannot cross any other edge in the drawing. In particular the endpoints of ej must be in the same face, say f, of the embedding of the blue graph B. Since this face f has to be in Renf, both endpoints of ej have to be in Cf or CF, and both paths from Vj are in the same column.	□
o
Lemma 2.5. If cr(D) < k, then the instance I is satisfiable. Moreover, the restriction of the drawing D to R or to B is an embedding.
cm
r
o
00

Proof. By Lemma 2.4, in the drawing D both paths in Vj are contained either in Cf or CF. Consider the assignment where variable xj gets value bj = T if the two paths of Vj are contained in Cf, and bj = F otherwise. We will show that this assignment satisfies the formula Ci A- ■ -ACm of the instance I.
We will use in our analysis the properties of D obtained in Lemma 2.4. For a red subgraph X, let cr(X) denote the crossing number of the subdrawing of D induced by X and the blue graph B.
All the edges in Vi have weight w. The weights of the horizontal blue edges contained in Cb add to 2(m + 1)w2. Furthermore, note that each of those blue horizontal edges is crossed by each of the two paths in Vj. Therefore we have cr(V) = 2 ■ (2m + 2)w3, and thus

&
cr(UjVj) = (4nm + 4n)w3.
cm
All the edges from the path Henf have weight w or w4, and hence only edges from Henf with weight w may cross the vertical blue edges contained in the row Renf. Inside the row Renf there are 2n + 1 vertical blue edges of weight w2, and thus
cm 00 cm cm
£ CO CO
cr (Henf) = (2n + 1)w3.
Since cr(D) < k and the paths V1,..., Vn, H1,... Hm, Henf form an edge-disjoint partition of the edges of R, we have
cr(UjHj) + cr(UjVj) + cr(Henf) < k,
and therefore
cr(UjHj) < k - (4nm + 4n)w3 - (2n + 1)w3 = m((2n + 2)w3 - (w2 + w - 1)). (1)
For each clause Cj, the edges of Hj have weight w, if they connect a vertex in Vj n Hj to a vertex in Vj+1 n Hj for some i, or weight w - 1 if they connect both vertices of Vj n Hj. Because of Lemma 2.4, the edges with weight w - 1 are always within the column Cbi for some i. This means that the boundary of any column Cf or CF, which has weight w2, is always crossed by a red edge of Hj with weight w. Let cj denote the boundary between the lower row Lj and the upper row Uj. This boundary cj must also be crossed by an edge of Hj, and that crossing contributes weight at least (w - 1)(w2 - 1) to cr(Hj). We conclude that
cr(Hj) > (2n + 1) ■ w ■ w2 + (w - 1)(w2 - 1) = (2n + 2)w3 - (w2 + w - 1), (2)
&
with equality if and only if the crossing between Hj and dj contributes exactly (w - 1)(w2 - 1) to the crossing number. Combining equations (1) and (2), we see that
cr(Hj) = (2n + 2)w3 - (w2 + w - 1)	(3)
for each clause Cj. Therefore, the boundary dj must be crossed at a blue edge b(i.j)b(i+1.j) of weight w2 — 1 by a red edge r(2i—1j)r(2ij) of weight w — 1. It may be that t = 2i — 1 or t = 2i. Consider first the case when t = 2i — 1. By the construction of the blue graph B, the edge b(t.j)b(t+1.j) has weight w2 — 1 because the literal xi appears in the clause Cj of I. Moreover, the endpoints of r(2i—1j)r(2ij) must be in the column CT since they are part of the vertical paths
o
00
Vi. Hence, the clause Cj is satisfied by the assignment xi = bi = T we defined at the beginning of the proof. The case when t = 2i is alike, but in this case the literal —xi appears in the clause Cj of I, and we took the assignment xi = bi = F.
Finally, note that our analysis shows that in D there are exactly k red-blue crossings, and therefore there cannot be any red-red crossings. Hence the restriction of the drawing D to the
o u
red graph is an embedding.	□
We can now prove our main result.
Proof of Theorem 2.1. Given an instance I for SAT, we construct anchored graphs R = R(I), B = B(I), and G = G(I) as described in the text. We further construct, for each X e {G, B, R}, the graph HX obtained from X by replacing each edge uv e E(X) of weight wuv by wuv parallel paths of length 2 connecting u to v. It is clear that HR and HB is a vertex-disjoint decomposition of Hg into planar anchored graphs. Since the weights of X are bounded by a polynomial in n and m, it follows that the graphs HG,HR,HB can be constructed in polynomial time. As discussed in the introduction, we have acr(HG) = acr(G). From Lemmas 2.2 and 2.5 if follows that acr(HG) = acr(G) < k if and only if I is satisfiable.	□
o
2.2 Crossing number for near-planar graphs
CM
We can now show that computing the crossing number of near-planar graphs is NP-hard. Our reduction is from the problem in Theorem 2.1, and we make use of the fact that the anchored
00
graph is decomposed into two vertex-disjoint planar anchored graphs R and B. The high-level cm approach is the following: we replace each edge of R U B by an edge with heavy weight and replace the boundary of the disk by a cycle C with heavy weights. The resulting graph is planar. We make it near-planar adding an arbitrary edge connecting R to B. The heavy weights of C force that, in an optimal drawing, C is embedded. Moreover, the additional edge forces the graphs R and B to be drawn on the same side of C, thus resembling an anchored drawing.
I-H
Theorem 2.6. Computing the crossing number of near-planar graphs is NP-hard.
Proof. Consider an anchored graph G, possibly with weighted edges, that is decomposed into two vertex-disjoint planar anchored graphs R and B. Let W be the sum of the weights of the edges in G; if G is unweighted, then W is the number of edges in G. The construction will use a parameter A = 320Wnm > 2W. (In this proof, setting A = 2W + 1 would be enough, but we will need such larger A in the proof of Corollary 2.8 below.)
Consider the weighted graph G' = G'(G, A), without anchors, obtained from G as follows: we start with G and multiply the weight of each edge by A. For every two consecutive anchors a and a' of G in the cyclic ordering nG, we introduce in G' an edge aa' with weight A4. The set of added edges defines a cycle, which we denote by C = C(G, A). This completes the description of G'. We also fix an arbitrary vertex r of R that is not an anchor, an arbitrary vertex b of B that is not an anchor. (If all vertices of R are anchors we just subdivide an edge and take r as the new vertex. A similar procedure can be done with B.) We will study the crossing number of G' + rb.
Firstly, we show that G' is planar, and thus G' + rb is a near-planar graph. The graph G'
consists of the cycle C connecting consecutive anchors of G, and two planar anchored graphs R and B. We can thus embed G' taking an embedding of C in R2, embedding R in the disk
o
00
bounded by C in R2, and embedding B in the exterior of the disk. Note that the embeddings of R and B exist because they are planar anchored graphs. Since the weight of the edge rb is one, it follows that G' + rb is a near-planar graph, even when replacing each edge of G' by the corresponding number of subdivided parallel edges.
We claim that acr(G) = |_cr(G' + rb)/A2J. Consider an optimal anchored drawing D of G in a topological disk Q with cr(D) = acr(G). We then extend the drawing D to obtain a drawing D' of G' + rb as follows. Pushing the interior of the edges inside Q, we may assume that D touches the boundary dQ of Q only at the anchors. We then draw the edges aa' of G' between consecutive anchors along the boundary of the disk Q. Finally, we draw the edge rb so as to minimize the number of crossings it contributes. Each crossing of D contributes A2 crossings to D'. The edge rb can cross each edge of G' — E(C) at most once in the drawing D' because of optimality of D and the drawing of rb. Therefore cr(D') < A2 ■ cr(D) + AW because the sum of the edge weights in G was W. Using that A > 2W we get
cr(G' + rb)/A2 < acr(G) + W/A < acr(G) + 1/2.	(4)
Let D' be a drawing of G' + rb in the plane such that no edge crosses itself and no two edges cross more than once. If the cycle C is embedded and no edge of C is involved in a crossing, then each pair of edges not in C can cross at most once, and hence cr(D') is upper bounded by
(W
Gï
£ CO
( 2 )A2 + 1 • W • A < A4, where we have used again A > 2W. If the restriction of V to C is not
an embedding or some edge of C participates in a crossing, then cr(D') > A4. It follows that in every optimal drawing D' of G' + rb, the cycle C is embedded and no edge crosses C.
Consider now an optimal drawing D' of G' + rb with cr(D') = cr(G' + rb). Let Q be the disk bounded by the image of C in D'. Since no edge of G' + rb can cross an edge of C, the drawing D' is contained in the closure of Q. If in D' we remove the image of C and the image of the edge rb, then we obtain an anchored drawing of G, which we shall denote by D. Note that cr(D) is equal to cr(D') minus the number of crossings contributed by rb and scaled down by A2 because of the weights introduced in G'. We thus have
acr(G) < acr(V) < cr(V/)/A2 = cr(G + rb)/A2.
Combining with equation (4) we get
acr(G) < cr(G' + rb)/A2 < acr(G) + 1/2.	(5)
Since acr(G) is an integer, this finishes the proof of the claim acr(G) = |_cr(G' + rb)/A2J.
The graph G' + rb can be constructed from G in polynomial time. Moreover, since since the weights of G' are polynomially bounded, we can also replace each edge by parallel subdivided edges to obtain an unweighted graph He + rb, as described in the introduction, that satisfies cr(G' + rb) = cr(He + rb). Since the graph He + rb is near-planar and acr(G) = |_cr(He + rb)/A2J, the result follows from Theorem 2.1.	□
CD
2.3 Extensions
CD
Our NP-hardness proof in Section 2.1 has additional properties that imply certain extensions worth to be mentioned. Let G, R and B be as defined in Section 2.1. The key observation for our extensions is that Lemmas 2.2 and 2.5 imply that the following statements are equivalent:
• i
•	the instance I is satisfiable;
a
CD	• graph G has an anchored drawing with at most k crossings;
iH
•	graph G has an anchored drawing with at most k crossings such that the restrictions to each of R and B are embeddings.
o
A direct consequence is the following.
Corollary 2.7. The following problem is NP-hard: given an anchored graph G decomposed into two vertex-disjoint graphs R and B, compute the minimum of acr(D) over the anchored drawings D of G that are an embedding when restricted to R and when restricted to B.
Since the embedding of B and the embedding of R are unique, we can modify the construction a bit to obtain 3-connectivity. The approach can be summarized as follows: we multiply the weights by a large enough parameter A and then add edges to increase connectivity. The contribution of the original edges to the crossing number grows quadratically in A while the contribution of the new edges can be kept at O(Anm).
Corollary 2.8. The following problem is NP-hard: given a simple planar, 3-connected graph G and an additional edge xy, compute the crossing number of G + xy.
Proof. Consider the anchored graph G and the subgraphs B and R, as constructed in Section 2.1. Recall the parameter A = 320Wnm, the planar graph G/, and the edge rb used in the proof of Theorem 2.6.
We now construct another planar graph G from G/, as follows. See Figure 5 for an example of the transformation locally. We start with a copy of G/ and replace each edge uv of weight wuv with wuv edges, each subdivided once, and connect the subdividing vertices with a path. Let's call the resulting graph G//, which is also planar. We call the additional vertices subdividing vertices. Consider an embedding of G//, which is unique up to a permutation in each group of parallel paths. Within each non-triangular face defined by blue edges and edges of C, we add (at most 4) edges between subdividing vertices so that the subgraph of G// induced by B U C is 3-connected. For the red graph R, we do a slightly different transformation: within each non-triangular face with red edges we add (at most 4) edges between the red .subdividing vertices so that the subgraph of G// induced by R is 3-connected. (Thus, we do not add new edges connecting R to C.) The resulting graph is G. It is planar by construction and it is 3-connected because R has at least 3 anchors. The edges added in the transformation from G// into G are called additional edges. Note that the embedding of G// has less than 20nm faces and therefore there are at most 80nm additional edges.
The transformation from G/ to G// is similar to the transformation from G/ to He discussed in the introduction, and thus cr(G// + rb) = cr(G/ + rb). From equation (5) in Theorem 2.6 we conclude
A2acr(G) < cr(G// + rb) < A2acr(G) + A2/2	(6)
£ CO CO
Since G// is a subgraph of G, we have
cr(G// + rb) < cr(G + rb)	(7)
Consider an optimal drawing D// of G// + rb. As discussed in the proof of Theorem 2.6, in D// the cycle C is embedded and we may assume that R and B are drawn inside the disk bounded
CD ■ i J-H
CD W
by C. We modify this drawing into a drawing of G + rb in the following way. We redraw each edge aa/ in C in such a way that vertices incident to any additional edge are in the interior of
U
C. (This is the reason for the asymmetry treating B and R in the construction of G. If both R and B would have additional edges incident to subdividing vertices of C, this step would not be possible.) This step does not introduce any crossing. Then, we draw each of the 80nm additional edges optimally; each such edge is inside the disk bounded by C. Each additional edge can incur into at most AW + 80nm new crossings because the sum of the weights of G — C is at most AW + 80nm. From the resulting drawing of G + rb we obtain
cr(G + rb) < cr(G// + rb) + 80nm ■ (AW + 80nm) < cr(G// + rb) + (3/8)A2.
C
C
C
CM
i-H
o
CM
o
CO
¿2 o u
cm IN
0 o
cm
1
cm CO cm cm
£ CO CO
m
CD
$h
CD
m
u
a
CD U
Figure 5: Example showing the transformation from G' (left) to G'' (center) and to G (right). The numbers on the left indicate the weights of the edges.
Combining with equations (6) and (7) we get
A2acr(G) < cr(G + rb) < cr(G'' + rb) + (3/8)A2 < A2acr(G) + (7/8)A2.
It follows that
acr(G) = |_cr(G + rb)/A2J;
Since computing acr(G) is NP-hard by Theorem 2.1, it is also NP-hard to compute cr(G + rb). The graph G can be constructed in polynomial time, it is planar and 3-connected, as desired. □
A rotation system in a graph G is a list n = (nv)veV(G), where each nv is a cyclic permutation of the edges incident to vertex v. A drawing of a graph G with rotation system n is a drawing where the the clockwise order of the edges incident to vertex v in the drawing is given by the permutation nv. Pelsmajer et al. [18] have recently studied the crossing number with rotation systems. Using a reduction from Linear Arrangement they show that computing the crossing number with rotation system is NP-hard. (As noted in [18], we can keep working with weighted edges when studying this crossing number.)
Since the graphs R and B used in our construction have a unique anchored embedding, we already know a priori the rotation system in any drawing of G whose restriction to R or to B is an embedding. Thus Corollary 2.7 implies the following.
Corollary 2.9. The following problem is NP-hard: given an anchored graph G and a rotation system n for G, compute the minimum of acr(D) over the anchored drawings D of G with rotation system n. The problem remains hard when the graph G is cubic.
Proof. When the rotation system is fixed, we can replace each vertex by a large hexagonal grid and attach the edges on the boundary of grid in the same order as in the rotation system. See Section 3 in [18] for the details. (To keep the graph anchored, we just need to make several vertices in the boundary of the hexagonal grid anchors.)	□
From Theorem 2.6 we also obtain the following.
Corollary 2.10. Computing the crossing number of a graph with fixed rotation system is NP-hard, even when the graph is planar and 3-connected.
in
o
Proof. Consider the graph G used in the proof of Corollary 2.8. It is planar and 3-connected. For each non-anchor vertex of (R U B) — V(C) we prescribe the rotation given by the unique combinatorial embedding of R and of B as anchored graphs. For each vertex of C, we prescribe the rotation system that forces R U B to be drawn in the same side of C. Thus, the edge rb is not needed in the reduction.	□
As shown in [18], hardness of crossing number with rotation system implies hardness of cross-00 ing number for cubic graphs by blowing up each vertex with a hexagonal grid. The described reduction yields a new, geometric proof of NP-completeness of the crossing number problem, even when restricted to cubic graphs. Hardness of the crossing number problem for cubic graphs was established by Hlineny [11], who asked if one can prove this result by a reduction from an NP-complete geometric problem instead of the Optimal Linear Arrangement problem used in his proof.
A rectilinear drawing of a graph is a drawing where each edge is drawn using a straight-CM line segment. The rectilinear crossing number of a graph G is the minimum number of crossings taken over all rectilinear drawings of G. On the one hand, lower bounds for the crossing number of a graph G are also lower bounds for the rectilinear crossing number of G. On the other hand, the drawings used in Lemma 2.2 to show the upper bound on the crossing number are rectilinear drawings. In fact, all the drawings we have described can be made straight-line drawings without increasing the number of crossings. In particular, we can replace each vertex by a hexagonal grid and still keep a rectilinear drawing because in the drawing of Lemma 2.2 we know for most edges whether they are horizontal or vertical, and for a few edges we have to decide whether they are diagonal or horizontal. From Corollaries 2.8 and 2.10 we conclude the following:
CM
Corollary 2.11. The following problem is NP-hard: given a simple planar, 3-connected graph cm G and an additional edge xy, compute the rectilinear crossing number of G + xy. 00
Corollary 2.12. Computing the rectilinear crossing number of cubic, 3-connected graphs is NP-hard.
It should be noted that in our reduction for near-planar graphs we need high-degree vertices along the cycle C. We do not know the computational complexity of computing the crossing number of the graph G + xy when G is planar and has bounded degree, or even degree 4. As discussed in the introduction, when G has degree 3 such crossing number can be computed in polynomial time; see [20] and [3].
3 1-planarity
In this section we show that it is NP-hard to decide whether a given near-planar graph is 1-planar. The approach is very similar to the one used to crossing number. However, while crossing numbers are global, the concept of 1-planarity is more local. Thus, we first define a gadget and study its 1-planar drawings. Afterward we show that deciding 1-planarity for anchored graphs is hard. An example showing the eventual reduction for a small example is shown in Figure 6. Finally, we consider near-planar graphs.
For any natural number t, a t-path is a path with t edges. A 5-thick edge connecting vertices u and v is a set of five 2-paths uviv, uv2v,..., uv5v, where v1,..., are distinct vertices of degree 2. Alternatively, such 5-thick edge is a complete bipartite graph K2,5 with u and v defining one of its parts. When a 5-thick edge is drawn without any crossings, it defines 4 inner faces. Those are the interior faces of the thick edge, each bounded by four edges. (The unbounded face of the drawing is not an inner face.) In our drawings, we will represent a 5-thick edge with a filled in lens-like shape.
CD C/3
J-H
a
r<T nF i r<T nF , nT nF , nT nF , C1 C1 bi C2 C2 02 C3 C3 O3 C4 C4 b 4
cm
i-H
o
CM
o
00
o
Jh
cm IN
0 o
cm
1
cm 00 cm cm
£ CO CO
«0
a1
«2
«3
a4
xi
X2
X3
x4
■ d4
f ^3
4d3
* d2
4 di
*di
Figure 6: Example of the resulting reduction for anchored 1-planarity for the formula on 4 variables x1; x2, x3, x4 and clauses -xi V -x3 V x4, -x2 V -x4, x2 V -x3, x1 V x2. The anchored 1-drawing in the figure corresponds to the boolean assignment x1 = x2 = T and x3 = x4 = F. The dashed line around the figure indicates the boundary of the disk.
CO CD
$H
CD CO
u
a
CD U
3.1 Basics and gadget
We first provide some basic properties of 1-planar graphs with 5-thick edges. If we have some 5-thick edges in a graph G, we view each of them a single (5-thick) edge and we no longer consider the vertices of degree 2 inside these 5-thick edges as vertices of G. After isolating as many edge-disjoint 5-thick edges as possible, we cover all remaining vertices of degree 2 by maximal t-paths (of various lengths) whose internal vertices have degree 2 in G.
To keep control over the drawings it will be convenient to restrict our attention to 1-drawings with the minimum number of crossings. For any drawing D of a graph G and any subgraph H of G, we use DH for the restriction of the drawing D to H.
Lemma 3.1. Let G be a 1-planar graph and let H be its subgraph consisting of 5-thick edges. Let D be a 1-drawing of G with the minimum number of crossings.
d
d
2
d
0
CM
i-H
o
CM
o
CO
o
£ CO CO
CD
■ I
J-H
CD
m
CD u
z
Figure 7: Transformation in Lemma 3.1(a). Applying these transformations to a 1-drawing produces another 1-drawing with fewer crossings as long as deg(z) = 2 (and z is not an anchor).
(a) The restriction DH of the drawing D to H is an embedding.
(b) Let z e V(G) and A c V(G) \ {z}. Let uv be a 5-thick edge in G. Suppose that there are 5 edge-disjoint paths in G - {u, v} from z to vertices in A. If in DH none of the vertices in A is in an inner face of the 5-thick edge uv, then in DH the vertex z cannot be in an inner face of the 5-thick edge uv.
The same properties hold if G is an anchored 1-planar graph, where no internal part of a 5-thick edge of H is an anchor, and D is an anchored 1-drawing of G with the minimum number of crossings.
Proof. We first show that in D no two parallel paths in the same 5-thick edge intersect. Indeed, whenever any two such paths cross in a 1-drawing, we can make a local change to get another
cm
1-drawing with strictly smaller total number of crossings. See Figure 7 for the transformation. Observe that the same transformation can be used for anchored drawings as long as degree-2 vertices in 5-thick edges are not anchors.
We next argue that there are no crossings involving different 5-thick edges. Consider a 5-thick edge uv and another 5-thick edge uV. We already know that Duv is an embedding. The vertices u' and v' have to be in the same face of Duv: if they are in different faces, each of the 5-edge disjoint paths forming u'v' have to cross some of the edges of the face containing u', which is not possible because such face has degree 4. Let us consider the 2-paths connecting u' to v'. At least one of them, say u'v1v', does not cross the boundary of the face F of Duv that contains u' and v'. If another 2-path u'v2v' crosses the boundary of F, then the face bounded by the 4-cycle u'v1v'v2u' either contains both u and v or none of them. It is easy to see that the 2-path u'v2v' is crossing twice a 2-path utv of the boundary of F and we can unmake the crossings. We conclude that no two 5-edges of H participate in a mutual crossing and thus DH is an embedding. This completes the proof of item (a).
To prove item (b) we use an argument similar to before. Assume for the sake of contradiction, that the face fz in DH that contains z is an inner face of uv, and thus has degree 4. Since we have 5 edge-disjoint paths in G - {u, v} from z to A, and A has no vertex in fz, each of those
paths has to cross a distinct edge on the boundary of fz, which is not possible.	□
Our construction is based on a gadget consisting of a pair of graphs X and Y. We first describe the gadget and then analyze certain types of 1-drawings for X U Y. Let X be the embedded graph constructed as follows (see Figure 8, left):
Jh
(i) The vertex set of X is grid-like with vertices , (a, e [4] x [4].
(ii)	For each (a, ,0) e [3] x [4], ft = 2 we connect u^,^ and u(a+1,^) with a 5-thick edge.
(iii)	For each (a, ^) e [4] x [3], a = 2 we connect u^,^ and u(a ^+1) with a 5-thick edge.
z
i-H
o o
CO
A
o u d
U(0,1)
u(0,0)
«(4,4)
V(0,2)
v(0,1)
7 V(1,2) 7
7 7 6 \6 7 7
1 \yL-6
( 6^\Tl6 (
7 7 6\ 6 7 7
v(0,0) 7 v(i,0) 7 v(2,0)
V(2,2)
(2,1)
U(1,0)
u(4,0)
Figure 8: Left: the embedded graph X with some of its vertices and faces labeled. The 5-thick edges are shaded. Right: the graph Y with its vertices labeled; each edge is actually a path whose length is annotated with the edge.
0 o
1
CO £
CO CO
CO CD
Jh
CD CO
u
a
CD U
(iv)	We add 2-thick edges between u(0,2) and u(12), between u(3,2) and u(4,2), between u(2,0) and u(2>1), and between u(2,3) and u(2,4).
(v)	We add 2-path edges connecting U(2 2) to «(1)2), U(2 3), U(3 2) and to U(21).
(vi)	The embedding is the one obtained by assigning vertex to the point (a, ft) e [4] x [4] in the Euclidean plane, and drawing the edges with almost straight curves. Thus, the embedding makes X look like a grid
(v) We use /(«,£) to denote the square-like face with in its bottom left. The other faces, defined by edges within one single 5-thick edge, are called internal faces. (Each 5-thick edge has 4 internal faces.)
We call Xpos the variant of X where the 2-path connecting u(12) to u(2 2) is replaced with a 3-path (Xpos is part of Figure 9, right). We call Xneg the variant of X where the 2-path connecting U(2 2) to U(3 2) is replaced with a 3-path.
Let Y be the graph, without a specified embedding, constructed as follows (see Figure 8, right):
(i)	Start with a grid-like vertex set with vertices	(a, ,0) e [2] x [2], and add two disjoint 7-paths between and v^/,^) if and only if |a — a'| + — ,0'| = 1.
(ii)	Remove V(2 2) and the 7-paths incident to it.
(iii)	Add two new vertices v and v' and the edge vv'. Next add two 6-paths connecting v to v(01) and two 6-paths connecting v' to v(21). Finally add 6-paths connecting v and v' to v(1,2) and v(1,o).
Let Z e {X, Xpos, Xneg}. A drawing of Z U Y is compliant if it extends the embedding of Z, no part of Y is drawn in the outer face of Z, vertex v(0 0) is in the face /(0,0) of Z, vertex v(o,2) is in the face /(0,3) of Z, vertex v(2 2) is in the face /(3,3) of Z, and vertex v(2 0) is in the face /(3,0) of Z. Let us call the vertices v(0 0), v(0 2), v(2 2), v(2 0) the corners of Y. Thus a compliant drawing has a fixed position for the corners. In our figures the corners are drawn with squares, while the other vertices of Y are drawn with empty circles. In the following we will only consider compliant 1-drawings of Z U Y. See Figure 9 for some examples of compliant
1-drawings.
o
oo
o u
IN
0 o
1
00
£ CO CO
m
CD
$H
CD
m
u
a
CD U
Figure 9: Left: A compliant drawing of X U Y with the properties of Lemma 3.2. Right: A compliant drawing of Xpos U Y with the properties of Lemma 3.3.
For each non-corner vertex of Y there are at least 5 edge-disjoint paths connecting it to the corners. Since the position of the corners is fixed in a compliant 1-drawing, Lemma 3.1(b) implies that no non-corner vertex of Y can be in an inner face of a 5-thick edge of Z. Thus, in a compliant 1-drawing of Z U Y each vertex of Y is in some face /(a„g).
Lemma 3.2. For any Z e {X, Xpos,Xneg}, there is a compliant 1-drawing of Z U Y satisfying any combination of a property stated in (a) and a property stated in (b) below:
(a)	V(o,i) is in the face /(o,i) and f(2)i) is in the face /(3,1), or v(0,i) is in the face /(0,2) and v(2,i) is in the face /(3,2).
(b)	V(i,o) is in the face /(i>0) and V(i 2) is in the face /(i>3), or V(i 0) is in the face /(2,0) and v(i,2) is in the face /(2,3).
Proof. See the left side of Figure 9 for the drawing of X U Y. The remaining drawings of X U Y are obtained by vertical and/or horizontal mirror symmetries. For Z = Xpos or Z = Xneg just subdivide once an edge incident to u(2 2).	□
Lemma 3.3. There is a compliant 1-drawing of Xpos U Y with the following two properties:
•	v(0,i) is in the face /(0>i) and v(2)i) is in the face /(3,2);
•	v(i,0) is in the face /(i>0) and v(i>2) is in the face /(i>3).
There is a compliant 1-drawing of Xneg U Y with the following two properties:
•	v(0,i) is in the face /(0>i) and v(2)i) is in the face /(3,2);
•	v(i,0) is in the face /(2,0) and V(i 2) is in the face /(2,3).
Proof. See the right side of Figure 9 for the drawing of Xpos U Y. For Xneg U Y apply a vertical mirror symmetry.	□
Lemma 3.4. For any Z e {X, Xpos,Xneg}, any compliant 1-drawing of ZU Y has the following properties:
(a)	vertex v(0)i) is in the face /(0>i) or /(0,2) of Z;
(b)	vertex v(2,i) is in the face /(3,i) or /(3,2) of Z;
o
J-H
o
a» o
cm
i
(c)	vertex v^q) is in the face /(1,0) or /(2,0) of Z;
(d)	vertex v(i,2) is in the face /(1,3) or /(2,3) of Z;
(e) if V(10) is in the face /(1>0) of Z, then V(12) is in the face /(1>3) of Z;
(f) if v(1>0) is in the face /(2,0) of Z, then v(1>2) is in the face /(2,3) of Z.
00 Proof. Consider any compliant 1-drawing of Z U Y. The vertex V(01) has a path of length 7 to V(0 Q) and a path of length 7 to V(0 2). This implies that V(01) must be in the face /(0>1) or /(0,2) of Z and proves item (a). Items (b)-(d) follow by rotational symmetry.
To prove item (e), we note that there is a path of length 12 connecting V(10) to V(12). By item (d), V(12) is in the face /(1>3) or /(2,3). However, any path from /(1>0) to /(2,3) must cross 13 edges of Z. Thus v(12) must be in face /(1>3), and item (e) is proved. Item (f) follows from (e) by a vertical mirror symmetry.	□
cm
Lemma 3.5. If a compliant 1-drawing of Xneg U Y has vertex V(01) in the face /(0>1) of Xneg and v(1>0) is in the face /(1>0) of Xneg, then v(2>1) must be in face /(3>1) of Xneg.
If a compliant 1-drawing of Xpos U Y has vertex V(01) in the face /(0>1) of Xpos and V(10) is in the face /(2,0) of Xpos, then v(2,1) must be in face /(3,1) of Xpos.
If a compliant 1-drawing of X U Y has vertex V(01) in the face /(0>1) of X, then V(21) must be in face /(3,1) of X.
Proof. We first consider the case for Xneg U Y. Consider any compliant 1-drawing of Xneg U Y with the properties stated. Because of Lemma 3.4(e), vertex v(12) must be in the face /(1>3). The vertices v and v' have paths of length 6 connecting to V(10) and V(12). This implies that v and v' can only be in faces /(1;1) or /(1>2), as any other face /(a,^) requires at least 7 crossings to connect to V(10) or V(1 2). We distinguish three cases:
co
•	If the vertex v' is in the face /(1;1) (Figure 10 left), any path connecting v' to the face /(3,2) requires 7 crossings. Since there is a path of length 6 connecting v' and v(21), the vertex v(21) cannot be in face /(3,2). Thus by Lemma 3.4(b) v(21) must be in the face /(3>1).
•	If the vertex v' is in the face /(1>2) and v is in the face /(1;1), we argue as follows; see Figure 10, right. The 6-path connecting v to v(12), the 6-path connecting v' to v(10), and the edge vv' must all cross the 2-path connecting u(12) to u(2 2). Thus, no such compliant 1-drawing with v in /(1;1) and v' in /(1>2) is possible.
•	If the vertices v' and v are both in the face /(1>2), we note that the two 6-paths connecting v to v(o,1) and the 6-path connecting v to v(10) must cross the 2-path connecting U(12) to U(2,2). Thus, no such compliant 1-drawing with v' and v in /(1>2) is possible.
This finishes the proof for Xneg U Y. The claim for Xpos U Y follows from the claim for Xneg U Y
by a vertical and horizontal mirror symmetry. For the case of X U Y, we note that v(10) must be in the face /(1>0) or /(2,0) by Lemma 3.4(c). If v(10) is in the face /(1>0) the claim follows from the case Xneg U Y, and if v(10) is in the face /(1>0) then it follows from the case Xneg U Y. □
3.2 1-planarity of anchored graphs
Jh
In this section we prove the following result.
CD
Theorem 3.6. Deciding if a given anchored graph is an anchored 1-planar graph is NP-hard, even if the input graph is decomposed into two vertex-disjoint planar anchored subgraphs (and the decomposition is part of the input).
o
CM
o
CO
¿z
o u ctf
• A	- -
- j i [Tu	--f
	
	-J-r ! 1
	l'
	' \
	/ r +
1 I M S > i	-I
- 't	
	1 i
1 / •	¥
cm IN
0 Ö
o
cm
1
cm CO cm cm
£ CO CO
CO CD
$H
CD CO
$H
a
CD U
Figure 10: Analysis of the gadget Xneg U Y treated in Lemma 3.5
We use a reduction from SAT and a grid-like construction similar to the one used for anchored crossing numbers in Section 2.1. Like before, we consider an instance I for SAT with variables xi,..., and clauses C1,..., Cm, and construct two graphs B = B(I) and R = R(I).
The blue graph B = B(I) is constructed as follows (see Figure 6):
(i)	For each variable xi and each clause Cj, we make an embedded graph	such that
is a copy of Xpos if the literal xi appears in Cj, a copy of Xneg if the literal -xi appears in Cj, and a copy of X otherwise. We use w(Ojg) and /(aj) for the vertex U(a , g) and face /(a , g) of B(i 'j), respectively.
(ii)	We identify parts of the graphs
as follows. For each clause Cj, j < m, and each a G [3], we identify the faces and 5-thick edges of /(aj3)) and of /(,0,' "o+1) (i = 1,... ,n). For
(ij)
each variable xi, i < n, and each ft G [3], we identify the faces and 5-thick edges of /(3
and of /^J1 'j) (j = 1,...,m).
(iii) We disregard the embedding of the graph, and consider it as an abstract graph.
(iv) The anchors of B are the vertices u(1 ' u(n'^j, u^1,), and «(amj, where a, ^ G [4], i = 1,..., n and j = 1,..., m.
For each variable xi, we define two columns. The column CT is formed by the faces /(1 '
where j = 1,..., m and fl G [2]. The column CF is formed by the faces /(j ' , where j = 1,..., m and ft G [2]. In Figure 6, the columns are annotated on the top. The red graph R = R(I) is constructed as follows (see Figure 6):
(i) For each variable xi and each clause Cj, we make a graph R(i ' j) such that R(i ' j) is a copy
.	TAV 1 irnrf^v sty,
(a
of Y. We
use "ß) for the vertex v(a , ß) of R(i ' j).
(ii) We identify parts of the graphs
R(i j)
as follows. For each clause Cj, j < m, and each
a G [2], we identify the vertex with V((jj0+1) (i = 1,...,n).	For each variable xi,
i < n, and each fl G [2], we identify the vertex v(3'j) and of v^O^g)^ (j = 1,..., m). We also identify, pairwise, the two 7-paths that connect identified vertices.
(iii) For each i G [n] we create two vertices, ai and bi. For each variable xi, vertex ai is
,(i+1 ,j)
connected to v(2'0) with a 5-path and vertex 6 is connected to 2) with a 5-path.
(i , m)
Vertex a0 is connected to v(0 '¿j with a 5-path and vertex 60 is connected to v ( 0m with a 5-path.
(iv) For each j = 1,..., m we create four vertices, Cj, cj, dj, dj. For each clause Cj, vertex Cj is connected to v (0'j) with a 5-path, vertex cj is connected to v 'j) with a 5-path, vertex dj is connected to v (n'j with a 5-path, and vertex dj is connected to v (n'j with a 5-path. We also create two vertices c0 and d0. Vertex c0 is connected to v (0 '¿j with a 5-path and
vertex d0 is connected to v(n'!
o
u
CO CD
■ i-H
u
vertex d0 is connected to v(2 '0j with a 5-path. The vertices created in this step are the anchors of R.
Let G = G(I) be the anchored graph obtained by taking the union of the red graph R and the blue graph B. The clockwise circular ordering of the anchors along the boundary of the disk is defined by the following properties:
IN	• For each variable xj, we have the subsequences of anchors aj,u(3'o)u(2 o)'U(i q),®»— and
,	(i ' m) (i ' m) (i ' m) ,
bi-!, U(l ' 4) , U(2 ,4) , U(3 ' 4) , bi.
•	For each clause Cj, we have the subsequences of anchors Cj-1, u^' 1), cj, u(0' 2), u^' 3), Cj and
d- ' j) d/ ' j) ' j) d- 1 dj , u(4 , 3), d, u(4 , 2), u(4 ,1), dJ-1.
•	We have the subsequence ao,u(0 ' ¿),c0, the subsequence cm,u(1 ' m)),b0, the subsequence bn,u(n'4'm),dm, and the subsequence d0,u(n'0j,an.
This concludes the description of the graph G(I).
cn Lemma 3'7If the ,mtmce 1 * samable then G(I'has an aM 1-iramng-
Proof. We draw the graph B without crossings. The corresponding embedding is unique, up to permutations of parallel 2-paths. Thus, the embedding of B corresponds to the one used during its construction, and we can talk about the subgraphs B(j 'j) and their faces /(j).
Let qi G {T, F} be an assignment for each variable x* that satisfies all clauses. For each clause Cj, let xt(j) be the first variable whose value qt(j) makes the clause Cj true. For each variable xj and each clause Cj, the graph R(j ' j) is drawn according to the following cases:
Case i = t(j). We use the compliant 1-drawing of B(j 'j) U R(j 'j) given in Lemma 3.3.
(i ' j) • f ( >,1) in f(0 '1), v(2,1)
Case i < t(j). We use a drawing of B(i ' j) U R(i ' j) given by Lemma 3.2 with v(0' I) in /(0' !), v(i' j)
in /((3i'!), and with both v(! 'j)) and v(! '^ in C^.
Case i > t(j). We use a drawing of B(j ' j) U R(j ' j) given by Lemma 3.2 with v(0' j) in /j' 2), v(2' j)
in /((3 '2), and with both v|! ' j) and v|! ' j) in Cf. •/(3 ' 2)' (1 ' 0) (1 ' 2) j
It is easy to check that, whenever a vertex or a path appears in more than one subgraph R(j 'j), the drawing we have described in both subgraphs is the same. Therefore, we have described a drawing for R minus its set of anchors. The drawing of the 5-paths incident to the anchors is straightforward.	□
Lemma 3.8. If G = G(I) is an anchored 1-planar graph, then I is satisfiable.
o
00
Proof. Assume that G is an anchored 1-planar graph and consider an anchored 1-drawing D of G with the minimum number of crossings. Let H be the subgraph of G consisting of 5-thick edges. By Lemma 3.1(a), the restriction DH is an embedding. The embedding of DH is unique, up to permutation of parallel 2-paths, because H is essentially a subdivision of a grid. We can further argue that Db is an embedding. Indeed, if any of the 2- or 3-paths contained in would participate in some crossing in DB, they can be redrawn to obtain another 1-drawing with fewer crossings.
The embedding DB is unique, up to permutations of parallel 2-paths. Thus, DB corresponds to the embedding used during the previous discussion, and we can talk about the subgraphs B(jj) and their faces /(Ojg). By Lemma 3.1(b), the vertices of R cannot be in any inner face of
Db. Thus, each vertex of R is in some face /(Ojg).
For each variable x and each clause Cj, the anchors a^ bj, Cj, dj force that the vertex V(2 2) is in the face /(.j' 3). Indeed, if v(2' j)) would be in any other face, at least one of the paths
CM
connecting it to the anchors cannot be drawn with its vertices being in non-inner faces. Similar statements hold for each corner of each R(j j) and, as a consequence, the restriction of D to any B(j j) U R(j j) is a compliant 1-drawing. Furthermore, for each clause Cj the anchors cj and deforce that j) is in /(0 j and j is in /(. 2j).
Consider any variable Xj. Because of Lemma 3.4(e) and (f), the vertices /(j '0), j = 1,..., m, are all in the column CT or the column CF. In the former case, we define qj = T, and in the latter we define qj = F.
We next argue that the assignment {xj = qj}j satisfies all clauses Ci,..., Cm, which implies that I is satisfiable. To see this assume, for the sake of contradiction, that some Cj is not satisfied. This means that, whenever xj = T, B(jj) is a copy of X or Xneg, and whenever xj = F, B(j j) is a copy of X or Xpos. Since v(0 j) is in the face /(0'j), consecutive applications of Lemma 3.5 imply that v^'!) is in the face /(.j j for each i = 1,..., n, and therefore 'j is
in the face v^'j). This contradicts the fact that in D the vertex v^'j) is in the face /(.2j)), as discussed before.	□
Theorem 3.6 follows from Lemmas 3.7 and 3.8 because the construction of G takes linear time and has maximum degree 20.
I-H
3.3 1-planarity of near-planar graphs
Theorem 3.9. Deciding whether a given near-planar graph is 1-planar is NP-complete, even when the graph has bounded maximum degree, has bounded crossing number, and can be drawn in the plane so that one edge crosses two other edges, but every other edge participates in at most one crossing.
CO
Proof. The proof is very similar to the proof of Theorem 2.6, but in this case it will be convenient to build on the precise construction used in Section 3.2.
CD
Let G be the anchored graph constructed in Section 3.2. Consider the graph G' obtained from G as follows. For every two consecutive anchors a and a' of G in the cyclic ordering we introduce in G' a 5-thick edge connecting a to a'. The set of added edges defines a 5-thick cycle, which we denote by C. Finally, we add a 9-path between u(j 'j) and v(0'j)), and let e denote an edge on this path.
The graph G' is a near-planar graph because G' — e is planar: we can draw C as a cycle, draw B inside C planarly, and draw R outside C planarly. Adding the edge e to this drawing
shows that cr(G') < 10. All edges except e in this drawing obey the 1-planarity condition and it can be achieved that e crosses only two other edges.
CO
u
a
CD
o
CM
o
CO
¿2 o u d
The instance I is satisfiable if and only if G' is 1-planar. Indeed, when I is satisfiable, the drawing of G described in Lemma 3.7 can be extended to a drawing G' because e and C can be added without using additional crossings. When G' is 1-planar, its 1-drawing D with the minimum number of crossings has the property that Dc is an embedding because of Lemma 3.1(a). The edge e forces that G is drawn inside or outside C because e can only participate in one crossing. Therefore, the restriction of D to G is an anchored 1-drawing of G, which implies that I is satisfiable by Lemma 3.8. Since G' can be constructed from G in linear time and G' has maximum degree 20, the result follows.	□
Acknowledgments
We thank anonymous reviewers of [2] for several helpful suggestions.
CM IN
References
[1]	K. J. Borozky, J. Pach, and G. Toth. Planar crossing numbers of graphs embeddable in another surface. Int. J. Found. Comput. Sci., 17(5):1005-1016, 2006.
[2]	S. Cabello and B. Mohar. Adding one edge to planar graphs makes crossing number hard. In Proc. SoCG 2010, pages 68-76, 2010.
[3]	S. Cabello and B. Mohar. Crossing and weighted crossing number of near-planar graphs. Algorithmica, 60(3):484-504, 2011.
[4]	M. Chimani and P. Hlineny. Approximating the crossing number of graphs embeddable in any orientable surface. In Proc. SODA 2010, pages 918-927, 2010.
[5]	M. Chimani, P. Hlineny, and P. Mutzel. Vertex insertion approximates the crossing number of apex graphs. Eur. J. Comb., 33(3):326-335, 2012.
[6]	J. Chuzhoy. An algorithm for the graph crossing number problem. In Proc. STOC 2011, pages 303-312, 2011. See http://arxiv.org/abs/1012.0255 for the full version.
[7]	H. Djidjev and I. Vrto. Planar crossing numbers of genus g graphs. In ICALP 2006, volume 4051 of LNCS, pages 419-430, 2006.
[8]	M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Alg. Discr. Meth., 4:312-316, 1983.
[9]	M. Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci., 68(2):285-302, 2004.
[10]	C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. Algorithmica, 41:289-308, 2005.
[11]	P. Hlineny. Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B, 96(4):455-471, 2006.
[12]	P. Hlineny and G. Salazar. Approximating the crossing number of toroidal graphs. In T. Tokuyama, editor, ISAAC 2007, volume 4835 of LNCS, pages 148-159, 2007.
[13]	P. Hlineny and G. Salazar. On the crossing number of almost planar graphs. In M. Kaufmann and D. Wagner, editors, GD 2006, volume 4372 of LNCS, pages 162-173. Springer, 2007.
[14]	K.-I. Kawarabayashi and B. Reed. Computing crossing number in linear time. In Proc. STOC 2007, pages 382-390, 2007.
[15]	V. P. Korzhik and B. Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. In Graph Drawing, volume 5417 of LNCS, pages 302-312. Springer, 2008.
o
[16]	V. P. Korzhik and B. Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory, to appear.
¿1
o u (Ö
[17]	B. Mohar. On the crossing number of almost planar graphs. Informatica, 30:301-303, 2006.
[18]	M. J. Pelsmajer, M. Schaefer, and D. Stefankovic. Crossing numbers of graphs with rotation systems. Algorithmica, 60(3):679-702, 2011.
[19]	G. Ringel. Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 29(1-2):107-117, 1965.
i—l
[20]	A. Riskin. The crossing number of a cubic plane polyhedral map plus an edge. Studia Sci. Math. Hungar., 31:405-413, 1996.
o
[21]	S. Werner. On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary. Combinatorica, 29(1):121-126, 2009.
CO CD
Jh
CD CO
u
a
CD U