# Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation

Authors: A. Suebsriwichai; T. Mouktonglang
Journal: Journal of Applied Mathematics
 (2017)

---

## Abstract

The crossing number of graphG is the minimum number of edges crossing in any drawing of G in a plane. In this paper we describe a method of finding the bound of 2-page fixed linear crossing number of G. We consider a conflict graph G′ of G. Then, instead of minimizing the crossing number of G, we show that it is equivalent to maximize the weight of a cut of G′. We formulate the original problem into the MAXCUT problem. We consider a semidefinite relaxation of the MAXCUT problem. An example of a case where G is hypercube is explicitly shown to obtain an upper bound. The numerical results confirm the effectiveness of the approximation.


---

## Body

## 1. Introduction

LetG be a simple connected graph with a vertex-set V(G)={v1,v2,v3,…,vn} and an edge-set E(G)={e1,e2,e3,…,em}. The crossing number of graph G, denoted cr⁡(G), is the minimum number of pairwise intersections of edge crossing on the plane drawing of graph G. Clearly, cr⁡(G)=0 if and only if G is planar. It is known that the exact crossing numbers of any graphs are very difficult to compute. In 1973, Erdös and Guy [1] wrote,“Almost all questions that one can ask about crossing numbers remain unsolved.” In fact, Garey and Johnson [2] prove that computing the crossing number is NP-complete.A 2-page drawing ofG is a representation of G on the plane such that its vertices are placed on a straight horizontal line L according to fixed vertex ordering and its edges are drawn as a semicircle above or below L but never cross L.Then-cube or n-dimensional hypercubeQn is recursively defined in terms of the Cartesian products. The one-dimension cube Q1 is simply K2 where K2 is a complete graph with 2 vertices. For n≥2, Qn is defined recursively as Qn-1×K2. The order of Qn is |V(Qn)|=2n and its size is |E(Qn)|=n2n-1. Since Qn is planar for n=1,2,3, so cr⁡(Qn)=0 for each such n. Eggleton and Guy [3] showed that cr⁡(Q4)=8 but cr⁡(Qn) is unknown for n≥5.It was declared by Eggleton and Guy [3] that the crossing numbers of the hypercube Qn (non-2-page) for n≥3 was(1)cr⁡Qn≤5324n-n2+122n-2.Then, in 1973, Erdös and Guy [1] conjectured equality in (1). In 1993, a lower bound of cr⁡(Qn) was proved by Sýkora and Vrt’o [4]:(2)cr⁡Qn≥1204n+On22n.In 2008, Faria et al. [5] constructed a new drawing of Qn in the plane which led to the conjectured number of crossings (3)5324n-n2+122n-2.To the best of our knowledge, the fixed linear crossing number for Qn has not been established. In this paper, we discuss a method to obtain an approximation for fixed linear crossing number for hypercube graph.


## 2. 2-Page Drawings of Hypercube GraphQn

