{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:12:35Z","timestamp":1699834355185},"reference-count":10,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,3]],"date-time":"2006-10-03T00:00:00Z","timestamp":1159833600000},"content-version":"vor","delay-in-days":8798,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1982,9]]},"abstract":"Abstract<\/jats:title>Let C<\/jats:italic>(v<\/jats:italic>1<\/jats:sub>, \u2026,v<\/jats:italic>n<\/jats:italic><\/jats:sub>) be a system consisting of a circle C<\/jats:italic> with chords v<\/jats:italic>1<\/jats:sub>, \u2026,v<\/jats:italic>n<\/jats:italic><\/jats:sub> on it having different endpoints. Define a graph G<\/jats:italic> having vertex set V(G)<\/jats:italic> = {v<\/jats:italic>1<\/jats:sub>, \u2026,v<\/jats:italic>n<\/jats:italic><\/jats:sub>} and for which vertices v<\/jats:italic>i<\/jats:italic><\/jats:sub> and v<\/jats:italic>j<\/jats:italic><\/jats:sub> are adjacent in G<\/jats:italic> if the chords v<\/jats:italic>i<\/jats:italic><\/jats:sub> and v<\/jats:italic>j<\/jats:italic><\/jats:sub> intersect. Such a graph will be called a circle graph. The chords divide the interior of C<\/jats:italic> into a number of regions. We give a method which associates to each such region an orientation of the edges of G.<\/jats:italic> For a given C<\/jats:italic>(v<\/jats:italic>1<\/jats:sub>, \u2026,v<\/jats:italic>n<\/jats:italic><\/jats:sub>) the number m<\/jats:italic> of different orientations corresponding to it satisfies q<\/jats:italic> + 1 \u2264 m<\/jats:italic> \u2264 n<\/jats:italic> + q<\/jats:italic> + 1, where q<\/jats:italic> is the number of edges in G.<\/jats:italic> An oriented graph obtained from a diagram C<\/jats:italic>(v<\/jats:italic>1<\/jats:sub>, \u2026,v<\/jats:italic>n<\/jats:italic><\/jats:sub>) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G<\/jats:italic> is acyclic. In this case we define a special orientation of the complement of G<\/jats:italic>, and use this to develop an improved algorithm for finding a maximum independent set in G<\/jats:italic>.<\/jats:p>","DOI":"10.1002\/jgt.3190060309","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T07:03:07Z","timestamp":1180422187000},"page":"325-341","source":"Crossref","is-referenced-by-count":10,"title":["Orientations of circle graphs"],"prefix":"10.1002","volume":"6","author":[{"given":"R. C.","family":"Read","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Rotem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,3]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/B978-0-12-417750-5.50011-7","volume-title":"Theory of Machines and Computations","author":"Even S.","year":"1971"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321710"},{"key":"e_1_2_1_4_2","first-page":"811","article-title":"Une characterization des graphes de chordes","volume":"286","author":"Fournier J. C.","year":"1978","journal-title":"C.R. Acad. Sci. Paris"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"e_1_2_1_7_2","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","year":"1973"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-016-5"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32822.x"},{"key":"e_1_2_1_10_2","first-page":"843","volume-title":"Colloquia Mathematica Societatis Janos Bolyai","author":"Read R. C.","year":"1976"},{"key":"e_1_2_1_11_2","first-page":"273","article-title":"Graft systemu tetiv dane kruznice","volume":"15","author":"Zelinka B.","year":"1965","journal-title":"Mat. Fyz. Casopis SAV"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190060309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190060309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T05:07:58Z","timestamp":1699765678000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190060309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,9]]},"references-count":10,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,9]]}},"alternative-id":["10.1002\/jgt.3190060309"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190060309","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,9]]}}}