{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T21:20:56Z","timestamp":1790284856440,"version":"4.1.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1996,4]]},"abstract":"<jats:p>Our main result is a linear-time (that is, time $O(m + n)$) algorithm to recognize and represent proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time complexity $O(n^2 )$. We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs.<\/jats:p>","DOI":"10.1137\/s0097539792269095","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:43:31Z","timestamp":1109227411000},"page":"390-403","source":"Crossref","is-referenced-by-count":129,"title":["Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs"],"prefix":"10.1137","volume":"25","author":[{"given":"Xiaotie","family":"Deng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavol","family":"Hell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140310"},{"key":"R2","unstructured":"J. Bang-Jensen, P. Hell, J. Huang,  Local tournaments and proper circular arc graphs, Technical report, CSS\/LCCR TR90-11, Simon Fraser University, Burnaby, BC, Canada,  1990"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90130-9"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192242754"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R6","unstructured":"X. Deng, P. Hell, J. Huang,  E.  Balas, G.  Cornuejols, R.  Kannan,  Recognition and representation of proper circular arc graphs,  Integer Programming and Combinatorial Optimization, Proc. 2nd Integer Programming and Combinatorial Optimization Conference, Carnegie-Mellon University, Pittsburgh, PA,  1992,  114\u2013121"},{"key":"R7","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin Charles","year":"1980"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52921-7_59"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200312"},{"key":"R10","unstructured":"W. L. Hsu,  A simple test of interval graphs,  Proc. SIAM Conference on Discrete Mathematics, Vancouver,  1992"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90165-E"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1016"},{"key":"R13","unstructured":"J. Huang, Ph.D. Thesis,  Tournament-like oriented graphs, Simon Fraser University, Burnaby, BC, Canada,  1992"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0218005"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0602012"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060307"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90052-4"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1971.39.535"},{"key":"R19","unstructured":"G. Wegner, Ph.D. Thesis,  Eigenschaften der nerven homologische-einfactor familien in  Rn, Universit\u00e4t Gottingen, Gottingen, Germany,  1967"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539792269095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:14Z","timestamp":1787338574000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539792269095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["10.1137\/S0097539792269095"],"URL":"https:\/\/doi.org\/10.1137\/s0097539792269095","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}