Throughout this paper, we consider the ordering of hypercube graphQn. Since Qn is defined recursively as Qn-1×K2, for n=2,…, where Q1 is a simple graph with 2 vertices together with a single edge incident to both vertices, Qn has 2 copies of Qn-1 with edges connecting between them. Given a fixed ordering on Qn-1, the vertices of the first Qn-1 are labeled 1,2,3,…,2n-1 and the vertices of the second Qn-1 are labeled 2n-1+1,2n-1+2,…,2n-1+2n-1=2n. The two vertices between the first Qn-1 and the second Qn-1 are adjacent if and only if the sum of the labeled is 2n+1. Figures 1 and 2 present the ordering of Q1,Q2,Q3 and Q4 which we consider throughout this paper. Notice that our method is independent on vertex ordering; therefore, for a fixed n, we can apply the method 2n! times so as to obtain the 2-page linear crossing number.Figure 1
n-Cube graphs with fixed vertex ordering for n=1,2,3.Figure 2
n-Cube graph with fixed vertex ordering for n=4.The 2-page drawing ofQn can be represented by drawing the vertices of Qn on a straight horizontal line L according a fixed vertex ordering. Each edge fully contained one of the two half-planes (pages) as a semicircle and never cross L. Notice that no edge crosses itself, no adjacent edges cross each other, no two edges cross more than once, and no three edges cross in a point.For a given 2-page drawing ofQn with the fixed vertex ordering, a pair of edges eij=(vi,vj) and elk=(vl,vk) are potential crossing if eij and elk cross each other when routed on the same side of L. Clearly, eij and elk are potential crossing if and only if vi<vl<vj<vk or vl<vi<vk<vj.Next we give the definition of conflict graphG′ of graph G.Definition 1.
Given a graphG. We define an associated conflict graph G′=(V′,E′) of a graph G=(V,E). There is corresponding one-to-one and onto mapping between the set of V′(G′) and E(G). Two vertices of G′ are adjacent if any two edges in G are potential crossing.For example, according to the given fixed vertex ordering ofQ3 (see Figure 3), Q3′ is a graph of n2n-1 nodes, V′(Q3′)={v12′,v23′,v34′,v45′,v56′,v67′,v78′,v14′,v36′,v58′,v27′,v18′}. v24′ and v35′ are adjacent in Q3′ because e24 and e35 are potential crossing in a 2-page drawing of Q3. A fixed vertex ordering of Q4 and its potential crossing can be seen in Figure 4.Figure 3
The 2-page drawing ofQ3 with fixed vertex ordering.Figure 4
The 2-page drawing ofQ4 with fixed vertex ordering.In this paper, we are interested only in fixed linear embeddings ofQn. There is a crossing between eij and elk if and only if eij and elk are potential crossing and embedded on the same side of L. We can see that the number of edge crossings depends on the order of vertices and on the sides to which the edges are assigned.The 2-page linear crossing number ofQn, denoted by ν2(Qn), is the minimum number of pairwise intersections of edges crossings determined by a 2-page drawing of Qn. The 2-page fixed linear crossing number of Qn is the minimum number of pairwise intersections of edges crossings determined by a 2-page drawing of Qn with fixed vertex ordering of Qn. It is known that ν2(Qn)=0 for n=1,2,3, ν2(Qn)>0 for n≥4.


## 3. Reduction to MAXCUT Problem

In this section, we show that the problem can be reduced to the maximum cut problem. Next, we reduce the fixed linear crossing number problem to the maximum cut problem (MAXCUT). The MAXCUT problem is as follows.Maximum Cut Problem (MAXCUT). Given an undirected graph G′=(V′,E′) the edge eij of the graph is associated with nonnegative weights aij. The problem is to find a cut of the largest possible weight, that is, to partition the set of V′ into disjoint sets V1 and V2 such that the total weight of all edges linking V1 and V2 (i.e., with one incident node in V1 and the other one in V2) is as large as possible.In the MAXCUT problem, we may assume that the weightsaij=aji≥0 are defined for every pair i,j of indices: it suffices to set aij=0 for pairs i,j of nonadjacent nodes. For the unweighted graph, we assume that aij=1 for i,j=1,2,…,n.LetG be a graph with a fixed vertex permutation. Given a vertex partition (V1,V2) of its conflict graph G′, the associated cut embedding is the fixed linear embedding of G where edges corresponding to V1 and V2 are embedded to the half spaces above and below the vertex line, respectively.Lemma 2 (see [6]).
(4)
ν
2
G
=
E
′
-
MC
⁡
G
′
,where |E′| is a number of potential crossing of 2-page drawing of G, which is the number of edges of G′. MC⁡(G′) is the size of the maxcut of G′.Proof.
Given a 2-page (circle) drawing ofG, define W⊂Vn as the chords that are drawn inside the circle. The edges of E′ with precisely one endpoint in W now correspond to edges of G that do not cross in the drawing.Theorem 3 (see [7]).
Consider a partition(V1,V2) of V′. Then the corresponding cut embedding is a fixed linear embedding of G with a minimum number of crossings if and only if (V1,V2) is a maximum cut in G′.Proof.
LetF′ be the set of edges in G′ with one endpoint in V1 and one endpoint in V2, that is, the cut given by (V1,V2). By definition of G′, we know that every crossing in the cut embedding associated with (V1,V2) corresponds to an edge in G′ such that either both its endpoint belong to V1 or both belong to V2, that is, to an edge in E′∖F′. Thus, the number of crossings is |E′|-|F′|. As |E′| is constant for a fixed vertex permutation, the result follows.Theorem3 reduces the fixed linear crossing number problem to the maximum cut problem (MAXCUT). In the next section, we describe the relaxation of the MAXCUT problem which leads to semidefinite programming.


