{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:20Z","timestamp":1759637840548},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_27","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"358-371","source":"Crossref","is-referenced-by-count":9,"title":["Extending Partial Representations of Trapezoid Graphs"],"prefix":"10.1007","author":[{"given":"Tomasz","family":"Krawczyk","sequence":"first","affiliation":[]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"27_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. ACM Trans. Algorithms 11(4), Article 32 (2015)","DOI":"10.1145\/2629341"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), Article 16 (2016)","DOI":"10.1145\/2738054"},{"issue":"3","key":"27_CR3","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 graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-319-03841-4_12","volume-title":"Graph Drawing","author":"S Chaplick","year":"2013","unstructured":"Chaplick, S., Fulek, R., Klav\u00edk, P.: Extending partial representations of circle graphs. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 131\u2013142. Springer, Cham (2013). doi: 10.1007\/978-3-319-03841-4_12"},{"issue":"1","key":"27_CR5","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(82)90167-4","volume":"38","author":"O Cogis","year":"1982","unstructured":"Cogis, O.: On the Ferrers dimension of a digraph. Discrete Math. 38(1), 47\u201352 (1982)","journal-title":"Discrete Math."},{"issue":"1","key":"27_CR6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R Cole","year":"2001","unstructured":"Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in $$O(E\\log D)$$ O ( E log D ) time. Combinatorica 21(1), 5\u201312 (2001)","journal-title":"Combinatorica"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in Algebra and Programming \u2014 CAAP\u201994","author":"A Cournier","year":"1994","unstructured":"Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol. 787, pp. 68\u201384. Springer, Heidelberg (1994). doi: 10.1007\/BFb0017474"},{"issue":"1","key":"27_CR8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I Dagan","year":"1988","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discrete Appl. Math. 21(1), 35\u201346 (1988)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"27_CR9","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."},{"issue":"3","key":"27_CR10","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B Dushnik","year":"1941","unstructured":"Dushnik, B., Miller, E.W.: Partially ordered sets. Am. J. Math. 63(3), 600\u2013610 (1941)","journal-title":"Am. J. Math."},{"issue":"4","key":"27_CR11","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"27_CR12","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/S089548019121885X","volume":"7","author":"S Felsner","year":"1994","unstructured":"Felsner, S., Habib, M., M\u00f6hring, R.H.: On the interplay between interval dimension and dimension. SIAM J. Discrete Math. 7(1), 22\u201340 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"27_CR13","doi-asserted-by":"crossref","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 43(2), 156\u2013160 (2003)","journal-title":"J. Graph Theory"},{"issue":"1\u20132","key":"27_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. 18(1\u20132), 25\u201366 (1967)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"27_CR15","first-page":"1370","volume":"254","author":"A Ghouila-Houri","year":"1962","unstructured":"Ghouila-Houri, A.: Caract\u00e9risation des graphes non orient\u00e9s dont on peut orienter les arr\u00eates de mani\u00e8re \u00e0 obtenir le graphe d\u2019une relation d\u2019ordre. C. R. Acad. Sci. 254, 1370\u20131371 (1962)","journal-title":"C. R. Acad. Sci."},{"key":"27_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. Canad. J. Math. 16, 539\u2013548 (1964)","journal-title":"Canad. J. Math."},{"issue":"3","key":"27_CR17","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BF02253207","volume":"18","author":"MC Golumbic","year":"1977","unstructured":"Golumbic, M.C.: The complexity of comparability graph recognition and coloring. Computing 18(3), 199\u2013208 (1977)","journal-title":"Computing"},{"key":"27_CR18","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"issue":"2\u20133","key":"27_CR19","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(91)90010-Y","volume":"88","author":"M Habib","year":"1991","unstructured":"Habib, M., Kelly, D., M\u00f6hring, R.H.: Interval dimension is a comparability invariant. Discrete Math. 88(2\u20133), 211\u2013229 (1991)","journal-title":"Discrete Math."},{"key":"27_CR20","unstructured":"James, L.O., Stanton, R.G., Cowan, D.D.: Graph decomposition for undirected graphs. In: Hoffman, F., Levow, R.B., Thomas, R.S.D. (eds.) 3rd Southeastern Conference on Combinatorics, Graph Theory, and Computing (CGTC 1972). Congressus Numerantium, vol. 6, pp. 281\u2013290. Utilitas Mathematica, Winnipeg (1972)"},{"issue":"3","key":"27_CR21","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"RJ Kang","year":"2012","unstructured":"Kang, R.J., M\u00fcller, T.: Sphere and dot product representations of graphs. Discrete Comput. Geom. 47(3), 548\u2013568 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"27_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-642-33090-2_58","volume-title":"Algorithms \u2013 ESA 2012","author":"P Klav\u00edk","year":"2012","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Krawczyk, T., Walczak, B.: Extending partial representations of function graphs and permutation graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 671\u2013682. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-33090-2_58"},{"issue":"4","key":"27_CR23","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1007\/s00453-016-0133-z","volume":"77","author":"P Klav\u00edk","year":"2017","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. Algorithmica 77(4), 1071\u20131104 (2017)","journal-title":"Algorithmica"},{"key":"27_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."},{"issue":"3","key":"27_CR25","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1007\/s00453-016-0186-z","volume":"78","author":"P Klav\u00edk","year":"2017","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Saitoh, T., Vysko\u010dil, T.: Extending partial representations of interval graphs. Algorithmica 78(3), 945\u2013967 (2017)","journal-title":"Algorithmica"},{"key":"27_CR26","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. 6648, pp. 276\u2013285. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20877-5_28"},{"issue":"1","key":"27_CR27","doi-asserted-by":"crossref","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 52(1), 67\u201378 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"27_CR28","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52(3), 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"27_CR29","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62(2), 289\u2013315 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"27_CR30","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/jagm.1994.1034","volume":"17","author":"TH Ma","year":"1994","unstructured":"Ma, T.H., Spinrad, J.P.: On the 2-chain subgraph cover and related problems. J. Algorithms 17(2), 251\u2013268 (1994)","journal-title":"J. Algorithms"},{"issue":"4","key":"27_CR31","doi-asserted-by":"crossref","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 49(4), 313\u2013324 (2005)","journal-title":"J. Graph Theory"},{"issue":"2","key":"27_CR32","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"RM McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"27_CR33","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"issue":"11","key":"27_CR34","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1016\/j.dam.2011.03.023","volume":"159","author":"GB Mertzios","year":"2011","unstructured":"Mertzios, G.B., Corneil, D.G.: Vertex splitting and the recognition of trapezoid graphs. Discrete Appl. Math. 159(11), 1131\u20131147 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"27_CR35","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."},{"issue":"2","key":"27_CR36","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1974","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1974)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"27_CR37","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR38","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: Johnson, D. (ed.) 1st Annual ACM-SIAM Symposium Discrete Algorithms (SODA 1990), pp. 138\u2013148. SIAM, Philadelphia (1990)"},{"issue":"2","key":"27_CR39","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"JP Spinrad","year":"1994","unstructured":"Spinrad, J.P.: Recognition of circle graphs. J. Algorithms 16(2), 264\u2013282 (1994)","journal-title":"J. Algorithms"},{"key":"27_CR40","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations, Field Institute Monographs, vol. 19. AMS, Providence (2003)","DOI":"10.1090\/fim\/019"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T12:11:49Z","timestamp":1570277509000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}