Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation
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 s...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2017/7640347 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832558736164519936 |
|---|---|
| author | A. Suebsriwichai T. Mouktonglang |
| author_facet | A. Suebsriwichai T. Mouktonglang |
| author_sort | A. Suebsriwichai |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-823ede38fa324cecbdae0d1803ca90fd |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-823ede38fa324cecbdae0d1803ca90fd2025-02-03T01:31:39ZengWileyJournal of Applied Mathematics1110-757X1687-00422017-01-01201710.1155/2017/76403477640347Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP RelaxationA. Suebsriwichai0T. Mouktonglang1Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, ThailandDepartment of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, ThailandThe 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.http://dx.doi.org/10.1155/2017/7640347 |
| spellingShingle | A. Suebsriwichai T. Mouktonglang Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation Journal of Applied Mathematics |
| title | Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation |
| title_full | Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation |
| title_fullStr | Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation |
| title_full_unstemmed | Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation |
| title_short | Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation |
| title_sort | bound for the 2 page fixed linear crossing number of hypercube graph via sdp relaxation |
| url | http://dx.doi.org/10.1155/2017/7640347 |
| work_keys_str_mv | AT asuebsriwichai boundforthe2pagefixedlinearcrossingnumberofhypercubegraphviasdprelaxation AT tmouktonglang boundforthe2pagefixedlinearcrossingnumberofhypercubegraphviasdprelaxation |