{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:33:21Z","timestamp":1725561201258},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540208310"},{"type":"electronic","value":"9783540245957"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24595-7_3","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T04:46:01Z","timestamp":1280378761000},"page":"25-36","source":"Crossref","is-referenced-by-count":8,"title":["Stop Minding Your P\u2019s and Q\u2019s: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm"],"prefix":"10.1007","author":[{"given":"John M.","family":"Boyer","sequence":"first","affiliation":[]},{"given":"Pier Francesco","family":"Cortese","sequence":"additional","affiliation":[]},{"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Booth, K., Lueker, G.: Testing for the consecutive ones property interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013 (1976)","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"3_CR2","unstructured":"Boyer, J., Myrvold, W.: Stop minding your P\u2019s and Q\u2019s: A simplified O(n) planar embedding algorithm. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 140\u2013146 (1999)"},{"key":"3_CR3","unstructured":"Boyer, J., Myrvold, W.: Stop minding your P\u2019s and Q\u2019s: Simplified planarity by edge addition (2003) (submitted), Preprint at http:\/\/www.pacificcoast.net\/~lightning\/planarity.ps"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Boyer, J.M., Cortese, P., Patrignani, M., Di Battista, G.: Stop minding your P\u2019s and Q\u2019s: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. Tech. Report RT-DIA-83-2003, Dept. of Computer Sci., Univ. di Roma Tre (2003)","DOI":"10.1007\/978-3-540-24595-7_3"},{"issue":"1","key":"3_CR5","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., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci.\u00a030(1), 54\u201376 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02579375","volume":"5","author":"H. Fraisseix de","year":"1985","unstructured":"de Fraisseix, H., Rosenstiehl, P.: A characterization of planar graphs by Tr\u00e9maux orders. Combinatorica\u00a05(2), 127\u2013135 (1985)","journal-title":"Combinatorica"},{"key":"3_CR7","unstructured":"de Fraysseix, H., Ossona de Mendez, P.: P.I.G.A.L.E - Public Implementation of a Graph Algorithm Library and Editor. SourceForge project page, http:\/\/sourceforge.net\/projects\/pigale"},{"key":"3_CR8","unstructured":"GDToolkit. An object-oriented library for handling and drawing graphs. Third University of Rome, http:\/\/www.dia.uniroma3.it\/~gdt"},{"key":"3_CR9","unstructured":"GTL. Graph template library. University of Passau - FMI - Theor. Comp. Science, http:\/\/infosun.fmi.uni-passau.de\/GTL\/"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM\u00a021(4) (1974)","DOI":"10.1145\/321850.321852"},{"key":"3_CR11","unstructured":"Hsu, W.-L.: An efficient implementation fo the PC-Tree algorithm of Shih and Hsu\u2019s planarity test. Tech. Report, Inst. of Inf. Science, Academia Sinica (2003)"},{"key":"3_CR12","first-page":"215","volume-title":"Theory of Graphs: Internat. Symposium (Rome 1966)","author":"A. Lempel","year":"1967","unstructured":"Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Theory of Graphs: Internat. Symposium (Rome 1966), pp. 215\u2013232. Gordon and Breach, New York (1967)"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01940648","volume":"16","author":"K. Mehlhorn","year":"1996","unstructured":"Mehlhorn, K., Mutzel, P.: On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica\u00a016, 233\u2013242 (1996)","journal-title":"Algorithmica"},{"key":"3_CR14","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1998","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, New York (1998)"},{"key":"3_CR15","unstructured":"Shih, W.-K., Hsu, W.-L.: A simple test for planar graphs. In: Int. Workshop on Discrete Math. and Algorithms, pp. 110\u2013122 (1993)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Shih, W.-K., Hsu, W.-L.: A new planarity test. Theor. Comp. Sci.\u00a0223 (1999)","DOI":"10.1016\/S0304-3975(98)00120-0"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24595-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:53:09Z","timestamp":1559332389000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24595-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540208310","9783540245957"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24595-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}