{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:11:18Z","timestamp":1725567078371},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_80","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"787-797","source":"Crossref","is-referenced-by-count":6,"title":["A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-Trees"],"prefix":"10.1007","author":[{"given":"Wen-Lian","family":"Hsu","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"80_CR1","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 the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"80_CR2","unstructured":"Boyer, J., Myvold, W.: Stop minding your P\u2019s and Q\u2019s: A simplified O(n) embedding algorithm. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 140\u2013149 (1999)"},{"key":"80_CR3","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/0222068","volume":"22","author":"J. Cai","year":"1993","unstructured":"Cai, J., Han, X., Tarjan, R.E.: An O(mlogn)-time algorithm for the maximal planar subgraph problem. SIAM J. Comput.\u00a022, 1142\u20131162 (1993)","journal-title":"SIAM J. Comput."},{"key":"80_CR4","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, 54\u201376 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"80_CR5","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J.E. Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. Assoc. Comput. Mach.\u00a021, 549\u2013568 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"80_CR6","doi-asserted-by":"crossref","unstructured":"Hristo, D.: A Linear Algorithm for the Maximal Planar Subgraph Problem. In: Workshop on Algorithms and Data Structures, pp. 369\u2013380 (1995)","DOI":"10.1007\/3-540-60220-8_77"},{"key":"80_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computations","author":"W.L. Hsu","year":"1995","unstructured":"Hsu, W.L.: Finding maximal planar subgraphs in linear time. In: Staples, J., Katoh, N., Eades, P., Moffat, A. (eds.) ISAAC 1995. LNCS, vol.\u00a01004, Springer, Heidelberg (1995)"},{"key":"80_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-44679-6_23","volume-title":"Computing and Combinatorics","author":"W.L. Hsu","year":"2001","unstructured":"Hsu, W.L.: PC-trees vs. PQ-trees. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 207\u2013217. Springer, Heidelberg (2001)"},{"key":"80_CR9","doi-asserted-by":"crossref","unstructured":"Hsu, W.L., McConnell, R.: PQ Trees, PC Trees and Planar Graphs. In: Dinesh, P. (ed.) Mehta and Sartaj Sahni (eds) Handbook of Data Structures and Applications (2004)","DOI":"10.1201\/9781420035179.ch32"},{"key":"80_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R. Jayakumar","year":"1989","unstructured":"Jayakumar, R., Thulasiraman, K., Swamy, M.: On O(n2) algorithms for graph planarization. IEEE Transactions on Computer-Aided Design\u00a08, 257\u2013267 (1989)","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"80_CR11","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1109\/43.709399","volume":"17","author":"M. Junger","year":"1998","unstructured":"Junger, M., Leipert, S., Mutzel, P.: A note on computing a maximal planar subgraph using PQ-Trees. IEEE Transactions on Computer-Aided Design\u00a017, 609\u2013612 (1998)","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"80_CR12","unstructured":"Kant, G.: An O(n2) maximal planarization algorithm based on PQ-trees. Technical Report RUU-CS-92-03, Department of Computer Science, Utrecht Unvesity (1992)"},{"key":"80_CR13","unstructured":"Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P., Gordon, Breach (eds.) Theory of Graphs, New York, pp. 215\u2013232 (1967)"},{"key":"80_CR14","first-page":"93","volume":"2","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Graph algorithms and NP-completeness. Data Structure and Algorithms\u00a02, 93\u2013122 (1984)","journal-title":"Data Structure and Algorithms"},{"key":"80_CR15","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":"80_CR16","unstructured":"Small, J.: A unified approach of testing, embedding and drawing planar graphs. In: Proc. ALCOM International Workshop on Graph Drawing, Sevre, France (1993)"},{"key":"80_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, University of Hong Kong, pp. 110\u2013122 (1993)"},{"key":"80_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":"80_CR19","unstructured":"Stamm-Wilbrandt, H.: A simple linear-time algorithm for embedding maximal planar graphs. In: Proc. ALCOM International Workshop on Graph Drawing, Sere, France (1993)"},{"key":"80_CR20","unstructured":"Thomas, R.: Planarity in linear time \u2013 Lecture Notes. Georgia Institute of Technology (1997)"},{"key":"80_CR21","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"S.G. Williamson","year":"1984","unstructured":"Williamson, S.G.: Depth-first search and Kuratowski subgraphs. J. ACM\u00a031, 681\u2013693 (1984)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_80","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T18:37:38Z","timestamp":1586457458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11533719_80","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}