{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T15:43:04Z","timestamp":1751384584316},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642102165"},{"type":"electronic","value":"9783642102172"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-10217-2_23","type":"book-chapter","created":{"date-parts":[[2009,11,9]],"date-time":"2009-11-09T15:52:03Z","timestamp":1257781923000},"page":"218-229","source":"Crossref","is-referenced-by-count":3,"title":["Polar Permutation Graphs"],"prefix":"10.1007","author":[{"given":"T\u0131naz","family":"Ekim","sequence":"first","affiliation":[]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Meister","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(89)90221-4","volume":"31","author":"H. Bodlaender","year":"1989","unstructured":"Bodlaender, H.: Achromatic number is NP-complete for cographs and interval graphs. Information Processing Letters\u00a031, 135\u2013138 (1989)","journal-title":"Information Processing Letters"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM Journal on Discrete Mathematics\u00a08, 606\u2013616 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM, Philadelphia (1999)"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/jgt.3190110113","volume":"11","author":"J.I. Brown","year":"1987","unstructured":"Brown, J.I., Corneil, D.G.: On generalized graph colorings. Journal of Graph Theory\u00a011, 87\u201399 (1987)","journal-title":"Journal of Graph Theory"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0012-365X(86)90113-5","volume":"62","author":"Z.A. Chernyak","year":"1986","unstructured":"Chernyak, Z.A., Chernyak, A.A.: About recognizing (\u03b1, \u03b2)-classes of polar graphs. Discrete Mathematics\u00a062, 133\u2013138 (1986)","journal-title":"Discrete Mathematics"},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. III. Tree-decompositions, minors and complexity issues. RAIRO Inform. Theor. Appl.\u00a026, 257\u2013286 (1992)","journal-title":"RAIRO Inform. Theor. Appl."},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems\u00a033, 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"key":"23_CR9","unstructured":"Ekim, T.: Polarity of claw-free graphs (submitted)"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"2469","DOI":"10.1016\/j.dam.2008.01.026","volume":"156","author":"T. Ekim","year":"2008","unstructured":"Ekim, T., Hell, P., Stacho, J., de Werra, D.: Polarity of chordal graphs. Discrete Applied Mathematics\u00a0156, 2469\u20132479 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR11","unstructured":"Ekim, T., Huang, J.: Recognizing line-polar bipartite graphs (manuscript)"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1016\/j.dam.2007.08.025","volume":"156","author":"T. Ekim","year":"2008","unstructured":"Ekim, T., Mahadev, N.V.R., de Werra, D.: Polar cographs. Discrete Applied Mathematics\u00a0156, 1652\u20131660 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Feder, T., Hell, P., Klein, S., Motwani, R.: Complexity of graph partition problems. In: Proceedings of STOC 1999, pp. 464\u2013472 (1999)","DOI":"10.1145\/301250.301373"},{"key":"23_CR14","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0020-0190(02)00288-0","volume":"84","author":"F.V. Fomin","year":"2002","unstructured":"Fomin, F.V., Kratsch, D., Novelli, J.-C.: Approximating minimum cocolorings. Information Processing Letters\u00a084, 285\u2013290 (2002)","journal-title":"Information Processing Letters"},{"key":"23_CR15","first-page":"115","volume":"143","author":"A.V. Gagarin","year":"1999","unstructured":"Gagarin, A.V.: Chordal (1, \u03b2)-polar graphs. Vestsi Nats. Akad. Navuk Belarusi Ser. Fiz.-Mat. Navuk\u00a0143, 115\u2013118 (1999)","journal-title":"Vestsi Nats. Akad. Navuk Belarusi Ser. Fiz.-Mat. Navuk"},{"key":"23_CR16","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol.\u00a057. North-Holland, Amsterdam (2004)"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the Clique-Width of Some Perfect Graph Classes. International Journal of Foundations of Computer Science\u00a011, 423\u2013443 (2000)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"P.L. Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica\u00a01, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0166-218X(03)00371-8","volume":"141","author":"P. Hell","year":"2004","unstructured":"Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics\u00a0141, 185\u2013194 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR20","unstructured":"Huang, J., Xu, B.: A forbidden subgraph characterization of line-polar bipartite graphs (submitted)"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"2901","DOI":"10.1016\/j.disc.2004.06.024","volume":"306","author":"V.V. Lozin","year":"2006","unstructured":"Lozin, V.V., Mosca, R.: Polar graphs and maximal independent sets. Discrete Mathematics\u00a0306, 2901\u20132908 (2006)","journal-title":"Discrete Mathematics"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Mathematics\u00a0201, 189\u2013241 (1999)","journal-title":"Discrete Mathematics"},{"key":"23_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/11604686_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Meister","year":"2005","unstructured":"Meister, D.: Computing Treewidth and Minimum Fill-In for Permutation Graphs in Linear Time. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 91\u2013102. Springer, Heidelberg (2005)"},{"key":"23_CR24","first-page":"50","volume":"6","author":"O.I. Melnikov","year":"1985","unstructured":"Melnikov, O.I., Kozhich, P.P.: Algorithms for recognizing the polarity of a graph with bounded parameters. Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk\u00a06, 50\u201354 (1985)","journal-title":"Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01072106","volume":"21","author":"R.I. Tyshkevich","year":"1985","unstructured":"Tyshkevich, R.I., Chernyak, A.A.: Decompositions of Graphs. Cybernetics and System Analysis\u00a021, 231\u2013242 (1985)","journal-title":"Cybernetics and System Analysis"},{"key":"23_CR26","first-page":"16","volume":"6","author":"R.I. Tyshkevich","year":"1985","unstructured":"Tyshkevich, R.I., Chernyak, A.A.: Algorithms for the canonical decomposition of a graph and recognizing polarity. Izvestia Akad. Nauk BSSR, ser. Fiz. Mat. Nauk\u00a06, 16\u201323 (1985) (in Russian)","journal-title":"Izvestia Akad. Nauk BSSR, ser. Fiz. Mat. Nauk"},{"key":"23_CR27","first-page":"633","volume":"20","author":"K. Wagner","year":"1984","unstructured":"Wagner, K.: Monotonic coverings of finite sets. Elektronische Informationsverarbeitung und Kybernetik\u00a020, 633\u2013639 (1984)","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-10217-2_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:34:29Z","timestamp":1619782469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-10217-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642102165","9783642102172"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-10217-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}