### 3.1. Formulating MAXCUT by Semidefinite Relaxation

In this section, we show that 2-page crossing number of hypercube graph problem can be obtained by computing a semidefinite relaxation of MAXCUT.First of all, we introduce the adjacency matrix ofG denoted Adj⁡(G) as we know it is an n×n matrix with the property (5)Adj⁡G≡aij,aij∈0,1,aij=1,ifviandvjareadjacent;0,otherwise.FromAdj⁡(G) we construct the conflict graph of G denoted G′. Finally, we perform MAXCUT on graph G′. We use semidefinite relaxation to approximate the optimal value solution to the MAXCUT problem. Obviously the approximation is larger than the actual MAXCUT optimal value. The feasibility of the relaxation set is strictly larger than the original ones.According to [2], the MAXCUT problem can be formulated as follows:(6)max14∑i,j=1naij1-xixjs.t.xi2=1i=1,…,n.We call the optimal value of (6) as “OPT.” Then, the relaxation of (6) can be rewritten as(7)max14∑i,j=1naij1-Xijs.t.X=Xiji,j=1n=XT⪰0,Xii=1,i=1,…,n,where A=[aij] is an adjacency matrix of G′ and X=[Xij] is a feasible solution to the semidefinite relaxation. The problem (7) is equivalent to(8)min14tr⁡AXs.t.X=Xiji,j=1n=XT⪰0,Xii=1,i=1,…,n,where A is a given adjacency matrix of G′ and X=[Xij] is a feasible solution to the semidefinite relaxation. We call the optimal value of (8) as “SDP.”As we have seen from the relation (4), we let |En′| be the number of potential crossing of 2-page drawing of Qn with our fixed vertex ordering (i.e., |En′| is the number of edges of Qn′).We can determine|En′| by considering the upper half of the main diagonal of the adjacency matrix of Qn.Definition 4.
LetAG=[aij] be the n×n adjacency matrix of G. The element aij where i+j=n+1 is called minor diagonal of adjacency matrix of G and the element aij where i+j=n+1,i<j is called semiminor diagonal of adjacency matrix of G, denoted by smd⁡(AG).For simplicity, the size ofsmd⁡(AG) is a number of elements in smd⁡(AG). Let AQn be the adjacency matrix of graph Qn. Therefore AQn is 2n×2n symmetric matrix. It is clear that the size of smd⁡(AQn) is 2n-1.LetAG1 and AG2 be adjacency matrices of graphs G1 and G2, respectively; we say that the number of potential crossing between AG1 and AG2, denoted by PC[AG1,AG2], is simply the number of potential crossing between 2-page drawing of graph G1 and G2. The adjacency matrix of size 26×26 of Q6 with respect to our ordering is presented in Figure 5.Figure 5
The adjacency matrix of size26×26 of Q6.Lemma 5.
For any integern≥5,(9)PC⁡smd⁡AQn-1,smd⁡AQn=PC⁡smd⁡AQn-1,smd⁡AQn+i,where i=1,2,…,n.Lemma 6.
For every adjacency matrix ofQn, AQn, where n≥4, there exists adjacency matrix of Q3, AQ3, which is a submatrix embedding in AQn. The number of submatrix AQ3 embedding in AQn is 2n-3.Lemma 7.
For any integern≥5,(10)PC⁡AQ3,smd⁡AQn=PC⁡AQ3,smd⁡AQn+i,where i=1,2,…,n.Lemma 8.
For any integern≥5,(11)PC⁡AQn-1,smd⁡AQn=PC⁡AQn-1,smd⁡AQn+i,where i=1,2,…,n.Lemma 9.
Forn≥4, the number of block smd⁡(AQi) embedding in AQn equals 2n-i, 4≤i≤n.Lemmas5–9 follow directly from the definitions.Lemma 10.
For any integern≥4, (12)PC⁡smd⁡AQn,smd⁡AQn+1=2n-122n-2.Proof.
The number of potential crossing betweensmd⁡(AQn) and smd⁡(AQn+1) is a result of the number of potential crossing between all of the element a1,2n,a2,2n-1,…,a2n-1,2n-1+1 in AQn and smd⁡(AQn+1). That is, (13)PC⁡smd⁡AQn,smd⁡AQn+1=2n-2+2n-4+⋯+2+0=2n-122n-2.Theorem 11.
For any integern≥5,(14)En′=2En-1′+2n+1+2∑k=5n2n-k2k4-12k4,E4′=40,where |En′| is the number of potential crossing of 2-page drawing of Qn with our fixed vertex ordering.Proof.
We prove this lemma by considering the number of potential crossing of 2-page drawing ofQn with our fixed vertex ordering. Since Qn has 2 copies of Qn-1 with some edges connecting between them, the number of potential crossing of AQn is a result of twice of the number of potential crossing within AQn-1 together with PC⁡[AQ3,smd⁡(AQn)] and PC⁡[smd⁡(AQi),smd⁡(AQn)],i=4,5,…,n-1.
Hence, it is enough to show that the number of potential crossing between 2-page drawing ofQn-1 and Qn-1 is equal to γ(n), where(15)γn=2n+1+2∑k=5n2n-k2k4-12k4.
Noteγ(n) is the number of potential crossing between all of submatrices AQ3 and smd⁡(AQn) and also between smd⁡(AQi) and smd⁡(AQn),i=4,5,…,n-1. By Lemmas 6 and 9,(16)γn=2n-3·PC⁡AQ3,smd⁡AQn+2n-4·PC⁡smd⁡AQ4,smd⁡AQn+2n-5·PC⁡smd⁡AQ5,smd⁡AQn+⋯+2n-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+2n-n-1·PC⁡smd⁡AQn-1,smd⁡AQn.
We precede by mathematical induction onn. For n=5, it can be easily seen that γ(5)=176 by counting. Assuming (15) holds true, now we consider γ(n+1) as a number of potential crossing between all of the submatrices AQ3 and smd⁡(AQn+1) and also between smd⁡(AQi) and smd⁡(AQn+1),i=4,5,…,n. By the Lemmas 5, 6, 7, 9, 8, and 10,(17)γn+1=2n+1-3·PC⁡AQ3,smd⁡AQn+1+2n+1-4·PC⁡smd⁡AQ4,smd⁡AQn+1+2n+1-5·PC⁡smd⁡AQ5,smd⁡AQn+1+⋯+2n+1-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+1+2n+1-n-1·PC⁡smd⁡AQn-1,smd⁡AQn+1+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=22n-3·PC⁡AQ3,smd⁡AQn+2n-4·PC⁡smd⁡AQ4,smd⁡AQn+2n-5·PC⁡smd⁡AQ5,smd⁡AQn+⋯+2n-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+2n-n-1·PC⁡smd⁡AQn-1,smd⁡AQn+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=2γn+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=2γn+2n+1-n·2n-122n-2=2γn+22n-12n-1-1=2γn+22n+14-12n+14=22n+1+2∑k=5n2n-k2k4-12k4+22n+14-12n+14=2·2n+1+2·∑k=5n2n+1-k2k4-12k4+22n+14-12n+14=2n+1+1+2∑k=5n2n+1-k2k4-12k4+2n+1-n+12n+14-12n+14=2n+1+1+2∑k=5n+12n+1-k2k4-12k4.The next theorem shows how effective the relaxation is.Theorem 12 (see [8]).
Let OPT be the optimal value of the MAXCUT problem and SDP be the optimal value of the semidefinite relaxation. Then(18)1≥OPTSDP≥0.87856⋯Theorem12 guarantees that the optimal value of the MAXCUT is close to the optimal value of the semidefinite relaxation. From (4), we have(19)AP⁡ν2Qn=En′-AP⁡MC⁡Qn′,where |En′| is a number of potential crossing of 2-page drawing of Qn. AP⁡(ν2(Qn)) is an approximation of 2-page fixed linear crossing number of Qn and AP⁡(MC⁡(Qn′)) is an approximation of MC(Qn′).Corollary 13.
LetAP⁡(ν2(Qn)) be an approximation of ν2(Qn). Then we have(20)AP⁡ν2Qn≤ν2Qn≤knAP⁡ν2Qn,where k(n) is a computable quantity depending on n.Proof.
From (4), (18), and (19), we have (21)ν2QnAP⁡ν2Qn=En′-MC⁡Qn′En′-AP⁡MC⁡Qn′≤En′-0.87856AP⁡MC⁡Qn′En′-AP⁡MC⁡Qn′.
Letk(n)=|En′|-0.87856AP⁡(MC⁡(Qn′))/|En′|-AP⁡(MC⁡(Qn′)) be the computable quantity depending on n.
Then,(22)ν2QnAP⁡ν2Qn≤knν2Qn≤kn·AP⁡ν2Qn.Corollary13 shows that the upper bound of ν2(Qn) is k(n)·AP⁡(ν2(Qn)), where k(n) is the computable quantity depending on n.


