{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T07:51:05Z","timestamp":1780386665869,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,7,1]],"date-time":"1996-07-01T00:00:00Z","timestamp":836179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,7]]},"DOI":"10.1007\/bf02086610","type":"journal-article","created":{"date-parts":[[2005,8,15]],"date-time":"2005-08-15T00:28:41Z","timestamp":1124065721000},"page":"111-117","source":"Crossref","is-referenced-by-count":71,"title":["Applications of the crossing number"],"prefix":"10.1007","volume":"16","author":[{"given":"J.","family":"Pach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Shahrokhi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02086610_CR1","first-page":"1","volume-title":"Lecture Notes in Computer Science, Vol. 1207","author":"P. K. Agarwal","year":"1996","unstructured":"P. K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, Quasi-planar graphs have a linear number of edges,Proc. Graph Drawing '95, Passau (F. J. Brandenburg, ed.), Lecture Notes in Computer Science, Vol. 1207, Springer-Verlag, Berlin, 1996, pp. 1\u20137."},{"key":"BF02086610_CR2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF02187731","volume":"4","author":"N. Alon","year":"1989","unstructured":"N. Alon and P. Erd\u00f3s, Disjoint edges in geometric graphs,Discrete Comput. Geom.,4 (1989), 287\u2013290.","journal-title":"Discrete Comput. Geom."},{"key":"BF02086610_CR3","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon and J. Spencer,The Probabilistic Method, Wiley, New York, 1992."},{"key":"BF02086610_CR4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0925-7721(93)90028-5","volume":"3","author":"B. Aronov","year":"1993","unstructured":"B. Aronov, R. Seidel, and D. Souvaine, On compatible triangulations of simple polygons,Comput. Geom. Theory Appl.,3 (1993), 27\u201336.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02086610_CR5","first-page":"2","volume":"3","author":"S. Avital","year":"1966","unstructured":"S. Avital and H. Hanani, Graphs,Gilyonot Lematematika,3 (1966), 2\u20138 (in Hebrew).","journal-title":"Gilyonot Lematematika"},{"key":"BF02086610_CR6","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0095-8956(92)90003-G","volume":"56","author":"V. Capoyleas","year":"1992","unstructured":"V. Capoyleas and J. Pach, A Tur\u00e1n-type theorem on chords of a convex polygon,J. Combin. Theory Ser. B,56 (1992), 9\u201315.","journal-title":"J. Combin. Theory Ser. B"},{"key":"BF02086610_CR7","first-page":"280","volume-title":"Lecture Notes in Computer Science, Vol. 324","author":"K. Diks","year":"1988","unstructured":"K. Diks, H. N. Djidjev, O. Sykora, and I. V\u0159to, Edge separators for planar graphs and their applications,Proc. 13th Symp. on Mathematical Foundations of Computer Science (M. P. Chytil, L. Janiga, V. Koubek, eds.), Lecture Notes in Computer Science, Vol. 324, Springer-Verlag, Berlin, 1988, pp. 280\u2013290."},{"key":"BF02086610_CR8","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1080\/00029890.1946.11991674","volume":"53","author":"P. Erd\u00f3s","year":"1946","unstructured":"P. Erd\u00f3s, On sets of distances ofn points,Amer. Math. Monthly,53 (1946), 248\u2013250.","journal-title":"Amer. Math. Monthly"},{"key":"BF02086610_CR9","first-page":"338","volume-title":"Lecture Notes in Computer Science, Vol. 450","author":"H. Gazit","year":"1990","unstructured":"H. Gazit and G. L. Miller, Planar separators and the Euclidean norm,Algorithms, Proc. International Symp. SIGAL '90 (T. Asanoet al., eds.), Lecture Notes in Computer Science, Vol. 450, Springer-Verlag, Berlin, 1990, pp. 338\u2013347."},{"key":"BF02086610_CR10","doi-asserted-by":"crossref","unstructured":"W. Goddard, M. Katchalski, and D. J. Kleitman, Forcing disjoint segments in the plane,European J. Combin., to appear.","DOI":"10.1006\/eujc.1996.0032"},{"key":"BF02086610_CR11","first-page":"114","volume":"43","author":"H. Hopf","year":"1934","unstructured":"H. Hopf and E. Pannwitz, Aufgabe No. 167,Jahresber. Deutsch. Math.-Verein.,43 (1934), 114.","journal-title":"Jahresber. Deutsch. Math.-Verein."},{"key":"BF02086610_CR12","volume-title":"Arhus University Lecture Note Series, No. 53","author":"Y. S. Kupitz","year":"1979","unstructured":"Y. S. Kupitz,Extremal Problems in Combinatorial Geometry, Arhus University Lecture Note Series, No. 53, Arhus University, Arhus, 1979."},{"key":"BF02086610_CR13","volume-title":"Foundations of Computing Series","author":"F. T. Leighton","year":"1983","unstructured":"F. T. Leighton,Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, MA, 1983."},{"key":"BF02086610_CR14","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs,SIAM J. Appl. Math.,36 (1979), 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02086610_CR15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G. L. Miller","year":"1986","unstructured":"G. L. Miller, Finding small simple cycle separators for 2-connected planar graphs,J. Comput. System Sci.,32 (1986), 265\u2013279.","journal-title":"J. Comput. System Sci."},{"key":"BF02086610_CR16","volume-title":"Every geometric graph withn vertices and 3.6n\u20143.4 edges contains three pairwise disjoint edges, Manuscript","author":"P. O'Donnel","year":"1991","unstructured":"P. O'Donnel and M. Perles, Every geometric graph withn vertices and 3.6n\u20143.4 edges contains three pairwise disjoint edges, Manuscript, Rutgers University, New Brunswick, 1991."},{"key":"BF02086610_CR17","series-title":"DIMACS Series, Vol. 6","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1090\/dimacs\/006\/19","volume-title":"Discrete and Computational Geometry. Papers from DIMACS Special Year","author":"J. Pach","year":"1991","unstructured":"J. Pach, Notes on geometric graph theory, in:Discrete and Computational Geometry. Papers from DIMACS Special Year (J. Goodmanet al., eds.), DIMACS Series, Vol. 6, American Mathematical Society, Providence, RI, 1991, pp. 273\u2013285."},{"key":"BF02086610_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02574361","volume":"12","author":"J. Pach","year":"1994","unstructured":"J. Pach and J. T\u00f6r\u00f3csik, Some geometric applications of Dilworth's theorem,Discrete Comput. Geom.,12 (1994), 1\u20137.","journal-title":"Discrete Comput. Geom."},{"key":"BF02086610_CR19","doi-asserted-by":"crossref","unstructured":"A. Saalfeld, Joint triangulations and triangulation maps,Proc. 3rd Ann. ACM Symp. on Computational Geometry, 1987, pp. 195\u2013204.","DOI":"10.1145\/41958.41979"},{"key":"BF02086610_CR20","unstructured":"D. Souvaine and R. Wenger, Constructing piecewise linear homeomorphisms,Comput. Geom. Theory Appl., to appear."},{"key":"BF02086610_CR21","volume-title":"Computational Aspects of VLSI","author":"J. P. Ullman","year":"1984","unstructured":"J. P. Ullman,Computational Aspects of VLSI, Computer Science Press, Rockville, MD, 1984."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086610.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02086610\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02086610","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T14:00:54Z","timestamp":1557842454000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02086610"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,7]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,7]]}},"alternative-id":["BF02086610"],"URL":"https:\/\/doi.org\/10.1007\/bf02086610","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,7]]}}}