{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T01:48:02Z","timestamp":1774489682942,"version":"3.50.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030044138","type":"print"},{"value":"9783030044145","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04414-5_18","type":"book-chapter","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T18:20:45Z","timestamp":1545070845000},"page":"255-268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Crossing Numbers and Stress of Random Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanna","family":"D\u00f6ring","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Reitzner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00856-6","volume-title":"Proofs from THE BOOK","author":"M Aigner","year":"2009","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from THE BOOK, 4th edn. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00856-6","edition":"4"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume-title":"Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday","author":"M. Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Theory and Practice of Combinatorics, North-Holland Mathematics Studies, North-Holland, vol. 60, pp. 9\u201312 (1982)"},{"key":"18_CR3","unstructured":"Biedl, T.C., Chimani, M., Derka, M., Mutzel, P.: Crossing number for graphs with bounded pathwidth. In: Proceedings of International Symposium on Algorithms and Computation (ISAAC) 2017, pp. 13:1\u201313:13. LIPIcs 92 (2017)"},{"issue":"5","key":"18_CR4","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/BF02574701","volume":"6","author":"D Bienstock","year":"1991","unstructured":"Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6(5), 443\u2013459 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-00219-9_21","volume-title":"Graph Drawing","author":"U Brandes","year":"2009","unstructured":"Brandes, U., Pich, C.: An experimental study on distance-based graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218\u2013229. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00219-9_21"},{"issue":"2","key":"18_CR6","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s00454-012-9440-6","volume":"49","author":"S Cabello","year":"2013","unstructured":"Cabello, S.: Hardness of approximation for crossing number. Discrete Comput. Geom. 49(2), 348\u2013358 (2013)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"18_CR7","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/s00453-009-9357-5","volume":"60","author":"S Cabello","year":"2011","unstructured":"Cabello, S., Mohar, B.: Crossing number and weighted crossing number of near-planar graphs. Algorithmica 60(3), 484\u2013504 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9357-5","journal-title":"Algorithmica"},{"key":"18_CR8","unstructured":"Chimani, M., et al.: People prefer less stress and fewer crossings. In: Duncan, C., Symvonis, A. (eds.) Proceedings of International Symposium on Graph Drawing (GD) 2014. LNCS, vol. 8871, pp. 523\u2013524. Springer, Heidelberg (2014)"},{"key":"18_CR9","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: Inserting multiple edges into a planar graph. In: Proceedings of International SYmposium on Computational Geometry (SoCG) 2016, pp. 30:1\u201330:15. LIPIcs 51 (2016)"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/j.ejc.2011.09.009","volume":"33","author":"M Chimani","year":"2012","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P., Mutzel, P.: Vertex insertion approximates the crossing number for apex graphs. Eur. J. Comb. 33, 326\u2013335 (2012)","journal-title":"Eur. J. Comb."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Chimani, M., D\u00f6ring, H., Reitzner, M.: Crossing numbers and stress of random graphs. eprint arXiv:1808.07558v1 (2018)","DOI":"10.1007\/978-3-030-04414-5_18"},{"issue":"4","key":"18_CR12","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1007\/s10878-016-0030-z","volume":"33","author":"M Chimani","year":"2017","unstructured":"Chimani, M., Hlin\u011bn\u00fd, P.: A tighter insertion-based approximation of the crossing number. J. Comb. Optim. 33(4), 1183\u20131225 (2017)","journal-title":"J. Comb. Optim."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: An algorithm for the graph crossing number problem. In: Proceedings of ACM Symposium on Theory of Computing (STOC) 2011, pp. 303\u2013312. ACM (2011)","DOI":"10.1145\/1993636.1993678"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-319-50106-2_32","volume-title":"Graph Drawing and Network Visualization","author":"J Fox","year":"2016","unstructured":"Fox, J., Pach, J., Suk, A.: Approximating the Rectilinear crossing number. In: Hu, Y., N\u00f6llenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 413\u2013426. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-50106-2_32"},{"issue":"3","key":"18_CR15","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebr. Discrete Methods 4(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"18_CR16","first-page":"219","volume":"29","author":"I Gitler","year":"2007","unstructured":"Gitler, I., Hlin\u011bn\u00fd, P., Lea\u00f1o, J., Salazar, G.: The crossing number of a projective graph is quadratic in the face-width. Electron. J. Comb. 29, 219\u2013233 (2007)","journal-title":"Electron. J. Comb."},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1137\/1.9781611973075.74","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Petr Hlin\u011bn\u00fd","year":"2010","unstructured":"Hlin\u011bn\u00fd, P., Chimani, M.: Approximating the crossing number of graphs embeddable in any orientable surface. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA) 2010, pp. 918\u2013927 (2010)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-540-77120-3_15","volume-title":"Algorithms and Computation","author":"P Hlin\u011bn\u00fd","year":"2007","unstructured":"Hlin\u011bn\u00fd, P., Salazar, G.: Approximating the crossing number of toroidal graphs. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 148\u2013159. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-77120-3_15"},{"issue":"1","key":"18_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0895480104442741","volume":"20","author":"E de Klerk","year":"2006","unstructured":"de Klerk, E., Maharry, J., Pasechnik, D.V., Richter, R.B., Salazar, G.: Improved bounds for the crossing numbers of $$K_{m, n}$$ and $$K_n$$. SIAM J. Discrete Math. 20(1), 189\u2013202 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36763-2_6","volume-title":"Graph Drawing","author":"M Klimenta","year":"2013","unstructured":"Klimenta, M., Brandes, U.: Graph drawing by classical multidimensional scaling: new perspectives. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 55\u201366. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36763-2_6"},{"key":"18_CR21","unstructured":"Kobourov, S.G.: Force-directed drawing algorithms. In: Handbook of Graph Drawing and Visualization, pp. 383\u2013408. CRC Press (2013)"},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-662-45803-7_20","volume-title":"Graph Drawing","author":"SG Kobourov","year":"2014","unstructured":"Kobourov, S.G., Pupyrev, S., Saket, B.: Are crossings important for drawing large graphs? In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 234\u2013245. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_20"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s00440-010-0288-5","volume":"150","author":"G Last","year":"2011","unstructured":"Last, G., Penrose, M.: Fock space representation, chaos expansion and covariance, inequalities for general Poisson processes. Probab. Theory Relat. Fields 150, 663\u2013690 (2011)","journal-title":"Probab. Theory Relat. Fields"},{"key":"18_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/9781316104477","volume-title":"Lectures on the Poisson Process","author":"G Last","year":"2017","unstructured":"Last, G., Penrose, M.: Lectures on the Poisson Process. Cambridge University Press, Cambridge (2017)"},{"key":"18_CR25","volume-title":"Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks","author":"FT Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge (1983)"},{"key":"18_CR26","series-title":"Bocconi & Springer Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05233-5","volume-title":"Stochastic Analysis for Poisson Point Processes: Malliavin Calculus, Wiener-It\u00f4 Chaos Expansions and Stochastic Geometry","year":"2016","unstructured":"Peccati, G., Reitzner, M. (eds.): Stochastic Analysis for Poisson Point Processes: Malliavin Calculus, Wiener-It\u00f4 Chaos Expansions and Stochastic Geometry. Bocconi & Springer Series, vol. 7. Springer, Switzerland (2016). https:\/\/doi.org\/10.1007\/978-3-319-05233-5. Bocconi University Press, Milan"},{"key":"18_CR27","volume-title":"Random Geometric Graphs (Oxford Studies in Probability)","author":"M Penrose","year":"2004","unstructured":"Penrose, M.: Random Geometric Graphs (Oxford Studies in Probability). Oxford University Press, Oxford (2004)"},{"key":"18_CR28","doi-asserted-by":"publisher","first-page":"3879","DOI":"10.1214\/12-AOP817","volume":"41","author":"M Reitzner","year":"2013","unstructured":"Reitzner, M., Schulte, M.: Central limit theorems for U-statistics of poisson point processes. Ann. Probab. 41, 3879\u20133909 (2013)","journal-title":"Ann. Probab."},{"key":"18_CR29","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.aam.2016.12.006","volume":"88","author":"M Reitzner","year":"2017","unstructured":"Reitzner, M., Schulte, M., Th\u00e4le, C.: Limit theory for the Gilbert graph. Adv. Appl. Math. 88, 26\u201361 (2017)","journal-title":"Adv. Appl. Math."},{"key":"18_CR30","volume-title":"Crossing Numbers of Graphs","author":"M Schaefer","year":"2017","unstructured":"Schaefer, M.: Crossing Numbers of Graphs. CRC-Press, Boca Raton (2017)"},{"key":"18_CR31","series-title":"Probability and Its Applications","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78859-1","volume-title":"Stochastic and Integral Geometry","author":"R Schneider","year":"2008","unstructured":"Schneider, R., Weil, W.: Stochastic and Integral Geometry. Probability and Its Applications. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78859-1"},{"key":"18_CR32","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/PL00008749","volume":"118","author":"L Wu","year":"2000","unstructured":"Wu, L.: A new modified logarithmic Sobolev inequality for Poisson point processes and several applications. Probab. Theory Relat. Fields 118, 427\u2013438 (2000)","journal-title":"Probab. Theory Relat. Fields"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04414-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T13:19:37Z","timestamp":1710249577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04414-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030044138","9783030044145"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04414-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"18 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Barcelona","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dccg.upc.edu\/gd2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.25","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.92","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The book also contains 1 full invited paper and 1 contest report","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}