{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:56:58Z","timestamp":1725562618845},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220671"},{"type":"electronic","value":"9783540248385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24838-5_10","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T17:34:14Z","timestamp":1281288854000},"page":"129-144","source":"Crossref","is-referenced-by-count":4,"title":["Lempel, Even, and Cederbaum Planarity Method"],"prefix":"10.1007","author":[{"given":"John M.","family":"Boyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cristina G.","family":"Fernandes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"Noma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 C.","family":"de Pina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","first-page":"517","volume":"10","author":"L. Auslander","year":"1961","unstructured":"Auslander, L., Parter, S.V.: On imbedding graphs in the plane. Journal of Mathematics and Mechanics\u00a010, 517\u2013523 (1961)","journal-title":"Journal of Mathematics and Mechanics"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ\u2013tree algorithms. Journal of Computer and Systems Sciences\u00a013, 335\u2013379 (1976)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-24595-7_3","volume-title":"Graph Drawing","author":"J.M. Boyer","year":"2004","unstructured":"Boyer, J.M., Cortese, P.F., 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. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 25\u201336. Springer, Heidelberg (2004)"},{"key":"10_CR4","unstructured":"Boyer, J.M., Myrvold, W.: On the cutting edge: Simplified O(n) planarity by edge addition, p. 29 (preprint)"},{"key":"10_CR5","unstructured":"Boyer, J.M., Myrvold, W.: Stop minding your P\u2019s and Q\u2019s: A simplified O(n) planar embedding algorithm. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 140\u2013146 (1999)"},{"key":"10_CR6","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, A., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ\u2013trees. Journal of Computer and Systems Sciences\u00a030, 54\u201376 (1985)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/321921.321929","volume":"23","author":"N. Deo","year":"1976","unstructured":"Deo, N.: Note on Hopcroft and Tarjan planarity algorithm. Journal of the Association for Computing Machinery\u00a023, 74\u201375 (1976)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10_CR8","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., Tarjan, R.E.: Computing an st-numbering. Theoretical Computer Science\u00a02, 339\u2013344 (1976)","journal-title":"Theoretical Computer Science"},{"key":"10_CR9","unstructured":"Goldstein, A.J.: An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In Graph and Combinatorics Conf. Contract No. NONR 1858-(21), Office of Naval Research Logistics Proj., Dep. of Math., Princeton U., p. 2 (1963)"},{"issue":"4","key":"10_CR10","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. Journal of the Association for Computing Machinery\u00a021(4), 549\u2013568 (1974)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10_CR11","unstructured":"Hsu, W.L.: An efficient implementation of the PC-tree algorithm of Shih & Hsu\u2019s planarity test. Technical report, Inst. of Information Science, Academia Sinica (2003)"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-63938-1_62","volume-title":"Graph Drawing","author":"M. J\u00fcnger","year":"1997","unstructured":"J\u00fcnger, M., Leipert, S., Mutzel, P.: Pitfalls of using PQ-trees in automatic graph drawing. In: DiBattista, G. (ed.) GD 1997. LNCS, vol.\u00a01353, pp. 193\u2013204. Springer, Heidelberg (1997)"},{"key":"10_CR13","first-page":"215","volume-title":"Theory of Graphs","author":"A. Lempel","year":"1967","unstructured":"Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P. (ed.) Theory of Graphs, pp. 215\u2013232. Gordon and Breach, New York (1967)"},{"key":"10_CR14","volume-title":"The LEDA Platform of Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., N\u00e4her, S.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge Press, Cambridge (1997)"},{"key":"10_CR15","unstructured":"Noma, A.: An\u00e1lise experimental de algoritmos de planaridade. Master\u2019s thesis, Universidade de S\u00e3o Paulo (2003) (in Portuguese), \n                  \n                    http:\/\/www.ime.usp.br\/dcc\/posgrad\/teses\/noma\/dissertation.ps.gz"},{"key":"10_CR16","volume-title":"Combinatorial Algorithms: Theory and Practice","author":"E.M. Reingold","year":"1977","unstructured":"Reingold, E.M., Nievergelt, J., Deo, N.: Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Inc., Englewood Cliffs (1977)"},{"key":"10_CR17","unstructured":"Shih, W.K., Hsu, W.L.: A simple test for planar graphs. In: Proceedings of the International Workshop on Discrete Math. and Algorithms, pp. 110\u2013122. University of Hong Kong (1993)"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(98)00120-0","volume":"223","author":"W.K. Shih","year":"1999","unstructured":"Shih, W.K., Hsu, W.L.: A new planarity test. Theoretical Computer Science\u00a0223, 179\u2013191 (1999)","journal-title":"Theoretical Computer Science"},{"key":"10_CR19","unstructured":"Thomas, R.: Planarity in linear time (1997), \n                  \n                    http:\/\/www.math.gatech.edu\/~thomas\/"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0167-5060(08)70719-2","volume":"6","author":"S.G. Williamson","year":"1980","unstructured":"Williamson, S.G.: Embedding graphs in the plane \u2013 algorithmic aspects. Ann. Disc. Math.\u00a06, 349\u2013384 (1980)","journal-title":"Ann. Disc. Math."},{"key":"10_CR21","volume-title":"Combinatorics for Computer Science","author":"S.G. Williamson","year":"1985","unstructured":"Williamson, S.G.: Combinatorics for Computer Science. Computer Science Press, Maryland (1985)"},{"key":"10_CR22","unstructured":"Williamson, S.G.: Personal Communication (August 2001)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24838-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T19:49:44Z","timestamp":1552852184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24838-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220671","9783540248385"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24838-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}