Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation (Q670454)

Summary: The crossing number of graph \(G\) 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.