{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:46Z","timestamp":1750307806997,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,6,9]],"date-time":"2008-06-09T00:00:00Z","timestamp":1212969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2008,6,9]]},"DOI":"10.1145\/1377676.1377739","type":"proceedings-article","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T14:13:22Z","timestamp":1213107202000},"page":"375-384","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved upper bounds on the crossing number"],"prefix":"10.1145","author":[{"given":"Vida","family":"Dujmovic","sequence":"first","affiliation":[{"name":"Carleton University, Ottawa, Canada"}]},{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[{"name":"Universitat Politecnica de Catalunya, Barcelona, Spain"}]}],"member":"320","published-online":{"date-parts":[[2008,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.05.001"},{"key":"e_1_3_2_1_2_1","series-title":"North-Holland Math","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume-title":"Theory and practice of combinatorics","author":"Ajtai Mikl\u00f3s","year":"1982","unstructured":"Mikl\u00f3s Ajtai , Va\u0161ek Chv\u00e1tal , Monroe M. Newborn , and Endre Szemer\u00e9di . Crossing-free subgraphs . In Theory and practice of combinatorics , vol. 60 of North-Holland Math . Stud., pp. 9 -- 12 . North-Holland , 1982 . Mikl\u00f3s Ajtai, Va\u0161ek Chv\u00e1tal, Monroe M. Newborn, and Endre Szemer\u00e9di. Crossing-free subgraphs. In Theory and practice of combinatorics, vol. 60 of North-Holland Math. Stud., pp. 9--12. North-Holland, 1982."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.003"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2007.01.024"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/05062706X"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.37236\/728"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004236"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700003300"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.14"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00236-6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.010"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00069"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_37"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1973.11993230"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200103)36:3%26lt;%26gt;1.0.CO;2-S"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0604033"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2003.07.007"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v47:1"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00037-6"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.09.009"},{"key":"e_1_3_2_1_23_1","first-page":"192","volume-title":"Combinatorics and Applications","author":"Robert","year":"1984","unstructured":"Robert E. Jamison and Renu Laskar. Elimination orderings of chordal graphs . In Combinatorics and Applications , pp. 192 -- 200 . Indian Statist. Inst. , 1984 . Robert E. Jamison and Renu Laskar. Elimination orderings of chordal graphs. In Combinatorics and Applications, pp. 192--200. Indian Statist. Inst., 1984."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-006-0684-x"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_3_2_1_26_1","volume-title":"Complexity Issues in VLSI","author":"Leighton F. Thomson","year":"1983","unstructured":"F. Thomson Leighton . Complexity Issues in VLSI . MIT Press , 1983 . F. Thomson Leighton. Complexity Issues in VLSI. MIT Press, 1983."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744433"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on surfaces","author":"Mohar Bojan","year":"2001","unstructured":"Bojan Mohar and Carsten Thomassen . Graphs on surfaces . Johns Hopkins University Press , 2001 . Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Press, 2001."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.37236\/1748"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200101)36:1%26lt;%26gt;1.0.CO;2-#"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086610"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003192"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1978"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_30"},{"key":"e_1_3_2_1_35_1","first-page":"3","volume-title":"Proc. 15th Int. Symp. on Graph Drawing (GD '07)","volume":"4875","author":"Pelsmajer Michael J.","year":"2007","unstructured":"Michael J. Pelsmajer , Marcus Schaefer , and Daniel Stefankovic . Crossing number of graphs with rotation systems. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors , Proc. 15th Int. Symp. on Graph Drawing (GD '07) , vol. 4875 of Lecture Notes in Comput. Sci. , pp. 3 -- 12 , 2007 . Michael J. Pelsmajer, Marcus Schaefer, and Daniel Stefankovic. Crossing number of graphs with rotation systems. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proc. 15th Int. Symp. on Graph Drawing (GD '07), vol. 4875 of Lecture Notes in Comput. Sci., pp. 3--12, 2007."},{"key":"e_1_3_2_1_36_1","first-page":"248","volume-title":"Proc. 5th Int. Symp. on Graph Drawing (GD '97)","volume":"1353","author":"Purchase Helen C.","year":"1997","unstructured":"Helen C. Purchase . Which aesthetic has the greatest effect on human understanding? In Giuseppe Di Battista, editor , Proc. 5th Int. Symp. on Graph Drawing (GD '97) , vol. 1353 of Lecture Notes in Comput. Sci. , pp. 248 -- 261 , 1997 . Helen C. Purchase. Which aesthetic has the greatest effect on human understanding? In Giuseppe Di Battista, editor, Proc. 5th Int. Symp. on Graph Drawing (GD '97), vol. 1353 of Lecture Notes in Comput. Sci., pp. 248--261, 1997."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1998.0093"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264222"},{"key":"e_1_3_2_1_39_1","first-page":"85","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"Reed Bruce A.","year":"2003","unstructured":"Bruce A. Reed . Algorithmic aspects of tree width. In Bruce A. Reed and Cl\u00e1udia L. Sales, editors , Recent Advances in Algorithms and Combinatorics , pp. 85 -- 107 , 2003 . Bruce A. Reed. Algorithmic aspects of tree width. In Bruce A. Reed and Cl\u00e1udia L. Sales, editors, Recent Advances in Algorithms and Combinatorics, pp. 85--107, 2003."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199601)21:1%3C51::AID-JGT7%3E3.0.CO;2-L"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574034"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1997.11990611"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1996.0069"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001383"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086611"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397002976"},{"key":"e_1_3_2_1_50_1","volume-title":"A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1{3):331--352","author":"Sz\u00e9kely L\u00e1szl\u00f3 A.","year":"2004","unstructured":"L\u00e1szl\u00f3 A. Sz\u00e9kely . A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1{3):331--352 , 2004 . L\u00e1szl\u00f3 A. Sz\u00e9kely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1{3):331--352, 2004."},{"key":"e_1_3_2_1_51_1","volume-title":"Crossing numbers of graphs: A bibliography","author":"Vrt'o Imrich","year":"2007","unstructured":"Imrich Vrt'o . Crossing numbers of graphs: A bibliography , 2007 . ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf. Imrich Vrt'o. Crossing numbers of graphs: A bibliography, 2007. ftp:\/\/ftp.ifi.savba.sk\/pub\/imrich\/crobib.pdf."},{"key":"e_1_3_2_1_52_1","first-page":"117","article-title":"Planar decompositions and the crossing number of graphs with an excluded minor","volume":"13","author":"Wood David R.","year":"2007","unstructured":"David R. Wood and Jan Arne Telle . Planar decompositions and the crossing number of graphs with an excluded minor . New York J. Math. , 13 : 117 -- 146 , 2007 . David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor. New York J. Math., 13:117--146, 2007.","journal-title":"New York J. Math."}],"event":{"name":"SoCG08: 24th Annual Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"College Park MD USA","acronym":"SoCG08"},"container-title":["Proceedings of the twenty-fourth annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377739","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1377676.1377739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:39Z","timestamp":1750254999000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1377676.1377739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,9]]},"references-count":52,"alternative-id":["10.1145\/1377676.1377739","10.1145\/1377676"],"URL":"https:\/\/doi.org\/10.1145\/1377676.1377739","relation":{},"subject":[],"published":{"date-parts":[[2008,6,9]]},"assertion":[{"value":"2008-06-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}