{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:55Z","timestamp":1771036375837,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            The crossing number of a graph\n            <jats:italic>G<\/jats:italic>\n            is the smallest number of edge crossings in any drawing of\n            <jats:italic>G<\/jats:italic>\n            into the plane. Recently, the first branch-and-cut approach for solving the crossing number problem has been presented in Buchheim et al. [2005]. Its major drawback was the huge number of variables out of which only very few were actually used in the optimal solution. This restricted the algorithm to rather small graphs with low crossing number.\n          <\/jats:p>\n          <jats:p>In this article, we discuss two column generation schemes; the first is based on traditional algebraic pricing, and the second uses combinatorial arguments to decide whether and which variables need to be added. The main focus of this article is the experimental comparison between the original approach and these two schemes. In addition, we evaluate the quality achieved by the best-known crossing number heuristic by comparing the new results with the results of the heuristic.<\/jats:p>","DOI":"10.1145\/1498698.1564504","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":4,"title":["Experiments on exact crossing minimization using column generation"],"prefix":"10.1145","volume":"14","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"TU Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Gutwenger","sequence":"additional","affiliation":[{"name":"TU Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"TU Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(84)90006-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.05.006"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222068"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0920"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.1.101"},{"key":"e_1_2_1_8_1","unstructured":"Di Battista G. Eades P. Tamassia R. and Tollis I. 1999. Graph Drawing. Prentice Hall Upper Saddle River NJ.  Di Battista G. Eades P. Tamassia R. and Tollis I. 1999. Graph Drawing. Prentice Hall Upper Saddle River NJ."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00005-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672876"},{"key":"e_1_2_1_11_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_21"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 11th Symposium on Graph Drawing","author":"Gutwenger C.","year":"2003","unstructured":"Gutwenger , C. and Mutzel , P . 2004. An experimental study of crossing minimization heuristics . In Proceedings of the 11th Symposium on Graph Drawing 2003 . Springer-Verlag, Berlin,13--24. Gutwenger, C. and Mutzel, P. 2004. An experimental study of crossing minimization heuristics. In Proceedings of the 11th Symposium on Graph Drawing 2003. Springer-Verlag, Berlin,13--24."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1128-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_80"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.21845"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.709399"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086607"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11%3C1325::AID-SPE342%3E3.0.CO;2-T"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90091-W"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing. ACM","author":"Liu P.","unstructured":"Liu , P. and Geldmacher , R . 1977. On the deletion of nonplanar edges of a graph . In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing. ACM , New York, 727--738. Liu, P. and Geldmacher, R. 1977. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory, and Computing. ACM, New York, 727--738."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Graph Drawing '99","volume":"1731","author":"Mutzel P.","unstructured":"Mutzel , P. and Ziegler , T . 1999. The constrained crossing minimization problem . In Proceedings of the Graph Drawing '99 , J. Kratochvil, Ed. LNCS , vol. 1731 . Springer-Verlag, Berlin, 175--185. Mutzel, P. and Ziegler, T. 1999. The constrained crossing minimization problem. In Proceedings of the Graph Drawing '99, J. Kratochvil, Ed. LNCS, vol. 1731. Springer-Verlag, Berlin, 175--185."},{"key":"e_1_2_1_23_1","unstructured":"OGDF 2006. OGDF -- Open Graph Drawing Framework. www.ogdf.net.  OGDF 2006. OGDF -- Open Graph Drawing Framework. www.ogdf.net."},{"key":"e_1_2_1_24_1","volume-title":"Which aesthetic has the greatest effect on human understanding&amp;quest","author":"Purchase H. C.","unstructured":"Purchase , H. C. 1997. Which aesthetic has the greatest effect on human understanding&amp;quest ; In Proceedings of the 5th Annual Symposium on Graph Drawing '97 Springer-Verlag , Berlin, 248--261. Purchase, H. C. 1997. Which aesthetic has the greatest effect on human understanding&amp;quest; In Proceedings of the 5th Annual Symposium on Graph Drawing '97 Springer-Verlag, Berlin, 248--261."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010105"},{"key":"e_1_2_1_26_1","unstructured":"Vrto I. 2006. Crossing numbers of graphs: A bibliography. ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf.  Vrto I. 2006. Crossing numbers of graphs: A bibliography. ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.322451"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1564504","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1564504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1564504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":26,"alternative-id":["10.1145\/1498698.1564504"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1564504","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}