### 3.2. Experimental Results

In this section, we consider the hypercube graphQn for n=4,5,6. Then, we give some examples for approximating the problems of the semidefinite relaxation in the form (8). We approximate this problem via MATLAB program together with an optimization toolbox called “SeDuMi.” The SeDuMi is a package for solving optimization problems with linear, quadratic, and semidefinite constraints.In Table1, the second column shows numerical results for the approximation of the MAXCUT on the associated conflict graph Qn′ by using the semidefinite relaxation. It is well known that this problem can be solved in a polynomial time. The third column displays the numbers of potential crossing of 2-page drawing of Qn referring to our fixed vertex ordering that we evaluate from (14). Notice that this potential crossing of 2-page drawing of Qn is the exact value. From (19), we calculate the approximation of 2-page fixed linear crossing number of Qn for n=4,5,6. The results are shown in the last column.Table 1
The numerical results of the approximation of 2-page fixed linear crossing number ofQn, AP(ν2(Qn)) for n=4,5,6.
n
A
P
(
M
C
(
Q
n
′
)
)
|
E
n
′
|
A
P
(
ν
2
(
Q
n
)
)
4
35
40
5
5
207
256
48
6
1034
1344
310In Table2, we present the lower bound of ν2(Qn), AP⁡ν2(Qn) and the upper bound of ν2(Qn), k(n)AP(ν2(G)). The second column shows the values of k(n) for n=4,5,6. We see that as n get larger the values of k(n) tend to decline continuously. It is interesting to study the behavior of k(n) as n→∞. It does not surprise to see that our approximation is strictly larger than the upper bound of cr⁡(Qn) (14) since the latter one does not have a restriction that all vertices must be placed on a line. However, it is surprising to see that these numbers are not so different from each other.Table 2
The computable quantityk(n), the bound of ν2(Qn), and the upper bound of cr⁡(Qn) for n=4,5,6.
n
k
(
n
)
A
P
(
ν
2
(
Q
n
)
)
k
(
n
)
A
P
(
ν
2
(
G
)
)
Upper bound ofcr⁡(Qn)
4
1.91
5
9.55
8
5
1.55
48
74.36
56
6
1.43
310
444.42
352


