{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T10:33:45Z","timestamp":1772793225440,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T00:00:00Z","timestamp":1456358400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000782","name":"European Science Foundation (FR)","doi-asserted-by":"publisher","award":["F.R.S.-FNRS - EUROGIGA NR 13604"],"award-info":[{"award-number":["F.R.S.-FNRS - EUROGIGA NR 13604"]}],"id":[{"id":"10.13039\/501100000782","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"GA\u010cR","doi-asserted-by":"crossref","award":["GIG\/11\/E023"],"award-info":[{"award-number":["GIG\/11\/E023"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"GA\u010cR","doi-asserted-by":"crossref","award":["GIG\/11\/E023"],"award-info":[{"award-number":["GIG\/11\/E023"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001824","name":"GA\u010cR","doi-asserted-by":"crossref","award":["14-14179S"],"award-info":[{"award-number":["14-14179S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001823","name":"Czech Ministry of Education, Youth and Sports","doi-asserted-by":"crossref","award":["LO1506"],"award-info":[{"award-number":["LO1506"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004895","name":"European Social Fund","doi-asserted-by":"publisher","award":["NEXLIZ - CZ.1.07\/2.3.00\/30.0038"],"award-info":[{"award-number":["NEXLIZ - CZ.1.07\/2.3.00\/30.0038"]}],"id":[{"id":"10.13039\/501100004895","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0133-z","type":"journal-article","created":{"date-parts":[[2016,2,25]],"date-time":"2016-02-25T09:26:25Z","timestamp":1456392385000},"page":"1071-1104","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Extending Partial Representations of Proper and Unit Interval Graphs"],"prefix":"10.1007","volume":"77","author":[{"given":"Pavel","family":"Klav\u00edk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiki","family":"Saitoh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Saumell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1\u0161","family":"Vysko\u010dil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,2,25]]},"reference":[{"issue":"4","key":"133_CR1","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/2629341","volume":"11","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Battista, G.D., Frati, F., Jel\u00ednek, V., Kratochv\u00edl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. ACM Trans. Algorithms 11(4), 32:1\u201332:42 (2015)","journal-title":"ACM Trans. Algorithms"},{"key":"133_CR2","doi-asserted-by":"crossref","unstructured":"Balko, M., Klav\u00edk, P., Otachi, Y.: Bounded representations of interval and proper interval graphs. In: Algorithms and Computation\u201424th International Symposium, ISAAC 2013, Lecture Notes in Computer Science, vol. 8283, pp. 535\u2013546. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-45030-3_50"},{"issue":"1","key":"133_CR3","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/s11083-011-9229-x","volume":"30","author":"B Balof","year":"2013","unstructured":"Balof, B., Doignon, J.P., Fiorini, S.: The representation polyhedron of a semiorder. Order 30(1), 103\u2013135 (2013)","journal-title":"Order"},{"key":"133_CR4","unstructured":"Bang-Jensen, J., Huang, J., Zhu, X.: Completing Orientations of Partially Oriented Graphs. CoRR (2015). arXiv:1509.01301"},{"key":"133_CR5","doi-asserted-by":"crossref","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: SODA\u201913: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1030\u20131043 (2013)","DOI":"10.1137\/1.9781611973105.74"},{"key":"133_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"133_CR7","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Dorbec, P., Kratochv\u00edl, J., Montassier, M., Stacho, J.: Contact representations of planar graphs: extending a partial representation is hard. In: Graph-Theoretic Concepts in Computer Science\u201440th International Workshop, WG 2014, Lecture Notes in Computer Science, vol. 8747, pp. 139\u2013151. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-12340-0_12"},{"key":"133_CR8","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Fulek, R., Klav\u00edk, P.: Extending partial representations of circle graphs. In: Graph Drawing\u201421st International Symposium, GD 2013, Lecture Notes in Computer Science, vol. 8242, pp. 131\u2013142. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03841-4_12"},{"key":"133_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"2","key":"133_CR10","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55(2), 99\u2013104 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"133_CR11","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG Corneil","year":"2009","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discret. Math. 23(4), 1905\u20131953 (2009)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"133_CR12","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390\u2013403 (1996)","journal-title":"SIAM J. Comput."},{"key":"133_CR13","unstructured":"Dur\u00e1n, G., Fern\u00e1ndez Slezak, F., Grippo, L.N., Oliveira, F.d.S., Szwarcfiter, J.: On unit interval graphs with integer endpoints. In: LAGOS 2015 (2015). http:\/\/www.lia.ufc.br\/lagos2015\/docs\/endm\/ENDM50_74.pdf"},{"issue":"3","key":"133_CR14","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"133_CR15","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397\u2013411 (1975)","journal-title":"SIAM J. Comput."},{"key":"133_CR16","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964)","journal-title":"Can. J. Math."},{"key":"133_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. North-Holland, Amsterdam (2004)"},{"key":"133_CR18","first-page":"65","volume":"11","author":"G Haj\u00f3s","year":"1957","unstructured":"Haj\u00f3s, G.: \u00dcber eine Art von Graphen. Int. Math. Nachr. 11, 65 (1957)","journal-title":"Int. Math. Nachr."},{"key":"133_CR19","doi-asserted-by":"crossref","unstructured":"Jampani, K.R., Lubiw, A.: Simultaneous interval graphs. In: Algorithms and Computation\u201421st International Symposium, ISAAC 2010, Lecture Notes in Computer Science, vol. 6506, pp. 206\u2013217. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-17517-6_20"},{"issue":"2","key":"133_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.7155\/jgaa.00259","volume":"16","author":"KR Jampani","year":"2012","unstructured":"Jampani, K.R., Lubiw, A.: The simultaneous representation problem for chordal, comparability and permutation graphs. J. Graph Algorithms Appl. 16(2), 283\u2013315 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"133_CR21","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"133_CR22","doi-asserted-by":"crossref","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Krawczyk, T., Walczak, B.: Extending partial representations of function graphs and permutation graphs. In: Algorithms\u201420th Annual European Symposium, ESA 2012, Lecture Notes in Computer Science, vol. 7501, pp. 671\u2013682. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33090-2_58"},{"key":"133_CR23","doi-asserted-by":"crossref","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Rutter, I., Saitoh, T., Saumell, M., Vysko\u010dil, T.: Extending partial representations of proper and unit interval graphs. In: Algorithm Theory\u201414th Scandinavian Symposium and Workshops, SWAT 2014, Lecture Notes in Computer Science, vol. 8503, pp. 253\u2013264. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-08404-6_22"},{"key":"133_CR24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2015.02.007","volume":"576","author":"P Klav\u00edk","year":"2015","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Saitoh, T.: Extending partial representations of subclasses of chordal graphs. Theor. Comput. Sci. 576, 85\u2013101 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"133_CR25","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Saitoh, T., Vyskocil, T.: Extending partial representations of interval graphs. CoRR (2013). arXiv:1306.2182"},{"key":"133_CR26","doi-asserted-by":"crossref","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Vysko\u010dil, T.: Extending partial representations of interval graphs. In: Theory and Applications of Models of Computation\u20148th Annual Conference, TAMC 2011, Lecture Notes in Computer Science, vol. 6648, pp. 276\u2013285. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-20877-5_28"},{"key":"133_CR27","unstructured":"Klav\u00edk, P., Otachi, Y., \u0160ejnoha, J.: On the classes of interval graphs of limited nesting and count of lengths. CoRR (2015). arXiv:1510.03998"},{"key":"133_CR28","doi-asserted-by":"crossref","unstructured":"Klav\u00edk, P., Saumell, M.: Minimal obstructions for partial representations of interval graphs. In: Algorithms and Computation\u201425th International Symposium, ISAAC 2014, Lecture Notes in Computer Science, vol. 8889, pp. 401\u2013413. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-13075-0_32"},{"issue":"5","key":"133_CR29","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1142\/S0129054106004261","volume":"17","author":"M Patrignani","year":"2006","unstructured":"Patrignani, M.: On extending a partial straight-line drawing. Int. J. Found. Comput. Sci. 17(5), 1061\u20131070 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"133_CR30","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF00160932","volume":"28","author":"M Pirlot","year":"1990","unstructured":"Pirlot, M.: Minimal representation of a semiorder. Theory Decis. 28, 109\u2013141 (1990)","journal-title":"Theory Decis."},{"issue":"3","key":"133_CR31","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0166-218X(91)90057-4","volume":"31","author":"M Pirlot","year":"1991","unstructured":"Pirlot, M.: Synthetic description of a semiorder. Discret. Appl. Math. 31(3), 299\u2013308 (1991)","journal-title":"Discret. Appl. Math."},{"key":"133_CR32","unstructured":"Roberts, F.S.: Representations of Indifference Relations. Ph.D. Thesis, Stanford University (1968)"},{"key":"133_CR33","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"FS Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, London (1969)"},{"issue":"2","key":"133_CR34","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"133_CR35","unstructured":"Soulignac, F.J.: Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. CoRR (2014). arXiv:1408.3443"},{"key":"133_CR36","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Field Institute Monographs (2003)","DOI":"10.1090\/fim\/019"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0133-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0133-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0133-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:23Z","timestamp":1559072843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0133-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,25]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["133"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0133-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,25]]}}}