{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:33:09Z","timestamp":1725489189471},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441861"},{"type":"electronic","value":"9783540457534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_8","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T11:37:09Z","timestamp":1187264229000},"page":"67-80","source":"Crossref","is-referenced-by-count":5,"title":["1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Jochen Alber, Hans L. Bodlaender, Henning Fernau, and Rolf Niedermeier. Fixed parameter algorithms for planar dominating set and related problems. In Algorithm theory\u2014Scandinavian Workshop on Algorithm Theory 2000 (Bergen, 2000), pages 97\u2013110. Springer, Berlin, 2000.","DOI":"10.1007\/3-540-44985-X_10"},{"issue":"2","key":"8_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277\u2013284, 1987.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Jochen Alber, Henning Fernau, and Rolf Niedermeier. Parameterized complexity: Exponential speed-up for planar graph problems. In Electronic Colloquium on Computational Complexity (ECCC). Germany, 2001.","DOI":"10.1007\/3-540-48224-5_22"},{"issue":"2\u20133","key":"8_CR4","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(85)90222-1","volume":"38","author":"T. Asano","year":"1985","unstructured":"Takao Asano. An approach to the subgraph homeomorphism problem. Theoret. Comput. Sci., 38(2\u20133):249\u2013267, 1985.","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for graphs with excluded minor and its applications. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), pages 293\u2013299, 1990.","DOI":"10.1145\/100216.100254"},{"issue":"1","key":"8_CR6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153\u2013180, 1994.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1\u20133","key":"8_CR7","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"H. J. Broersma","year":"2000","unstructured":"Hajo J. Broersma, Elias Dahlhaus, and Ton Kloks. A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs. Discrete Appl. Math., 99(1\u20133):367\u2013400, 2000.","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H. L. Bodlaender","year":"1995","unstructured":"Hans L. Bodlaender, John R. Gilbert, Hj\u00e1lmt\u00fdr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238\u2013255, 1995.","journal-title":"J. Algorithms"},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H. L. Bodlaender","year":"1995","unstructured":"Hans L. Bodlaender, Ton Kloks, and Dieter Kratsch. Treewidth and pathwidth of permutation graphs. SIAM J. Discrete Math., 8(4):606\u2013616, 1995.","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR10","unstructured":"Vincent Bouchitt\u00e9, Dieter Kratsch, Haiko M\u00fcller, and Ioan Todinca. On treewidth approximations. In Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW\u201901)."},{"key":"8_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"John A. Bondy and U. S. R. Murty. Graph Theory with Applications. American Elsevier Publishing Co., Inc., New York, 1976."},{"issue":"2","key":"8_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H. L. Bodlaender","year":"1993","unstructured":"Hans L. Bodlaender and Rolf H. M\u00f6hring. The pathwidth and treewidth of cographs. SIAM J. Discrete Math., 6(2):181\u2013188, 1993.","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR13","first-page":"1","volume":"11","author":"H. L. Bodlaender","year":"1993","unstructured":"Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1\u201323, 1993.","journal-title":"Acta Cybernetica"},{"issue":"6","key":"8_CR14","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"Hans L. Bodlaender. A linear-time algorithm for finding treedecompositions of small treewidth. SIAM J. Comput., 25(6):1305\u20131317, 1996.","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"8_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(97)00031-0","volume":"79","author":"H. L. Bodlaender","year":"1997","unstructured":"Hans L. Bodlaender and Dimitrios M. Thilikos. Treewidth for graphs with small chordality. Discrete Appl. Math., 79(1\u20133):45\u201361, 1997.","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"8_CR16","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"Vincent Bouchitt\u00e9 and Ioan Todinca. Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput., 31(1):212\u2013232 (electronic), 2001.","journal-title":"SIAM J. Comput."},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Graph-theoretic concepts in computer science (Ascona, 1999)","author":"J. Chen","year":"1999","unstructured":"Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: further observations and further improvements. In Graph-theoretic concepts in computer science (Ascona, 1999), pages 313\u2013324. Springer, Berlin, 1999."},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Maw-Shang Chang, Ton Kloks, and Chuan-Min Lee. Maximum clique transversals. In Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 300\u2013310. Mathematical Programming Society, Boltenhagen, Germany, 2001.","DOI":"10.1007\/3-540-45477-2_5"},{"issue":"4","key":"8_CR19","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1137\/0211055","volume":"11","author":"N. Chiba","year":"1982","unstructured":"Norishige Chiba, Takao Nishizeki, and Nobuji Saito. An approximation algorithm for the maximum independent set problem on planar graphs. SIAM J. Comput., 11(4):663\u2013675, 1982.","journal-title":"SIAM J. Comput."},{"key":"8_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. G. Downey","year":"1999","unstructured":"Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, New York, 1999."},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Erik D. Demaine, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Exponential speedup of fixed parameter algorithms on K 3,3-minor-free or K 5-minor-free graphs. Technical Report MIT-LCS-TR-838, M.I.T, March 2002.","DOI":"10.1007\/3-540-36136-7_24"},{"issue":"3\u20134","key":"8_CR22","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"David Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27(3\u20134):275\u2013291, 2000.","journal-title":"Algorithmica"},{"key":"8_CR23","unstructured":"MohammadTaghi Hajiaghayi. Algorithms for Graphs of (Locally) Bounded Treewidth. Master\u2019s thesis, University of Waterloo, September 2001."},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01462229","volume":"1","author":"M. Habib","year":"1994","unstructured":"Michel Habib and Rolf H. M\u00f6hring. Treewidth of cocomparability graphs and a new order-theoretic parameter. ORDER, 1:47\u201360, 1994.","journal-title":"ORDER"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Mohammadtaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. Fast approximation schemes for K 3,3-minor-free or K 5-minor-free graphs. In Euroconference on Combinatorics, Graph Theory and Applications 2001 (Barcelona, 2001). 2001.","DOI":"10.1016\/S1571-0653(04)00379-8"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2:135\u2013158, 1973.","journal-title":"SIAM J. Comput."},{"key":"8_CR27","unstructured":"Tom Kloks and Leizhen Cai. Parameterized tractability of some (efficient) Y-domination variants for planar graphs and t-degenerate graphs. In International Computer Symposium (ICS). Taiwan, 2000."},{"key":"8_CR28","unstructured":"Tom Kloks, C.M. Lee, and Jim Liu. Feedback vertex sets and disjoint cycles in planar (di)graphs. In Optimization Online. Mathematical Programming Society, Philadelphia, 2001."},{"key":"8_CR29","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-57568-5_240","volume-title":"Algorithms and computation (Hong Kong, 1993)","author":"T. Kloks","year":"1993","unstructured":"Ton Kloks. Treewidth of circle graphs. In Algorithms and computation (Hong Kong, 1993), pages 108\u2013117. Springer, Berlin, 1993."},{"key":"8_CR30","unstructured":"Andr\u00e9 K\u00e9zdy and Patrick McGuinness. Sequential and parallel algorithms to find a K 5 minor. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, FL, 1992), pages 345\u2013356, 1992."},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Iyad A. Kanj and Ljubomir Perkovic. Improved parameterized algorithms for planar dominating set. In 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002. Warszawa-Otwock, Poland, August 26\u201330, 2002. To appear.","DOI":"10.1007\/3-540-45687-2_33"},{"issue":"3","key":"8_CR32","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0022-0000(91)90004-O","volume":"42","author":"A. Kanevsky","year":"1991","unstructured":"Arkady Kanevsky and Vijaya Ramachandran. Improved algorithms for graph four-connectivity. J. Comput. System Sci., 42(3):288\u2013306, 1991. Twenty-Eighth IEEE Symposium on Foundations of Computer Science (Los Angeles, CA, 1987).","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"8_CR33","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615\u2013627, 1980.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01191205","volume":"12","author":"G. L. Miller","year":"1992","unstructured":"Gary L. Miller and Vijaya Ramachandran. A new graph triconnectivity algorithm and its parallelization. Combinatorica, 12(1):53\u201376, 1992.","journal-title":"Combinatorica"},{"key":"8_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory Series B, 36:49\u201364, 1984.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors \u2014 a survey. In I. Anderson, editor, Surveys in Combinatorics, pages 153\u2013171. Cambridge Univ. Press, 1985.","DOI":"10.1017\/CBO9781107325678.009"},{"issue":"3","key":"8_CR37","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"8_CR38","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory Series B, 52:153\u2013190, 1991.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"8_CR39","doi-asserted-by":"crossref","unstructured":"Neil Robertson and Paul Seymour. Excluding a graph with one crossing. In Graph structure theory (Seattle, WA, 1991), pages 669\u2013675. Amer. Math. Soc., Providence, RI, 1993.","DOI":"10.1090\/conm\/147\/01206"},{"issue":"4","key":"8_CR40","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0895480191193789","volume":"7","author":"R. Sundaram","year":"1994","unstructured":"Ravi Sundaram, Karan S. Singh, and Pandu C. Rangan. Treewidth of circular-arc graphs. SIAM J. Discrete Math., 7(4):647\u2013655, 1994.","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"8_CR41","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P. D. Seymour","year":"1994","unstructured":"Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217\u2013241, 1994.","journal-title":"Combinatorica"},{"issue":"2","key":"8_CR42","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. Tarjan","year":"1972","unstructured":"Robert Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146\u2013160, 1972.","journal-title":"SIAM J. Comput."},{"key":"8_CR43","first-page":"280","volume":"2","author":"K. Wagner","year":"1937","unstructured":"Kehrer Wagner. \u00dcber eine Eigenschaft der eben Komplexe. Deutsche Math., 2:280\u2013285, 1937.","journal-title":"Deutsche Math."},{"issue":"4","key":"8_CR44","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"S. G. Williamson","year":"1984","unstructured":"S. G. Williamson. Depth-first search and Kuratowski subgraphs. J. Assoc. Comput. Mach., 31(4):681\u2013693, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"8_CR45","doi-asserted-by":"crossref","unstructured":"Mihalis Yannakakis. Node-and edge-deletion NP-complete problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, CA, 1978), pages 253\u2013264. ACM press, New York, 1978.","DOI":"10.1145\/800133.804355"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:33:13Z","timestamp":1556771593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}