{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:47:51Z","timestamp":1767016071299,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,13]],"date-time":"2011-06-13T00:00:00Z","timestamp":1307923200000},"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":[[2011,6,13]]},"DOI":"10.1145\/1998196.1998258","type":"proceedings-article","created":{"date-parts":[[2011,6,14]],"date-time":"2011-06-14T14:45:32Z","timestamp":1308062732000},"page":"370-379","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["On the structure and composition of forbidden sequences, with geometric applications"],"prefix":"10.1145","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90677-8"},{"key":"e_1_3_2_1_2_1","volume-title":"Davenport-Schinzel Sequences and their Geometric Applications","author":"Agarwal P.","year":"1995","unstructured":"P. Agarwal and M. Sharir . Davenport-Schinzel Sequences and their Geometric Applications . Cambridge University Press , 1995 . P. Agarwal and M. Sharir. Davenport-Schinzel Sequences and their Geometric Applications. Cambridge University Press, 1995."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90032-0"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404002"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2373068"},{"key":"e_1_3_2_1_6_1","first-page":"87","volume-title":"Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Efrat A.","year":"1994","unstructured":"A. Efrat and M. Sharir . A near-linear algorithm for the planar segment center problem . In Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 87 -- 97 , 1994 . A. Efrat and M. Sharir. A near-linear algorithm for the planar segment center problem. In Proceedings 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 87--97, 1994."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02711511"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133172"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.02.040"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(90)90074-7"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.03.004"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579170"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.05.006"},{"issue":"4","key":"e_1_3_2_1_15_1","first-page":"737","article-title":"A general upper bound in extremal theory of sequences","volume":"33","author":"Klazar M.","year":"1992","unstructured":"M. Klazar . A general upper bound in extremal theory of sequences . Comment. Math. Univ. Carolin. , 33 ( 4 ): 737 -- 746 , 1992 . M. Klazar. A general upper bound in extremal theory of sequences. Comment. Math. Univ. Carolin., 33(4):737--746, 1992.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00188-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302967"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979018330X"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758836"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706597"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220029"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773960"},{"key":"e_1_3_2_1_24_1","first-page":"1115","volume-title":"Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms","author":"Pettie S.","year":"2008","unstructured":"S. Pettie . Splay trees, Davenport-Schinzel sequences, and the deque conjecture . In Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms , pages 1115 -- 1124 , 2008 . S. Pettie. Splay trees, Davenport-Schinzel sequences, and the deque conjecture. In Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms, pages 1115--1124, 2008."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873719"},{"key":"e_1_3_2_1_26_1","volume-title":"Degrees of nonlinearity in forbidden 0--1 matrix problems. In submission","author":"Pettie S.","year":"2010","unstructured":"S. Pettie . Degrees of nonlinearity in forbidden 0--1 matrix problems. In submission , 2010 . S. Pettie. Degrees of nonlinearity in forbidden 0--1 matrix problems. In submission, 2010."},{"key":"e_1_3_2_1_27_1","volume-title":"Generalized Davenport-Schinzel sequences and their 0--1 matrix counterparts. In submission","author":"Pettie S.","year":"2010","unstructured":"S. Pettie . Generalized Davenport-Schinzel sequences and their 0--1 matrix counterparts. In submission , 2010 . S. Pettie. Generalized Davenport-Schinzel sequences and their 0--1 matrix counterparts. In submission, 2010."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873672"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/080735862"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.11.015"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/647549.728926"},{"key":"e_1_3_2_1_32_1","volume-title":"Extremal problems in ordered graphs. arXiv, 0907.2479v1","author":"Weidert C.","year":"2009","unstructured":"C. Weidert . Extremal problems in ordered graphs. arXiv, 0907.2479v1 , 2009 . C. Weidert. Extremal problems in ordered graphs. arXiv, 0907.2479v1, 2009."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187894"}],"event":{"name":"SoCG '11: Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Paris France","acronym":"SoCG '11"},"container-title":["Proceedings of the twenty-seventh annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998258","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1998196.1998258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:27Z","timestamp":1750244787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,13]]},"references-count":33,"alternative-id":["10.1145\/1998196.1998258","10.1145\/1998196"],"URL":"https:\/\/doi.org\/10.1145\/1998196.1998258","relation":{},"subject":[],"published":{"date-parts":[[2011,6,13]]},"assertion":[{"value":"2011-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}