Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation
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.
- An improved upper bound on the crossing number of the hypercube
- Crossing Number is NP-Complete
- Crossing Number Problems
- Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
- Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- On crossing numbers of hypercubes and cube connected cycles
This page was built for publication: Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670454)
