{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T01:47:13Z","timestamp":1648950433375},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T00:00:00Z","timestamp":1519776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00224-018-9855-4","type":"journal-article","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T04:48:01Z","timestamp":1519793281000},"page":"1490-1524","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Monotone Paths in Geometric Triangulations"],"prefix":"10.1007","volume":"62","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ritankar","family":"Mandal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,28]]},"reference":[{"key":"9855_CR1","doi-asserted-by":"crossref","unstructured":"Adler, I., Papadimitriou, C., Rubinstein, A.: On simplex pivoting rules and complexity theory. In: Proceedings of the 17th IPCO, LNCS 8494, Springer (2014)","DOI":"10.1007\/978-3-319-07557-0_2"},{"key":"9855_CR2","first-page":"9","volume":"12","author":"M Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. Ann. Discret. Math. 12, 9\u201312 (1982)","journal-title":"Ann. Discret. Math."},{"key":"9855_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry, 3rd edn. Springer, Berlin (2008)","edition":"3rd edn."},{"key":"9855_CR4","doi-asserted-by":"crossref","unstructured":"Buchin, K., Knauer, C., Kriegel, K., Schulz, A., Seidel, R.: On the number of cycles in planar graphs. In: Proceedings of the 13th COCOON, LNCS 4598, Springer (2007)","DOI":"10.1007\/978-3-540-73545-8_12"},{"issue":"3","key":"9855_CR5","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1007\/s00373-015-1621-7","volume":"32","author":"A Dumitrescu","year":"2016","unstructured":"Dumitrescu, A., L\u00f6ffler, M., Schulz, A., T\u00f3th, C. s. D.: Counting carambolas. Graphs Combin. 32(3), 923\u2013942 (2016)","journal-title":"Graphs Combin."},{"key":"9855_CR6","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Rote, G., T\u00f3th, Cs. D.: Monotone paths in planar convex subdivisions and polytopes. In: Discrete Geometry and Optimization, vol. 69 of Fields Institute of Communications, Springer, pp. 79\u2013104 (2013)","DOI":"10.1007\/978-3-319-00200-2_6"},{"issue":"2","key":"9855_CR7","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1137\/110849407","volume":"27","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Schulz, A., Sheffer, A., T\u00f3th, C. s. D.: Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discret. Math. 27(2), 802\u2013826 (2013)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"9855_CR8","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/2421119.2421136","volume":"43","author":"A Dumitrescu","year":"2012","unstructured":"Dumitrescu, A., T\u00f3th, C. s. D.: Computational Geometry Column 54. SIGACT News Bullet. 43(4), 90\u201397 (2012)","journal-title":"SIGACT News Bullet."},{"issue":"5","key":"9855_CR9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1017\/S0963548317000141","volume":"26","author":"A Dumitrescu","year":"2017","unstructured":"Dumitrescu, A., T\u00f3th, C. s. D.: Convex polygons in geometric triangulations. Combin. Probab. Comput. 26(5), 641\u2013659 (2017)","journal-title":"Combin. Probab. Comput."},{"issue":"4","key":"9855_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0925-7721(00)00010-9","volume":"16","author":"A Garc\u00eda","year":"2000","unstructured":"Garc\u00eda, A., Noy, M., Tejel, A.: Lower bounds on the number of crossing-free subgraphs of K N . Comput. Geom. 16(4), 211\u2013221 (2000)","journal-title":"Comput. Geom."},{"issue":"1","key":"9855_CR11","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/05062370X","volume":"21","author":"B G\u00e4rtner","year":"2007","unstructured":"G\u00e4rtner, B., Kaibel, V.: Two new bounds for the random-edge simplex-algorithm. SIAM J. Discret. Math. 21(1), 178\u2013190 (2007)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"9855_CR12","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1137\/S0097539703434978","volume":"34","author":"V Kaibel","year":"2005","unstructured":"Kaibel, V., Mechtel, R., Sharir, M., Ziegler, G.M.: The simplex algorithm in dimension three. SIAM J. Comput. 34(2), 475\u2013497 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9855_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF02293053","volume":"8","author":"G Kalai","year":"1992","unstructured":"Kalai, G.: Upper bounds for the diameter and height of graphs of convex polyhedra. Discret. Comput. Geom. 8(4), 363\u2013372 (1992)","journal-title":"Discret. Comput. Geom."},{"key":"9855_CR14","unstructured":"Kalai, G.: Polytope skeletons and paths. In: Handbook of Discrete and Computational Geometry Goodman, J., O\u2019Rourke, J., T\u00f3th, C. D. (eds), Chapter 19, pp. 505\u2013532, 3rd edn, CRC Press, Boca Raton (2017)"},{"issue":"4","key":"9855_CR15","first-page":"946","volume":"13","author":"V Klee","year":"1965","unstructured":"Klee, V.: Paths on polyhedra I. J. SIAM 13(4), 946\u2013956 (1965)","journal-title":"J. SIAM"},{"key":"9855_CR16","doi-asserted-by":"crossref","unstructured":"van Kreveld, M., L\u00f6ffler, M., Pach, J.: How many potatoes are in a mesh?, in Proc. 23rd ISAAC, LNCS 7676, Springer, pp. 166\u2013176 (2012)","DOI":"10.1007\/978-3-642-35261-4_20"},{"issue":"1","key":"9855_CR17","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/j.aim.2005.05.021","volume":"204","author":"J Matou\u0161ek","year":"2006","unstructured":"Matou\u0161ek, J., Szab\u00f3, T.: RANDOM EDGE can be exponential on abstract cubes. Adv. Math. 204(1), 262\u2013277 (2006)","journal-title":"Adv. Math."},{"key":"9855_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1002\/jgt.10168","volume":"46","author":"J Pach","year":"2004","unstructured":"Pach, J., T\u00f3th, G.: Monotone drawings of planar graphs. J. Graph Theory 46, 39\u201347 (2004). Corrected version: arXiv: http:\/\/arXiv.org\/abs\/1101.0967 ,2011","journal-title":"J. Graph Theory"},{"key":"9855_CR19","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.endm.2008.06.039","volume":"31","author":"A Razen","year":"2008","unstructured":"Razen, A., Snoeyink, J., Welzl, E.: Number of crossing-free geometric graphs vs. triangulations. Electron. Notes Discret. Math. 31, 195\u2013200 (2008)","journal-title":"Electron. Notes Discret. Math."},{"issue":"1","key":"9855_CR20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"issue":"3","key":"9855_CR21","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/s11750-013-0295-7","volume":"21","author":"F Santos","year":"2013","unstructured":"Santos, F.: Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP 21(3), 426\u2013460 (2013)","journal-title":"TOP"},{"key":"9855_CR22","doi-asserted-by":"crossref","first-page":"P70","DOI":"10.37236\/557","volume":"18","author":"M Sharir","year":"2011","unstructured":"Sharir, M., Sheffer, A.: Counting triangulations of planar point sets. Electron. J. Combin. 18, P70 (2011)","journal-title":"Electron. J. Combin."},{"issue":"6","key":"9855_CR23","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1017\/S096354831300031X","volume":"22","author":"M Sharir","year":"2013","unstructured":"Sharir, M., Sheffer, A.: Counting plane graphs: cross-graph charging schemes. Combin. Probab. Comput. 22(6), 935\u2013954 (2013)","journal-title":"Combin. Probab. Comput."},{"issue":"4","key":"9855_CR24","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1016\/j.jcta.2013.01.002","volume":"120","author":"M Sharir","year":"2013","unstructured":"Sharir, M., Sheffer, A., Welzl, E.: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn\u2019s technique. J. Combin. Theory, Ser. A 120(4), 777\u2013794 (2013)","journal-title":"J. Combin. Theory, Ser. A"},{"issue":"3","key":"9855_CR25","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/050636036","volume":"36","author":"M Sharir","year":"2006","unstructured":"Sharir, M., Welzl, E.: On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput. 36(3), 695\u2013720 (2006)","journal-title":"SIAM J. Comput."},{"key":"9855_CR26","unstructured":"Sheffer, A.: Numbers of plane graphs, https:\/\/adamsheffer.wordpress.com\/numbers-of-plane-graphs\/ (version of April, 2016)"},{"issue":"4","key":"9855_CR27","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1287\/moor.5.4.599","volume":"5","author":"MJ Todd","year":"1980","unstructured":"Todd, M.J.: The monotonic bounded Hirsch conjecture is false for dimension at least 4. Math. Oper. Res. 5(4), 599\u2013601 (1980)","journal-title":"Math. Oper. Res."},{"key":"9855_CR28","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140962310","volume":"28","author":"MJ Todd","year":"2014","unstructured":"Todd, M.J.: An improved Kalai-Kleitman bound for the diameter of a polyhedron. SIAM J. Discret. Math. 28, 1944\u20131947 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"9855_CR29","unstructured":"Ziegler, G.M.: Lectures on Polytopes, vol. 152 of GTM, Springer, pp. 83\u201393 (1994)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9855-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9855-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9855-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T20:22:40Z","timestamp":1603916560000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9855-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,28]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["9855"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9855-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,28]]},"assertion":[{"value":"28 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}