{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T02:28:27Z","timestamp":1747880907872},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540639381"},{"type":"electronic","value":"9783540696742"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63938-1_62","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T11:35:47Z","timestamp":1153222547000},"page":"193-204","source":"Crossref","is-referenced-by-count":9,"title":["Pitfalls of using PQ-trees in automatic graph drawing"],"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":[[2005,7,29]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K. and Lueker, G. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13, 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T., Abe, S., and Ozawa, T. (1985). A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30, 54\u201376.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"18_CR3","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1109\/21.23105","volume":"18","author":"G. Battista Di","year":"1988","unstructured":"Di Battista, G. and Nardelli, E. (1988). Hierarchies and planarity theory. IEEE Transactions on systems, man, and cybernetics, 18(6), 1035\u20131046.","journal-title":"IEEE Transactions on systems, man, and cybernetics"},{"key":"18_CR4","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"Even, S. (1979). Graph Algorithms. Computer Science Press, Potomac, Maryland."},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"Even, S. and Tarjan, R. E. (1976). Computing an st-numbering. Theoretical Computer Science, 2, 339\u2013344.","journal-title":"Theoretical Computer Science"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Heath, L. and Pemmaraju, S. (1996a). Recognizing leveled-planar dags in linear time. In F. J. Brandenburg, editor, Proc. Graph Drawing '95, volume 1027 of Lecture Notes in Computer Science, pages 300\u2013311. Springer Verlag.","DOI":"10.1007\/BFb0021813"},{"key":"18_CR7","unstructured":"Heath, L. and Pemmaraju, S. (1996b). Stack and queue layouts of directed acyclic graphs: Part II. Technical report, Department of Computer Science, Virginia Polytechnic Institute & State University."},{"issue":"8","key":"18_CR8","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1109\/TCS.1986.1085997","volume":"33","author":"R. Jayakumar","year":"1986","unstructured":"Jayakumar, R., Thulasiraman, K., and Swamy, M. (1986). On maximal planarization of non-planar graphs. IEEE Transactions on Circuits Systems, 33(8), 843\u2013844.","journal-title":"IEEE Transactions on Circuits Systems"},{"issue":"3","key":"18_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R. Jayakumar","year":"1989","unstructured":"Jayakumar, R., Thulasiraman, K., and Swamy, M. (1989). On O(n 2) algorithms for graph planarization. IEEE Transactions on Computer-Aided Design, 8(3), 257\u2013267.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"18_CR10","unstructured":"J\u00fcnger, M., Leipert, S., and Mutzel, P. (1996). On computing a maximal planar subgraph using PQ-trees. Technical Report 96.227, Institut f\u00fcr Informatik der Universit\u00e4t zu K\u00f6ln."},{"key":"18_CR11","unstructured":"Kant, G. (1992). An O(n 2) maximal planarization algorithm based on PQ-trees. Technical Report RUU-CS-92-03, Department of Computer Science, Utrecht University."},{"key":"18_CR12","first-page":"215","volume-title":"Theory of Graphs: International Symposium: Rome, July 1966","author":"A. Lempel","year":"1967","unstructured":"Lempel, A., Even, S., and Cederbaum, I. (1967). An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium: Rome, July 1966, pages 215\u2013232. Gordon and Breach, New York."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Ozawa, T. and Takahashi, H. (1981). A graph-planarization algorithm and its application to random graphs. In Graph Theory and Algorithms, volume 108 of Lecture Notes in Computer Science, pages 95\u2013107. Springer Verlag.","DOI":"10.1007\/3-540-10704-5_9"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63938-1_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T03:17:36Z","timestamp":1555730256000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63938-1_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540639381","9783540696742"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-63938-1_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}