{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:40:26Z","timestamp":1767339626924},"publisher-location":"Berlin, Heidelberg","reference-count":6,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540654735"},{"type":"electronic","value":"9783540376231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-37623-2_17","type":"book-chapter","created":{"date-parts":[[2007,11,19]],"date-time":"2007-11-19T12:45:17Z","timestamp":1195476317000},"page":"224-237","source":"Crossref","is-referenced-by-count":36,"title":["Level Planarity Testing in Linear Time"],"prefix":"10.1007","author":[{"given":"Michael","family":"J\u00fcnger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Leipert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,1,15]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13:335\u2013379, 1976.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30:54\u201376, 1985.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"17_CR3","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/21.23105","volume":"18","author":"G. Battista Di","year":"1988","unstructured":"G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Transactions on systems, man, and cybernetics, 18(6):1035\u20131046, 1988.","journal-title":"IEEE Transactions on systems, man, and cybernetics"},{"key":"17_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/BFb0021813","volume-title":"Proc. Graph Drawing\u2019 95","author":"L.S. Heath","year":"1996","unstructured":"L.S. Heath and S.V. Pemmaraju. Recognizing leveled-planar dags in linear time. In F. J. Brandenburg, editor, Proc. Graph Drawing\u2019 95, volume 1027 of Lecture Notes in Computer Science, pages 300\u2013311. Springer Verlag, 1996a."},{"key":"17_CR5","unstructured":"L.S. Heath and S.V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. Technical report, Department of Computer Science, Virginia Polytechnic Institute & State University, 1996b."},{"key":"17_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-63938-1_62","volume-title":"Graph Drawing\u2019 97","author":"M. J\u00fcnger","year":"1997","unstructured":"M. J\u00fcnger, S. Leipert, and P. Mutzel. Pitfalls of using PQ-trees in Automatic Graph Drawing. In G. DiBattista, editor, Graph Drawing\u2019 97, volume 1353 of Lecture Notes in Computer Science, pages 193\u2013204. Springer Verlag, 1997."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-37623-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T18:12:27Z","timestamp":1551118347000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-37623-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540654735","9783540376231"],"references-count":6,"URL":"https:\/\/doi.org\/10.1007\/3-540-37623-2_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}