{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T17:33:25Z","timestamp":1789407205257,"version":"build-2803163510"},"reference-count":20,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,6]],"date-time":"2006-10-06T00:00:00Z","timestamp":1160092800000},"content-version":"vor","delay-in-days":3992,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1995,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila\u2010Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. \u00a9 1995 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/jgt.3190200312","type":"journal-article","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T11:27:04Z","timestamp":1181215624000},"page":"361-374","source":"Crossref","is-referenced-by-count":21,"title":["Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs"],"prefix":"10.1002","volume":"20","author":[{"given":"Pavon","family":"Hell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140310"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90130-9"},{"key":"e_1_2_1_4_2","volume-title":"Local tournaments and proper circular arc graphs","author":"Bank\u2010Jensen J.","year":"1990"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_2_1_6_2","unstructured":"X.Deng P.Hell andJ.Huang Linear time representation algorithms for proper circular arc graphs and proper interval graphs SIAM J. Comput. in press."},{"key":"e_1_2_1_7_2","unstructured":"X.Deng P.Hell andJ.Hunag Recognition and representation of proper circular arc graphs in:Integer Programming and Combinatorial Optimization Proceedings of the Second IPCO Conference(eds. E. Balas G. Cornuejols and R. Kannan) (1962) 114\u2013121."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_2_1_9_2","first-page":"1370","article-title":"Caract\u00e9risation des graphes non orient\u00e8s dont on peut orienter les arrtes de maniere \u00e0 obtenier le graphe d'un relation d'ordre","volume":"254","author":"Ghouil\u00e0\u2010Houri A.","year":"1962","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_2_1_10_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_11_2","first-page":"101","volume-title":"Algorithms, Lecture Notes in Computer Science","author":"Hell P.","year":"1990"},{"key":"e_1_2_1_12_2","unstructured":"B.Bhattacharya P.HellandJ.Huang Linear algorithm for maximum clique and minimum coloring on proper circular arc graphs SIAM J. Disc. Math. in press."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1016"},{"key":"e_1_2_1_14_2","unstructured":"J.Hunag Tournament\u2010like orineted graphs Ph.D. thesis Simon Fraser University 1992."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.2307\/2317880"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1971-016-5"},{"key":"e_1_2_1_17_2","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"Roberts P. L.","year":"1969"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"D. J.RoseandR. E.Tarjan Algorithmic aspects of vertex elimination Proc. 7\u2010th Annual ACM Symposium on the Theory of Computing (1975)245\u2013254.","DOI":"10.1145\/800116.803775"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190060307"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214048"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(74)80027-0"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190200312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190200312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T02:59:17Z","timestamp":1698289157000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190200312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,11]]}},"alternative-id":["10.1002\/jgt.3190200312"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190200312","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,11]]}}}