{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:25:01Z","timestamp":1760441101753},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_58","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"671-682","source":"Crossref","is-referenced-by-count":21,"title":["Extending Partial Representations of Function Graphs and Permutation Graphs"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Klav\u00edk","sequence":"first","affiliation":[]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Krawczyk","sequence":"additional","affiliation":[]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Angelini, P., Di Battista, G., Frati, F., Jel\u00ednek, V., Kratochv\u00edl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: SODA 2010, pp. 202\u2013221 (2010)","DOI":"10.1137\/1.9781611973075.19"},{"key":"58_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inform. Process. Lett.\u00a08, 121\u2013123 (1979)","journal-title":"Inform. Process. Lett."},{"key":"58_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. 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. Sys. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Sys. Sci."},{"key":"58_CR4","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems (2011), http:\/\/arxiv.org\/abs\/1112.0245"},{"key":"58_CR5","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. ACM\u00a019, 400\u2013410 (1972)","journal-title":"J. ACM"},{"key":"58_CR6","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1002\/jgt.10088","volume":"43","author":"J. Fiala","year":"2003","unstructured":"Fiala, J.: NP-completeness of the edge precoloring extension problem on bipartite graphs. J. Graph Theory\u00a043, 156\u2013160 (2003)","journal-title":"J. Graph Theory"},{"key":"58_CR7","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungaricae\u00a018, 25\u201366 (1967)","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"58_CR8","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02253207","volume":"18","author":"M.C. Golumbic","year":"1977","unstructured":"Golumbic, M.C.: The complexity of comparability graph recognition and coloring. Computing\u00a018, 199\u2013208 (1977)","journal-title":"Computing"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980)","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"M.C. Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Math.\u00a043, 37\u201346 (1983)","journal-title":"Discrete Math."},{"key":"58_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-17517-6_20","volume-title":"Algorithms and Computation","author":"K.R. Jampani","year":"2010","unstructured":"Jampani, K.R., Lubiw, A.: Simultaneous Interval Graphs. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol.\u00a06506, pp. 206\u2013217. Springer, Heidelberg (2010)"},{"key":"58_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.7155\/jgaa.00259","volume":"16","author":"K.R. Jampani","year":"2012","unstructured":"Jampani, K.R., Lubiw, A.: The simultaneous representation problem for chordal, comparability and permutation graphs. Graph Algorithms Appl.\u00a016, 283\u2013315 (2012)","journal-title":"Graph Algorithms Appl."},{"key":"58_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-20877-5_28","volume-title":"Theory and Applications of Models of Computation","author":"P. Klav\u00edk","year":"2011","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Vysko\u010dil, T.: Extending Partial Representations of Interval Graphs. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 276\u2013285. Springer, Heidelberg (2011)"},{"key":"58_CR14","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","volume":"52","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J.: String graphs. II. recognizing string graphs is NP-hard. J. Combin. Theory Ser. B\u00a052, 67\u201378 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"58_CR15","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/malq.19670130104","volume":"13","author":"M.R. Krom","year":"1967","unstructured":"Krom, M.R.: The decision problem for a class of first-order formulas in which all disjunctions are binary. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik\u00a013, 15\u201320 (1967)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"58_CR16","first-page":"217","volume":"15","author":"K. Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sur le probl\u00e8me des courbes gauches en topologie. Fund. Math.\u00a015, 217\u2013283 (1930)","journal-title":"Fund. Math."},{"key":"58_CR17","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20085","volume":"49","author":"D. Marx","year":"2005","unstructured":"Marx, D.: NP-completeness of list coloring and precoloring extension on the edges of planar graphs. J. Graph Theory\u00a049, 313\u2013324 (2005)","journal-title":"J. Graph Theory"},{"key":"58_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math.\u00a0201, 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"58_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/11618058_34","volume-title":"Graph Drawing","author":"M. Patrignani","year":"2006","unstructured":"Patrignani, M.: On Extending a Partial Straight-Line Drawing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol.\u00a03843, pp. 380\u2013385. Springer, Heidelberg (2006)"},{"key":"58_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. In: STOC 2002, pp. 1\u20136 (2002)","DOI":"10.1145\/509907.509910"},{"key":"58_CR21","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Field Institute Monographs (2003)","DOI":"10.1090\/fim\/019"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:11:17Z","timestamp":1606187477000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}