## 3.1. Formulating MAXCUT by Semidefinite Relaxation

In this section, we show that 2-page crossing number of hypercube graph problem can be obtained by computing a semidefinite relaxation of MAXCUT.First of all, we introduce the adjacency matrix ofG denoted Adj⁡(G) as we know it is an n×n matrix with the property (5)Adj⁡G≡aij,aij∈0,1,aij=1,ifviandvjareadjacent;0,otherwise.FromAdj⁡(G) we construct the conflict graph of G denoted G′. Finally, we perform MAXCUT on graph G′. We use semidefinite relaxation to approximate the optimal value solution to the MAXCUT problem. Obviously the approximation is larger than the actual MAXCUT optimal value. The feasibility of the relaxation set is strictly larger than the original ones.According to [2], the MAXCUT problem can be formulated as follows:(6)max14∑i,j=1naij1-xixjs.t.xi2=1i=1,…,n.We call the optimal value of (6) as “OPT.” Then, the relaxation of (6) can be rewritten as(7)max14∑i,j=1naij1-Xijs.t.X=Xiji,j=1n=XT⪰0,Xii=1,i=1,…,n,where A=[aij] is an adjacency matrix of G′ and X=[Xij] is a feasible solution to the semidefinite relaxation. The problem (7) is equivalent to(8)min14tr⁡AXs.t.X=Xiji,j=1n=XT⪰0,Xii=1,i=1,…,n,where A is a given adjacency matrix of G′ and X=[Xij] is a feasible solution to the semidefinite relaxation. We call the optimal value of (8) as “SDP.”As we have seen from the relation (4), we let |En′| be the number of potential crossing of 2-page drawing of Qn with our fixed vertex ordering (i.e., |En′| is the number of edges of Qn′).We can determine|En′| by considering the upper half of the main diagonal of the adjacency matrix of Qn.Definition 4.
LetAG=[aij] be the n×n adjacency matrix of G. The element aij where i+j=n+1 is called minor diagonal of adjacency matrix of G and the element aij where i+j=n+1,i<j is called semiminor diagonal of adjacency matrix of G, denoted by smd⁡(AG).For simplicity, the size ofsmd⁡(AG) is a number of elements in smd⁡(AG). Let AQn be the adjacency matrix of graph Qn. Therefore AQn is 2n×2n symmetric matrix. It is clear that the size of smd⁡(AQn) is 2n-1.LetAG1 and AG2 be adjacency matrices of graphs G1 and G2, respectively; we say that the number of potential crossing between AG1 and AG2, denoted by PC[AG1,AG2], is simply the number of potential crossing between 2-page drawing of graph G1 and G2. The adjacency matrix of size 26×26 of Q6 with respect to our ordering is presented in Figure 5.Figure 5
The adjacency matrix of size26×26 of Q6.Lemma 5.
For any integern≥5,(9)PC⁡smd⁡AQn-1,smd⁡AQn=PC⁡smd⁡AQn-1,smd⁡AQn+i,where i=1,2,…,n.Lemma 6.
For every adjacency matrix ofQn, AQn, where n≥4, there exists adjacency matrix of Q3, AQ3, which is a submatrix embedding in AQn. The number of submatrix AQ3 embedding in AQn is 2n-3.Lemma 7.
For any integern≥5,(10)PC⁡AQ3,smd⁡AQn=PC⁡AQ3,smd⁡AQn+i,where i=1,2,…,n.Lemma 8.
For any integern≥5,(11)PC⁡AQn-1,smd⁡AQn=PC⁡AQn-1,smd⁡AQn+i,where i=1,2,…,n.Lemma 9.
Forn≥4, the number of block smd⁡(AQi) embedding in AQn equals 2n-i, 4≤i≤n.Lemmas5–9 follow directly from the definitions.Lemma 10.
For any integern≥4, (12)PC⁡smd⁡AQn,smd⁡AQn+1=2n-122n-2.Proof.
The number of potential crossing betweensmd⁡(AQn) and smd⁡(AQn+1) is a result of the number of potential crossing between all of the element a1,2n,a2,2n-1,…,a2n-1,2n-1+1 in AQn and smd⁡(AQn+1). That is, (13)PC⁡smd⁡AQn,smd⁡AQn+1=2n-2+2n-4+⋯+2+0=2n-122n-2.Theorem 11.
For any integern≥5,(14)En′=2En-1′+2n+1+2∑k=5n2n-k2k4-12k4,E4′=40,where |En′| is the number of potential crossing of 2-page drawing of Qn with our fixed vertex ordering.Proof.
We prove this lemma by considering the number of potential crossing of 2-page drawing ofQn with our fixed vertex ordering. Since Qn has 2 copies of Qn-1 with some edges connecting between them, the number of potential crossing of AQn is a result of twice of the number of potential crossing within AQn-1 together with PC⁡[AQ3,smd⁡(AQn)] and PC⁡[smd⁡(AQi),smd⁡(AQn)],i=4,5,…,n-1.
Hence, it is enough to show that the number of potential crossing between 2-page drawing ofQn-1 and Qn-1 is equal to γ(n), where(15)γn=2n+1+2∑k=5n2n-k2k4-12k4.
Noteγ(n) is the number of potential crossing between all of submatrices AQ3 and smd⁡(AQn) and also between smd⁡(AQi) and smd⁡(AQn),i=4,5,…,n-1. By Lemmas 6 and 9,(16)γn=2n-3·PC⁡AQ3,smd⁡AQn+2n-4·PC⁡smd⁡AQ4,smd⁡AQn+2n-5·PC⁡smd⁡AQ5,smd⁡AQn+⋯+2n-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+2n-n-1·PC⁡smd⁡AQn-1,smd⁡AQn.
We precede by mathematical induction onn. For n=5, it can be easily seen that γ(5)=176 by counting. Assuming (15) holds true, now we consider γ(n+1) as a number of potential crossing between all of the submatrices AQ3 and smd⁡(AQn+1) and also between smd⁡(AQi) and smd⁡(AQn+1),i=4,5,…,n. By the Lemmas 5, 6, 7, 9, 8, and 10,(17)γn+1=2n+1-3·PC⁡AQ3,smd⁡AQn+1+2n+1-4·PC⁡smd⁡AQ4,smd⁡AQn+1+2n+1-5·PC⁡smd⁡AQ5,smd⁡AQn+1+⋯+2n+1-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+1+2n+1-n-1·PC⁡smd⁡AQn-1,smd⁡AQn+1+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=22n-3·PC⁡AQ3,smd⁡AQn+2n-4·PC⁡smd⁡AQ4,smd⁡AQn+2n-5·PC⁡smd⁡AQ5,smd⁡AQn+⋯+2n-n-2·PC⁡smd⁡AQn-2,smd⁡AQn+2n-n-1·PC⁡smd⁡AQn-1,smd⁡AQn+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=2γn+2n+1-n·PC⁡smd⁡AQn,smd⁡AQn+1=2γn+2n+1-n·2n-122n-2=2γn+22n-12n-1-1=2γn+22n+14-12n+14=22n+1+2∑k=5n2n-k2k4-12k4+22n+14-12n+14=2·2n+1+2·∑k=5n2n+1-k2k4-12k4+22n+14-12n+14=2n+1+1+2∑k=5n2n+1-k2k4-12k4+2n+1-n+12n+14-12n+14=2n+1+1+2∑k=5n+12n+1-k2k4-12k4.The next theorem shows how effective the relaxation is.Theorem 12 (see [8]).
Let OPT be the optimal value of the MAXCUT problem and SDP be the optimal value of the semidefinite relaxation. Then(18)1≥OPTSDP≥0.87856⋯Theorem12 guarantees that the optimal value of the MAXCUT is close to the optimal value of the semidefinite relaxation. From (4), we have(19)AP⁡ν2Qn=En′-AP⁡MC⁡Qn′,where |En′| is a number of potential crossing of 2-page drawing of Qn. AP⁡(ν2(Qn)) is an approximation of 2-page fixed linear crossing number of Qn and AP⁡(MC⁡(Qn′)) is an approximation of MC(Qn′).Corollary 13.
LetAP⁡(ν2(Qn)) be an approximation of ν2(Qn). Then we have(20)AP⁡ν2Qn≤ν2Qn≤knAP⁡ν2Qn,where k(n) is a computable quantity depending on n.Proof.
From (4), (18), and (19), we have (21)ν2QnAP⁡ν2Qn=En′-MC⁡Qn′En′-AP⁡MC⁡Qn′≤En′-0.87856AP⁡MC⁡Qn′En′-AP⁡MC⁡Qn′.
Letk(n)=|En′|-0.87856AP⁡(MC⁡(Qn′))/|En′|-AP⁡(MC⁡(Qn′)) be the computable quantity depending on n.
Then,(22)ν2QnAP⁡ν2Qn≤knν2Qn≤kn·AP⁡ν2Qn.Corollary13 shows that the upper bound of ν2(Qn) is k(n)·AP⁡(ν2(Qn)), where k(n) is the computable quantity depending on n.


