{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:05Z","timestamp":1759638725701},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615767"},{"type":"electronic","value":"9783540706274"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61576-8_71","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:58:53Z","timestamp":1330275533000},"page":"39-47","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Connected proper interval graphs and the guard problem in spiral polygons"],"prefix":"10.1007","author":[{"given":"Chiuyuan","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Chen","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(81)90048-X","volume":"13","author":"A. A. Bertossi","year":"1982","unstructured":"A. A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett. 13 (1982) 157\u2013159.","journal-title":"Inform. Process. Lett."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"A. A. Bertossi","year":"1983","unstructured":"A. A. Bertossi, Finding Hamiltonian circuits in proper interval graphs, Inform. Process. Lett. 17 (1983) 97\u2013101.","journal-title":"Inform. Process. Lett."},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1002\/jgt.3190150508","volume":"15","author":"G. Ding","year":"1991","unstructured":"G. Ding, Convering the edges with consecutive sets, J. Graph Theory 15 (1991) 559\u2013562.","journal-title":"J. Graph Theory"},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(90)90026-B","volume":"11","author":"H. Evertt","year":"1990","unstructured":"H. Evertt and D. G. Corneil, Recognizing visibility graphs of spiral polygons, J. Algorithms 11 (1990) 1\u201326.","journal-title":"J. Algorithms"},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835\u2013855.","journal-title":"Pacific J. Math."},{"key":"5_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco (1979)."},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976) 704\u2013714.","journal-title":"SIAM J. Comput."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput. 1 (1972) 180\u2013187.","journal-title":"SIAM J. Comput."},{"key":"5_CR9","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964) 539\u2013548.","journal-title":"Canad. J. Math."},{"key":"5_CR10","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York (1980)."},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/0211042","volume":"11","author":"D. Gouyou-Beauchamps","year":"1982","unstructured":"D. Gouyou-Beauchamps, The Hamiltonian circuit problem is polynomial for 4-connected planar graphs, SIAM J. Comput. 11 (1982) 529\u2013539.","journal-title":"SIAM J. Comput."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, Hamiltonian paths in grid graphs, SIAM J. Comput. 11 (1982) 676\u2013686.","journal-title":"SIAM J. Comput."},{"key":"5_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computation","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computation (eds. R. E. Miller and J. W. Thatcher) Plenum Press, New York (1972) 85\u2013103."},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"J. M. Keil","year":"1985","unstructured":"J. M. Keil, Finding Hamiltonian circuits in interval graphs, Inform. Process. Lett. 20 (1985) 201\u2013206.","journal-title":"Inform. Process. Lett."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/1008343.1008344","volume":"7","author":"M. S. Krishnamoorthy","year":"1975","unstructured":"M. S. Krishnamoorthy, An NP-hard problem in bipartite graphs, SIGACT News 7 (1975) 26.","journal-title":"SIGACT News"},{"key":"5_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(90)90025-S","volume":"35","author":"G. K. Manacher","year":"1990","unstructured":"G. K. Manacher, T. A. Mankus, and C. J. Smith, An optimum \u0398(nlogn) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals, Inform. Process. Lett. 35 (1990) 205\u2013211.","journal-title":"Inform. Process. Lett."},{"key":"5_CR17","volume-title":"Art Gallery Theorems and Algorithms","author":"J. O'Rourke","year":"1987","unstructured":"J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, New York (1987)."},{"key":"5_CR18","unstructured":"F. S. Roberts, Representations of Indifference Relations, Ph.D. thesis, Stanford University (1968)."},{"key":"5_CR19","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F. S. Roberts","year":"1969","unstructured":"F. S. Roberts, Indifference graphs, in: Proof Techniques in Graph Theory (ed. F. Harary) Academic Press, New York (1969) 139\u2013146."},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1137\/0221061","volume":"21","author":"W. K. Shih","year":"1992","unstructured":"W. K. Shih, T. C. Chern, and W. L. Hsu, An O(n\n2logn) algorithm for the Hamiltonian cycle problem on circular-arc graphs, SIAM J. Comput. 21 (1992) 1026\u20131046.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorics and Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61576-8_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:15:13Z","timestamp":1578518113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61576-8_71"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615767","9783540706274"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-61576-8_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}