{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:11Z","timestamp":1740107111728,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T00:00:00Z","timestamp":1656115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T00:00:00Z","timestamp":1656115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003074","name":"ANPCyT","doi-asserted-by":"crossref","award":["PICT-2015-2218"],"award-info":[{"award-number":["PICT-2015-2218"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010253","name":"UBACyT","doi-asserted-by":"crossref","award":["20020170100495BA","20020160100095BA"],"award-info":[{"award-number":["20020170100495BA","20020160100095BA"]}],"id":[{"id":"10.13039\/501100010253","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MATH-AMSUD","award":["MATH190013"],"award-info":[{"award-number":["MATH190013"]}]},{"name":"ISCI CONICYT","award":["PIA FB0816","ICM P-05-004-F"],"award-info":[{"award-number":["PIA FB0816","ICM P-05-004-F"]}]},{"DOI":"10.13039\/501100002923","name":"Consejo Nacional de Investigaciones Cient\u00edficas y T\u00e9cnicas","doi-asserted-by":"publisher","award":["4841\/14"],"award-info":[{"award-number":["4841\/14"]}],"id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005740","name":"Universidad Nacional del Sur","doi-asserted-by":"publisher","award":["PGI 24\/L103","PGI 24\/L115"],"award-info":[{"award-number":["PGI 24\/L103","PGI 24\/L115"]}],"id":[{"id":"10.13039\/501100005740","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003074","name":"ANPCyT","doi-asserted-by":"crossref","award":["PICT-2017-1315"],"award-info":[{"award-number":["PICT-2017-1315"]}],"id":[{"id":"10.13039\/501100003074","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00373-022-02510-1","type":"journal-article","created":{"date-parts":[[2022,6,25]],"date-time":"2022-06-25T16:02:51Z","timestamp":1656172971000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["2-Nested Matrices: Towards Understanding the Structure of Circle Graphs"],"prefix":"10.1007","volume":"38","author":[{"given":"Guillermo","family":"Dur\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5150-6947","authenticated-orcid":false,"given":"Nina","family":"Pardal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mart\u00edn D.","family":"Safe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"key":"2510_CR1","doi-asserted-by":"crossref","unstructured":"Annexstein, F. S., Swaminathan, R. P.: On testing consecutive-ones property in parallel. In Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA \u201995, pages 234\u2013243, New York, NY, USA, 1995. Association for Computing Machinery","DOI":"10.1145\/215399.215449"},{"issue":"4","key":"2510_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1002\/jgt.21681","volume":"73","author":"A Basu","year":"2013","unstructured":"Basu, A., Das, S., Ghosh, S., Sen, M.: Circular-arc bigraphs and its subclasses. J. Graph Theory 73(4), 361\u2013376 (2013)","journal-title":"J. Graph Theory"},{"issue":"16","key":"2510_CR3","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1016\/j.dam.2010.06.020","volume":"159","author":"F Bonomo","year":"2011","unstructured":"Bonomo, F., Dur\u00e1n, G., Grippo, L., Safe, M.: Partial characterizations of circle graphs. Discrete Appl. Math. 159(16), 1699\u20131706 (2011)","journal-title":"Discrete Appl. Math."},{"key":"2510_CR4","doi-asserted-by":"publisher","unstructured":"Bonomo-Braberman, F., Dur\u00e1n, G., Pardal, N., Safe, M. D.: Forbidden induced subgraph characterization of circle graphs within split graphs. Discrete Appl. Math., In press., 2021. https:\/\/doi.org\/10.1016\/j.dam.2020.12.021","DOI":"10.1016\/j.dam.2020.12.021"},{"issue":"3","key":"2510_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A Bouchet","year":"1987","unstructured":"Bouchet, A.: Reducing prime graphs and recognizing circle graphs. Combinatorica 7(3), 243\u2013254 (1987)","journal-title":"Combinatorica"},{"key":"2510_CR6","doi-asserted-by":"crossref","unstructured":"Bouchet, A.: Circle graphs obstructions. J. Comb. Theory, Ser. B, 60(1):107\u2013144, (1994)","DOI":"10.1006\/jctb.1994.1008"},{"key":"2510_CR7","doi-asserted-by":"crossref","unstructured":"Brijder, R., Traldi, L.: A characterization of circle graphs in terms of multimatroid representations. Electron. J. Comb., 27(1):P1.25, (2020)","DOI":"10.37236\/6992"},{"key":"2510_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103455","volume":"102","author":"R Brijder","year":"2022","unstructured":"Brijder, R., Traldi, L.: A characterization of circle graphs in terms of total unimodularity. Eur. J. Comb. 102, 103455 (2022)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"2510_CR9","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2510_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.dam.2012.12.021","volume":"164","author":"G Dur\u00e1n","year":"2014","unstructured":"Dur\u00e1n, G., Grippo, L., Safe, M.: Structural results on circular-arc graphs and circle graphs: a survey and the main open problems. Discrete Appl. Math. 164, 427\u2013443 (2014)","journal-title":"Discrete Appl. Math."},{"key":"2510_CR11","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A.: Queues, stacks, and graphs. In Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), pages 71\u201386, (1971)","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"key":"2510_CR12","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S Even","year":"1972","unstructured":"Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. Assoc. Comput. Mach. 19, 400\u2013410 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"6","key":"2510_CR13","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1016\/j.dam.2011.04.016","volume":"160","author":"T Feder","year":"2012","unstructured":"Feder, T., Hell, P., Huang, J., Rafiey, A.: Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms. Discrete Appl. Math. 160(6), 697\u2013707 (2012)","journal-title":"Discrete Appl. Math."},{"key":"2510_CR14","unstructured":"Fishburn, P. C.: Interval orders and interval graphs. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1985. A study of partially ordered sets, A Wiley-Interscience Publication"},{"key":"2510_CR15","unstructured":"F\u00f6ldes, S., Hammer, P. L.: Split graphs. Technical Report Technical Report CORR 76-3, University of Waterloo, Waterloo, Canada, (1976)"},{"key":"2510_CR16","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"2510_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar. 18, 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"issue":"2","key":"2510_CR18","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"MR Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Alg. Disc. Meth. 1(2), 216\u2013227 (1980)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"2510_CR19","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1002\/net.3230040407","volume":"4","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: Algorithms on circular-arc graphs. Networks 4, 357\u2013369 (1974)","journal-title":"Networks"},{"issue":"1","key":"2510_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.20363","volume":"61","author":"J Geelen","year":"2009","unstructured":"Geelen, J., Oum, S.: Circle graph obstructions under pivoting. J. Graph Theory 61(1), 1\u201311 (2009)","journal-title":"J. Graph Theory"},{"issue":"4","key":"2510_CR21","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1007\/s00453-013-9745-8","volume":"69","author":"E Gioan","year":"2014","unstructured":"Gioan, E., Paul, C., Tedder, M., Corneil, D.: Practical and efficient circle graph recognition. Algorithmica 69(4), 759\u2013788 (2014)","journal-title":"Algorithmica"},{"key":"2510_CR22","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition, 2004. With a foreword by Claude Berge","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"2510_CR23","doi-asserted-by":"crossref","unstructured":"Hsu, W.-L.: On physical mapping algorithms: an error-tolerant test for the consecutive ones property. In Computing and combinatorics (Shanghai, 1997), volume 1276 of Lecture Notes in Comput. Sci., pages 242\u2013250. Springer, Berlin, (1997)","DOI":"10.1007\/BFb0045091"},{"issue":"7\u20138","key":"2510_CR24","doi-asserted-by":"publisher","first-page":"1037","DOI":"10.1016\/j.dam.2012.11.005","volume":"161","author":"MC Lin","year":"2013","unstructured":"Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Normal Helly circular-arc graphs and its subclasses. Discrete Appl. Math. 161(7\u20138), 1037\u20131059 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2510_CR25","first-page":"53","volume":"6","author":"W Lipski","year":"1983","unstructured":"Lipski, W.: Generalizations of the consecutive ones property and related np-complete problems. Fund. Inform. 6(1), 53\u201369 (1983)","journal-title":"Fund. Inform."},{"issue":"2","key":"2510_CR26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R McConnell","year":"2003","unstructured":"McConnell, R.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"issue":"4","key":"2510_CR27","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.aml.2007.04.001","volume":"21","author":"GB Mertzios","year":"2008","unstructured":"Mertzios, G.B.: A matrix characterization of interval and proper interval graphs. Appl. Math. Lett. 21(4), 332\u2013337 (2008)","journal-title":"Appl. Math. Lett."},{"key":"2510_CR28","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0012-365X(85)90117-7","volume":"54","author":"W Naji","year":"1985","unstructured":"Naji, W.: Reconnaissance des graphes de cordes. Discret. Math. 54, 329\u2013337 (1985)","journal-title":"Discret. Math."},{"key":"2510_CR29","unstructured":"Pardal, N.: Structural characterization of some problems on circle and interval graphs. PhD thesis, Universidad de Buenos Aires - Universit\u00e9 Sorbonne Paris-Nord, 2020. arXiv:2006.00099"},{"key":"2510_CR30","first-page":"119","volume":"46","author":"N Pardal","year":"2018","unstructured":"Pardal, N., Dur\u00e1n, G.A., Grippo, L.N., Safe, M.D.: On nested and 2-nested graphs: two subclasses of graphs between threshold and split graphs. Mat. Contemp. 46, 119\u2013128 (2018)","journal-title":"Mat. Contemp."},{"key":"2510_CR31","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/0095-8956(71)90010-4","volume":"11","author":"FS Roberts","year":"1971","unstructured":"Roberts, F.S.: On the compatibility between a graph and a simple order. J. Combinatorial Theory Ser. B 11, 28\u201338 (1971)","journal-title":"J. Combinatorial Theory Ser. B"},{"issue":"2","key":"2510_CR32","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1002\/jgt.22486","volume":"93","author":"MD Safe","year":"2020","unstructured":"Safe, M.D.: Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property. J. Graph Theory 93(2), 268\u2013298 (2020)","journal-title":"J. Graph Theory"},{"issue":"2","key":"2510_CR33","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1137\/19M1266162","volume":"35","author":"MD Safe","year":"2021","unstructured":"Safe, M.D.: Circularly compatible ones, $$D$$-circularity, and proper circular-arc bigraphs. SIAM J. Discrete Math. 35(2), 707\u2013751 (2021)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"2510_CR34","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1002\/jgt.3190130206","volume":"13","author":"M Sen","year":"1989","unstructured":"Sen, M., Das, S., Roy, A.B., West, D.B.: Interval digraphs: an analogue of interval graphs. J. Graph Theory 13(2), 189\u2013202 (1989)","journal-title":"J. Graph Theory"},{"issue":"5","key":"2510_CR35","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1002\/jgt.3190130508","volume":"13","author":"M Sen","year":"1989","unstructured":"Sen, M., Das, S., West, D.B.: Circular-arc digraphs: a characterization. J. Graph Theory 13(5), 581\u2013592 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"2510_CR36","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/S0895480190177145","volume":"7","author":"M Sen","year":"1994","unstructured":"Sen, M., Sanyal, B.K.: Indifference digraphs: a generalization of indifference graphs and semiorders. SIAM J. Discrete Math. 7(2), 157\u2013165 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"2510_CR37","doi-asserted-by":"publisher","first-page":"723","DOI":"10.7151\/dmgt.1894","volume":"36","author":"L Traldi","year":"2016","unstructured":"Traldi, L.: Splitting cubic circle graphs. Discuss. Math. Graph Theory 36(3), 723\u2013741 (2016)","journal-title":"Discuss. Math. Graph Theory"},{"key":"2510_CR38","doi-asserted-by":"publisher","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"A Tucker","year":"1971","unstructured":"Tucker, A.: Matrix characterizations of circular-arc graphs. Pacific J. Math. 39, 535\u2013545 (1971)","journal-title":"Pacific J. Math."},{"key":"2510_CR39","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A Tucker","year":"1972","unstructured":"Tucker, A.: A structure theorem for the consecutive $$1$$\u2019s property. J. Combinatorial Theory Ser. B 12, 153\u2013162 (1972)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"2510_CR40","unstructured":"Tucker, A.C.: Two characterizations of proper circular-arc graphs. PhD thesis, Stanford University, (1969)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02510-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02510-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02510-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T13:16:05Z","timestamp":1660223765000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02510-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,25]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["2510"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02510-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2022,6,25]]},"assertion":[{"value":"16 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"111"}}