{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T01:34:31Z","timestamp":1784424871087,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540669043","type":"print"},{"value":"9783540466482","type":"electronic"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46648-7_7","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:29:28Z","timestamp":1186907368000},"page":"72-81","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Level Planar Embedding in Linear Time"],"prefix":"10.1007","author":[{"given":"Michael","family":"J\u00fcnger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Leipert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","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":"7_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"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G. Battista Di","year":"1988","unstructured":"G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61:175\u2013198, 1988.","journal-title":"Theoretical Computer Science"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(92)90072-4","volume":"41","author":"G. Battista Di","year":"1992","unstructured":"G. Di Battista, R. Tamassia, and I. G. Tollis. Constrained visibility representations of graphs. Information Processing Letters, 41:1\u20137, 1992.","journal-title":"Information Processing Letters"},{"key":"7_CR5","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":"1995","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, 1995."},{"key":"7_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-37623-2_17","volume-title":"Graph Drawing\u2019 98","author":"M. J\u00fcnger","year":"1998","unstructured":"M. J\u00fcnger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In S. Whitesides, editor, Graph Drawing\u2019 98, volume 1547 of Lecture Notes in Computer Science, pages 224\u2013237. Springer Verlag, 1998."},{"key":"7_CR7","unstructured":"S. Leipert. Level Planarity Testing and Embedding in Linear Time. PhD thesis, Universit\u00e4t zu K\u00f6ln, 1998."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46648-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T17:14:41Z","timestamp":1585934081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46648-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669043","9783540466482"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/3-540-46648-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"3 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}