## 3.2. Experimental Results

In this section, we consider the hypercube graphQn for n=4,5,6. Then, we give some examples for approximating the problems of the semidefinite relaxation in the form (8). We approximate this problem via MATLAB program together with an optimization toolbox called “SeDuMi.” The SeDuMi is a package for solving optimization problems with linear, quadratic, and semidefinite constraints.In Table1, the second column shows numerical results for the approximation of the MAXCUT on the associated conflict graph Qn′ by using the semidefinite relaxation. It is well known that this problem can be solved in a polynomial time. The third column displays the numbers of potential crossing of 2-page drawing of Qn referring to our fixed vertex ordering that we evaluate from (14). Notice that this potential crossing of 2-page drawing of Qn is the exact value. From (19), we calculate the approximation of 2-page fixed linear crossing number of Qn for n=4,5,6. The results are shown in the last column.Table 1
The numerical results of the approximation of 2-page fixed linear crossing number ofQn, AP(ν2(Qn)) for n=4,5,6.
n
A
P
(
M
C
(
Q
n
′
)
)
|
E
n
′
|
A
P
(
ν
2
(
Q
n
)
)
4
35
40
5
5
207
256
48
6
1034
1344
310In Table2, we present the lower bound of ν2(Qn), AP⁡ν2(Qn) and the upper bound of ν2(Qn), k(n)AP(ν2(G)). The second column shows the values of k(n) for n=4,5,6. We see that as n get larger the values of k(n) tend to decline continuously. It is interesting to study the behavior of k(n) as n→∞. It does not surprise to see that our approximation is strictly larger than the upper bound of cr⁡(Qn) (14) since the latter one does not have a restriction that all vertices must be placed on a line. However, it is surprising to see that these numbers are not so different from each other.Table 2
The computable quantityk(n), the bound of ν2(Qn), and the upper bound of cr⁡(Qn) for n=4,5,6.
n
k
(
n
)
A
P
(
ν
2
(
Q
n
)
)
k
(
n
)
A
P
(
ν
2
(
G
)
)
Upper bound ofcr⁡(Qn)
4
1.91
5
9.55
8
5
1.55
48
74.36
56
6
1.43
310
444.42
352


## 4. Concluding Remarks

In this paper, given graphG, we show how the associating conflict graph G′ is constructed. We recharacterize the problem of finding the crossing number of graph G to the MAXCUT problem of G′. We approximate the MAXCUT problem by the semidefinite relaxation which can be solved easily by a standard optimization package; in this case, we use SeDuMi 1.02. The numerical results show reasonable outcome. Clearly, another relaxation method can be explored. Moreover, it would be quite interesting to see the behavior of k(n) as n get larger. One can further study how to estimate k(n) for a larger n.



---

*Source: 7640347-2017-05-08.xml*