{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T09:27:36Z","timestamp":1774690056205,"version":"3.50.1"},"reference-count":12,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5951,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1016\/s0166-218x(96)00013-3","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T13:19:33Z","timestamp":1049721573000},"page":"13-32","source":"Crossref","is-referenced-by-count":72,"title":["Trapezoid graphs and generalizations, geometry and algorithms"],"prefix":"10.1016","volume":"74","author":[{"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudolf","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorenz","family":"Wernisch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(96)00013-3_BIB1","first-page":"237","volume":"37","author":"Alt","year":"1991","journal-title":"Computing a maximum cardinality matching in a bipartite graph in time O(n1.5 (m\/ log n)0.5) Inf. Proc. Lett."},{"key":"10.1016\/S0166-218X(96)00013-3_BIB2","series-title":"Introduction to Algorithms","author":"Cormen","year":"1989"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB3","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"Dagan","year":"1988","journal-title":"Trapezoid graphs and their coloring Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(96)00013-3_BIB4","first-page":"29","volume":"11","author":"Fredman","year":"1975","journal-title":"On computing the length of longest increasing subsequences Discrete Math."},{"key":"10.1016\/S0166-218X(96)00013-3_BIB5","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1002\/net.3230030305","article-title":"Algorithms for a maximum clique and a maximum independent set of a circle graph","volume":"3","author":"Gavril","year":"1973","journal-title":"Networks"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB6","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB7","series-title":"Data Structures and Algorithms 3. Multi-dimensional Searching and Computational Geometry","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB8","series-title":"Proc. 5. Ann. Symp. on Discr. Alg.","article-title":"Linear-time modular decomposition and efficient transitive orientation of undirected graphs","author":"McConnel","year":"1994"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB9","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1983"},{"issue":"2","key":"10.1016\/S0166-218X(96)00013-3_BIB10","first-page":"77","article-title":"Range trees with slack parameter","volume":"2","author":"Smid","year":"1991","journal-title":"Algorithms Rev."},{"key":"10.1016\/S0166-218X(96)00013-3_BIB11","series-title":"Combinatorics and Partially Ordered Sets: Dimension Theory","author":"Trotter","year":"1991"},{"key":"10.1016\/S0166-218X(96)00013-3_BIB12","first-page":"80","article-title":"Preserving order in a forest in less than logarithmic time and linear space","volume":"6","author":"van Emde Boas","year":"1977"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X96000133?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X96000133?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T14:28:34Z","timestamp":1556116114000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X96000133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["S0166218X96000133"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(96)00013-3","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}