{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:18Z","timestamp":1758586218150,"version":"3.44.0"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_22","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:44Z","timestamp":1758498344000},"page":"295-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Simultaneous Contact Representations of\u00a0Planar Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2620-6133","authenticated-orcid":false,"given":"Jan","family":"Kratochv\u00edl","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-0097","authenticated-orcid":false,"given":"Melanie","family":"Reihl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2014.11.016","volume":"575","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and partitioned book embedding problems. Theoret. Comput. Sci. 575, 71\u201389 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.11.016","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"22_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(93)90354-V","volume":"114","author":"S Bellantoni","year":"1993","unstructured":"Bellantoni, S., Ben-Arroyo Hartman, I., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity. Discret. Math. 114(1\u20133), 41\u201349 (1993). https:\/\/doi.org\/10.1016\/0012-365X(93)90354-V","journal-title":"Discret. Math."},{"key":"22_CR3","doi-asserted-by":"publisher","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2) (2015). https:\/\/doi.org\/10.1145\/2738054","DOI":"10.1145\/2738054"},{"key":"22_CR4","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"22_CR5","doi-asserted-by":"publisher","unstructured":"Bouchet, A.: Reducing prime graphs and recognizing circle graphs. Comb. 7(3), 243\u2013254 (1987). https:\/\/doi.org\/10.1007\/BF02579301","DOI":"10.1007\/BF02579301"},{"key":"22_CR6","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","author":"A Brandstaedt","year":"1999","unstructured":"Brandstaedt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. Soc. Ind. Appl. Math. (1999). https:\/\/doi.org\/10.1137\/1.9780898719796","journal-title":"Soc. Ind. Appl. Math."},{"issue":"2","key":"22_CR7","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0406017","volume":"6","author":"GR Brightwell","year":"1993","unstructured":"Brightwell, G.R., Scheinerman, E.R.: Representations of planar graphs. SIAM J. Discret. Math. 6(2), 214\u2013229 (1993). https:\/\/doi.org\/10.1137\/0406017","journal-title":"SIAM J. Discret. Math."},{"key":"22_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-319-12340-0_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Chaplick","year":"2014","unstructured":"Chaplick, S., Dorbec, P., Kratochv\u00edl, J., Montassier, M., Stacho, J.: Contact representations of planar graphs: extending a partial representation is hard. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 139\u2013151. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-12340-0_12"},{"issue":"4","key":"22_CR9","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1002\/JGT.22436","volume":"91","author":"S Chaplick","year":"2019","unstructured":"Chaplick, S., Fulek, R., Klav\u00edk, P.: Extending partial representations of circle graphs. J. Graph Theory 91(4), 365\u2013394 (2019). https:\/\/doi.org\/10.1002\/JGT.22436","journal-title":"J. Graph Theory"},{"key":"22_CR10","unstructured":"Chaplick, S., Itoh, T., Liotta, G., Ma, K.L., Rutter, I.: Trends and perspectives in graph drawing and network visualization. In: NII Shonan Meeting Report No. 171 (2020)"},{"key":"22_CR11","doi-asserted-by":"publisher","unstructured":"Dagan, I., Golumbic, M.C., Pinter, R.Y.: Trapezoid graphs and their coloring. Discret. Appl. Math. 21(1), 35\u201346 (1988). https:\/\/doi.org\/10.1016\/0166-218X(88)90032-7","DOI":"10.1016\/0166-218X(88)90032-7"},{"key":"22_CR12","doi-asserted-by":"publisher","unstructured":"Estrella-Balderrama, A., Gassner, E., J\u00fcnger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: Graph Drawing, 15th International Symposium, GD 2007. LNCS, vol.\u00a04875, pp. 280\u2013290. Springer (2007). https:\/\/doi.org\/10.1007\/978-3-540-77537-9_28","DOI":"10.1007\/978-3-540-77537-9_28"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Even, S., Pnueli, A., Lempel, A.: Permutation graphs and transitive graphs. J. ACM 19(3), 400\u2013410 (1972). https:\/\/doi.org\/10.1145\/321707.321710","DOI":"10.1145\/321707.321710"},{"key":"22_CR14","doi-asserted-by":"publisher","unstructured":"Fiala, J., Rutter, I., Stumpf, P., Zeman, P.: Extending partial representations of circular-arc graphs. In: Graph-Theoretic Concepts in Computer Science - 21st International Symposium, WG 2022. LNCS, vol. 13453, pp. 230\u2013243. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_17","DOI":"10.1007\/978-3-031-15914-5_17"},{"key":"22_CR15","unstructured":"de\u00a0Fraysseix, H., Ossona de Mendez, P., Pach, J.: Representation of planar graphs by segments. Intuitive Geom. 63 (2001)"},{"key":"22_CR16","doi-asserted-by":"publisher","unstructured":"de\u00a0Fraysseix, H., Ossona de Mendez, P., Rosenstiehl, P.: On Triangle contact graphs. Comb., Probab. Comput. 3(2), 233\u2013246 (1994). https:\/\/doi.org\/10.1017\/S0963548300001139","DOI":"10.1017\/S0963548300001139"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/11917496_29","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E Gassner","year":"2006","unstructured":"Gassner, E., J\u00fcnger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous graph embeddings with fixed edges. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 325\u2013335. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11917496_29"},{"issue":"5\u20136","key":"22_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0020-0190(00)00025-9","volume":"73","author":"F Gavril","year":"2000","unstructured":"Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Inf. Process. Lett. 73(5\u20136), 181\u2013188 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00025-9","journal-title":"Inf. Process. Lett."},{"key":"22_CR19","doi-asserted-by":"publisher","unstructured":"Golumbic, M.C.: Algorithmic aspects of intersection graphs and representation hypergraphs. Graphs Comb. 4(1), 307\u2013321 (1988). https:\/\/doi.org\/10.1007\/BF01864170","DOI":"10.1007\/BF01864170"},{"issue":"1","key":"22_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"I Hartman","year":"1991","unstructured":"Hartman, I., Newman, I., Ziv, R.: On grid intersection graphs. Discret. Math. 87(1), 41\u201352 (1991). https:\/\/doi.org\/10.1016\/0012-365X(91)90069-E","journal-title":"Discret. Math."},{"key":"22_CR21","doi-asserted-by":"publisher","unstructured":"Hlin\u011bn\u00fd, P.: Classes and recognition of curve contact graphs$$ ^{\\text{,} }$$. J. Comb. Theory B 74(1), 87\u2013103 (1998). https:\/\/doi.org\/10.1006\/jctb.1998.1846","DOI":"10.1006\/jctb.1998.1846"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P.: Contact graphs of line segments are NP-complete. Discret. Math. 235(1-3), 95\u2013106 (2001). https:\/\/doi.org\/10.1016\/S0012-365X(00)00263-6","DOI":"10.1016\/S0012-365X(00)00263-6"},{"key":"22_CR23","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Paul, W.J., Valiant, L.G.: On Time versus Space and Related Problems. In: 16th Annual Symposium on Foundations of Computer Science FOCS 1975, pp. 57\u201364. IEEE Computer Society (1975). https:\/\/doi.org\/10.1109\/SFCS.1975.23","DOI":"10.1109\/SFCS.1975.23"},{"key":"22_CR24","doi-asserted-by":"publisher","unstructured":"Jampani, K.R., Lubiw, A.: Simultaneous interval graphs. In: Algorithms and Computation - 21st International Symposium, ISAAC 2010. LNCS, vol.\u00a06506, pp. 206\u2013217. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-17517-6_20","DOI":"10.1007\/978-3-642-17517-6_20"},{"issue":"2","key":"22_CR25","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.7155\/jgaa.00259","journal-title":"J. Graph Algorithms Appl."},{"key":"22_CR26","doi-asserted-by":"publisher","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Krawczyk, T., Walczak, B.: Extending partial representations of function graphs and permutation graphs. In: Algorithms - 20th Annual European Symposium, ESA 2012. LNCS, vol.\u00a07501, pp. 671\u2013682. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-33090-2_58","DOI":"10.1007\/978-3-642-33090-2_58"},{"key":"22_CR27","doi-asserted-by":"publisher","unstructured":"Klav\u00edk, P.: Extending partial representations of proper and unit interval graphs. Algorithmica 77(4), 1071\u20131104 (2017). https:\/\/doi.org\/10.1007\/s00453-016-0133-z","DOI":"10.1007\/s00453-016-0133-z"},{"key":"22_CR28","doi-asserted-by":"publisher","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Vyskocil, T.: Extending partial representations of interval graphs. In: Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011. LNCS, vol.\u00a06648, pp. 276\u2013285. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-20877-5_28","DOI":"10.1007\/978-3-642-20877-5_28"},{"key":"22_CR29","first-page":"141","volume":"88","author":"P Koebe","year":"1936","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Verh. S\u00e4chs. Akad. Leipzig 88, 141\u2013164 (1936)","journal-title":"Ber. Verh. S\u00e4chs. Akad. Leipzig"},{"issue":"3","key":"22_CR30","doi-asserted-by":"publisher","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. Discret. Appl. Math. 52(3), 233\u2013252 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90143-0","journal-title":"Discret. Appl. Math."},{"key":"22_CR31","doi-asserted-by":"publisher","unstructured":"Kratochv\u00edl, J.: Intersection graphs of noncrossing arc-connected sets in the plane. In: Graph Drawing, Symposium on Graph Drawing, GD \u201996. LNCS, vol.\u00a01190, pp. 257\u2013270. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-62495-3_53","DOI":"10.1007\/3-540-62495-3_53"},{"key":"22_CR32","doi-asserted-by":"publisher","unstructured":"Krawczyk, T., Walczak, B.: Extending partial representations of trapezoid graphs. In: Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017. LNCS, vol. 10520, pp. 358\u2013371. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_27","DOI":"10.1007\/978-3-319-68705-6_27"},{"key":"22_CR33","doi-asserted-by":"publisher","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica 37(2), 93\u2013147 (2003). https:\/\/doi.org\/10.1007\/s00453-003-1032-7","DOI":"10.1007\/s00453-003-1032-7"},{"key":"22_CR34","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics in intersection graph theory. Soc. Ind. Appl. Math. (1999)","DOI":"10.1137\/1.9780898719802"},{"key":"22_CR35","unstructured":"M\u00fcnch, M., I., R., P., S.: Partial and simultaneous transitive orientations via modular decompositions. In: 33rd International Symposium on Algorithms and Computation, ISAAC 2022, LIPIcs, pp. 1\u201316. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"4","key":"22_CR36","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1007\/s00453-023-01188-y","volume":"86","author":"M M\u00fcnch","year":"2024","unstructured":"M\u00fcnch, M., Rutter, I., Stumpf, P.: Partial and simultaneous transitive orientations via modular decompositions. Algorithmica 86(4), 1263\u20131292 (2024). https:\/\/doi.org\/10.1007\/s00453-023-01188-y","journal-title":"Algorithmica"},{"issue":"1","key":"22_CR37","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problem. SIAM J. Comput. 8(1), 111\u2013114 (1979). https:\/\/doi.org\/10.1137\/0208008","journal-title":"SIAM J. Comput."},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"Roberts, F.: Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, The IMA Volumes in Mathematics and its Applications, vol.\u00a017. Springer (1989)","DOI":"10.1007\/978-1-4684-6381-1"},{"key":"22_CR39","doi-asserted-by":"publisher","unstructured":"Rutter, I., Strash, D., Stumpf, P., Vollmer, M.: Simultaneous representation of proper and unit interval graphs. In: Algorithms - 20th Annual European Symposium, ESA 2019. LIPIcs, vol.\u00a0144, pp. 1\u201315. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.80","DOI":"10.4230\/LIPIcs.ESA.2019.80"},{"key":"22_CR40","doi-asserted-by":"publisher","unstructured":"Rutter, I., Stumpf, P.: Simultaneous representation of interval graphs in the sunflower case. In: 31st Annual European Symposium on Algorithms - ESA 2023. LIPIcs, vol.\u00a0274, pp. 1\u201315. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.90","DOI":"10.4230\/LIPICS.ESA.2023.90"},{"key":"22_CR41","doi-asserted-by":"publisher","unstructured":"Spinrad, J.P.: Recognition of circle graphs. J. Algorithms 16(2), 264\u2013282 (1994). https:\/\/doi.org\/10.1006\/jagm.1994.1012","DOI":"10.1006\/jagm.1994.1012"},{"key":"22_CR42","unstructured":"Stumpf, P.F.: Partial representation extension and simultaneous representation of intersection graphs. Phd thesis, University of Passau, Passau, Germany (2023)"},{"key":"22_CR43","doi-asserted-by":"publisher","unstructured":"Tucker, A.C.: An efficient test for circular-arc graphs. SIAM J. Comput. 9(1), 1\u201324 (1980). https:\/\/doi.org\/10.1137\/0209001","DOI":"10.1137\/0209001"},{"key":"22_CR44","doi-asserted-by":"publisher","unstructured":"Zhang, P., et al.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Comput. Appl. Biosci. 10(3), 309\u2013317 (1994). https:\/\/doi.org\/10.1093\/bioinformatics\/10.3.309","DOI":"10.1093\/bioinformatics\/10.3.309"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:47Z","timestamp":1758498347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}