{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:46:02Z","timestamp":1725497162295},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_27","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"280-291","source":"Crossref","is-referenced-by-count":2,"title":["How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms"],"prefix":"10.1007","author":[{"given":"Frederic","family":"Dorn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Alber","year":"2000","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Niedermeier, R.: Fixed parameter algorithms for planar dominating set and related problems. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 97\u2013110. Springer, Heidelberg (2000)"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 613\u2013627. Springer, Heidelberg (2002)"},{"key":"27_CR4","first-page":"33","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Arora","year":"1998","unstructured":"Arora, S., Grigni, M., Karger, D., Klein, P., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, pp. 33\u201341. ACM Press, New York (1998)"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0210059","volume":"10","author":"P.A. Bernstein","year":"1981","unstructured":"Bernstein, P.A., Goodman, N.: Power of natural semijoins. SIAM Journal on Computing\u00a010, 751\u2013771 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H. Bodlaender","year":"1997","unstructured":"Bodlaender, H.: Treewidth: Algorithmic techniques and results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 19\u201336. Springer, Heidelberg (1997)"},{"key":"27_CR7","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernet.\u00a011, 1\u201321 (1993)","journal-title":"Acta Cybernet."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics\u00a06, 181\u2013188 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0012-365X(03)00230-9","volume":"273","author":"V. Bouchitt\u00e9","year":"2003","unstructured":"Bouchitt\u00e9, V., Mazoit, F., Todinca, I.: Chordal embeddings of planar graphs. Discrete Mathematics\u00a0273, 85\u2013102 (2003)","journal-title":"Discrete Mathematics"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W. Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS Journal on Computing\u00a015, 233\u2013248 (2003)","journal-title":"INFORMS Journal on Computing"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. Journal of the ACM\u00a052, 866\u2013893 (2005)","journal-title":"Journal of the ACM"},{"key":"27_CR12","volume-title":"Graph theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"27_CR14","unstructured":"Dorn, F.: How to use planarity efficiently: new tree-decomposition based algorithms (manuscript, 2007), \n                  \n                    http:\/\/www.ii.uib.no\/~frederic\/PlanDomSet.pdf"},{"key":"27_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/11785293_18","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Fast subexponential algorithm for non-local problems on graphs of bounded genus. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 172\u2013183. Springer, Heidelberg (2006)"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/11682462_37","volume-title":"LATIN 2006: Theoretical Informatics","author":"F. Dorn","year":"2006","unstructured":"Dorn, F., Telle, J.A.: Two birds with one stone: the best of branchwidth and treewidth with one algorithm. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 386\u2013397. Springer, Heidelberg (2006)"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1219944.1219946","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl.\u00a03, 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"27_CR19","first-page":"168","volume-title":"SODA 2003","author":"F.V. Fomin","year":"2003","unstructured":"Fomin, F.V., Thilikos, D.M.: Dominating sets in planar graphs: branch-width and exponential speed-up. In: SODA 2003. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, pp. 168\u2013177. ACM Press, New York (2003)"},{"key":"27_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory Series B\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P. Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: A survey. Discrete Mathematics\u00a0306, 297\u2013317 (2006)","journal-title":"Discrete Mathematics"},{"key":"27_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0020-0190(89)90070-7","volume":"31","author":"C.W. Ho","year":"1989","unstructured":"Ho, C.W., Lee, R.C.T.: Counting clique trees and computing perfect elimination schemes in parallel. Inf. Process. Lett.\u00a031, 61\u201368 (1989)","journal-title":"Inf. Process. Lett."},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Science\u00a032, 265\u2013279 (1986)","journal-title":"Journal of Computer and System Science"},{"key":"27_CR25","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Discrete Applied Mathematics\u00a079, 171\u2013188 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR26","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S. Parter","year":"1961","unstructured":"Parter, S.: The use of linear graphs in Gauss elimination. SIAM Review\u00a03, 119\u2013130 (1961)","journal-title":"SIAM Review"},{"key":"27_CR27","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B\u00a052, 153\u2013190 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"27_CR28","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing\u00a05, 146\u2013160 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR29","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing\u00a013, 566\u2013579 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR30","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math\u00a010, 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math"},{"key":"27_CR31","volume-title":"Graph algorithms","author":"J. Leeuwen van","year":"1990","unstructured":"van Leeuwen, J.: Graph algorithms. MIT Press, Cambridge, MA, USA (1990)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:34Z","timestamp":1619520154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_27","relation":{},"subject":[]}}