{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T10:18:00Z","timestamp":1772792280456,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T00:00:00Z","timestamp":1495584000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ESF","award":["EUROGIGA GraDr"],"award-info":[{"award-number":["EUROGIGA GraDr"]}]},{"DOI":"10.13039\/501100004569","name":"MNiSW","doi-asserted-by":"crossref","award":["DI2013 000443"],"award-info":[{"award-number":["DI2013 000443"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Polish National Science Center","award":["UMO-2011\/03\/D\/ST6\/01370"],"award-info":[{"award-number":["UMO-2011\/03\/D\/ST6\/01370"]}]},{"name":"Polish National Science Center","award":["UMO-2015\/17\/B\/ST6\/01873"],"award-info":[{"award-number":["UMO-2015\/17\/B\/ST6\/01873"]}]},{"DOI":"10.13039\/501100003407","name":"MIUR","doi-asserted-by":"crossref","award":["2012C4E3KT 001"],"award-info":[{"award-number":["2012C4E3KT 001"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00453-017-0322-4","type":"journal-article","created":{"date-parts":[[2017,5,24]],"date-time":"2017-05-24T14:44:05Z","timestamp":1495637045000},"page":"2286-2323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The Partial Visibility Representation Extension Problem"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3501-4608","authenticated-orcid":false,"given":"Steven","family":"Chaplick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3303-8107","authenticated-orcid":false,"given":"Grzegorz","family":"Gu\u015bpiel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3313-1237","authenticated-orcid":false,"given":"Grzegorz","family":"Gutowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Krawczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"1","key":"322_CR1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0166-218X(92)90018-6","volume":"40","author":"T Andreae","year":"1992","unstructured":"Andreae, T.: Some results on visibility graphs. Discrete Appl. Math. 40(1), 5\u201317 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"322_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2629341","volume":"11","author":"P Angelini","year":"2015","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), 1\u201342 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"322_CR3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"KA Baker","year":"1972","unstructured":"Baker, K.A., Fishburn, P.C., Roberts, F.S.: Partial orders of dimension 2. Networks 2(1), 11\u201328 (1972)","journal-title":"Networks"},{"issue":"1","key":"322_CR4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/s00454-010-9310-z","volume":"45","author":"TC Biedl","year":"2011","unstructured":"Biedl, T.C.: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discrete Comput. Geom. 45(1), 141\u2013160 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"322_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2738054","volume":"12","author":"T Bl\u00e4sius","year":"2015","unstructured":"Bl\u00e4sius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. ACM Trans. Algorithms 12(2), 1\u201346 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"322_CR6","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/s00454-016-9831-1","volume":"57","author":"J Cardinal","year":"2017","unstructured":"Cardinal, J., Hoffmann, U.: Recognition and complexity of point visibility graphs. Discrete Comput. Geom. 57(1), 164\u2013178 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"322_CR7","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1137\/S0895480198343455","volume":"18","author":"Y-W Chang","year":"2004","unstructured":"Chang, Y.-W., Hutchinson, J.P., Jacobson, M.S., Lehel, J., West, D.B.: The bar visibility number of a graph. SIAM J. Discrete Math. 18(3), 462\u2013471 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"322_CR8","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: WG 2014: 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Nouan-le-Fuzelier, France, June 2014. Revised selected papers, pp. 139\u2013151 (2014)","DOI":"10.1007\/978-3-319-12340-0_12"},{"key":"322_CR9","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Fulek, R., Klav\u00edk, P.: Extending partial representations of circle graphs. In: GD 2013: 21st International Symposium on Graph Drawing, Bordeaux, France, September 2013. Revised selected papers, pp. 131\u2013142 (2013)","DOI":"10.1007\/978-3-319-03841-4_12"},{"key":"322_CR10","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Gu\u015bpiel, G., Gutowski, G., Krawczyk, T., Liotta, G.: The partial visibility representation extension problem. In: GD 2016: 24th International Symposium on Graph Drawing and Network Visualization, Athens, Greece, September 2016. Revised selected papers, pp. 266\u2013279 (2016)","DOI":"10.1007\/978-3-319-50106-2_21"},{"issue":"4","key":"322_CR11","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0020-0190(95)00020-D","volume":"54","author":"M Chrobak","year":"1995","unstructured":"Chrobak, M., Payne, T.H.: A linear-time algorithm for drawing a planar graph on a grid. Inf. Process. Lett. 54(4), 241\u2013246 (1995)","journal-title":"Inf. Process. Lett."},{"key":"322_CR12","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)"},{"key":"322_CR13","unstructured":"Di Battista, G., Frati, F.: A survey on small-area planar graph drawing (2014). arXiv:1410.1006"},{"issue":"2\u20133","key":"322_CR14","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G Battista Di","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61(2\u20133), 175\u2013198 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"322_CR15","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"322_CR16","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02187850","volume":"7","author":"G Battista Di","year":"1992","unstructured":"Di Battista, G., Tamassia, R., Tollis, I.G.: Area requirement and symmetry display of planar upward drawings. Discrete Comput. Geom. 7(1), 381\u2013401 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"322_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"3","key":"322_CR18","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M Berg de","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187\u2013205 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"322_CR19","unstructured":"de Fraysseix, H., de Mendez, P.O., Pach, J.: Representation of planar graphs by segments. In: Intuitive Geometry (Szeged, 1991), Volume\u00a063 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 109\u2013117 (1994)"},{"key":"322_CR20","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1017\/S0963548300001139","volume":"3","author":"H Fraysseix de","year":"1994","unstructured":"de Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3, 233\u2013246 (1994)","journal-title":"Comb. Probab. Comput."},{"key":"322_CR21","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: Small sets supporting F\u00e1ry embeddings of planar graphs. In: STOC 1988: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, pp. 426\u2013433 (1988)","DOI":"10.1145\/62212.62254"},{"issue":"1","key":"322_CR22","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H Fraysseix de","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"1","key":"322_CR23","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci. 38(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"322_CR24","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y.O., Las Vergnas, M., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319\u2013321 (1983)","journal-title":"Discrete Math."},{"key":"322_CR25","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229\u2013233 (1948)","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"322_CR26","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"2","key":"322_CR27","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01108622","volume":"12","author":"A Garg","year":"1995","unstructured":"Garg, A., Tamassia, R.: Upward planarity testing. Order 12(2), 109\u2013133 (1995)","journal-title":"Order"},{"issue":"2","key":"322_CR28","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/S0097539794277123","volume":"31","author":"A Garg","year":"2001","unstructured":"Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"322_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2543581.2543589","volume":"46","author":"SK Ghosh","year":"2013","unstructured":"Ghosh, S.K., Goswami, P.P.: Unsolved problems in visibility graphs of points, segments, and polygons. ACM Comput. Surv. 46(2), 1\u201329 (2013)","journal-title":"ACM Comput. Surv."},{"key":"322_CR30","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Proceedings of the GD 2000: 8th International Symposium on Graph Drawing, Colonial Williamsburg, VA, USA, September 2000, pp. 77\u201390 (2001)","DOI":"10.1007\/3-540-44541-2_8"},{"issue":"1","key":"322_CR31","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(91)90069-E","volume":"87","author":"IB-A Hartman","year":"1991","unstructured":"Hartman, I.B.-A., Newman, I., Ziv, R.: On grid intersection graphs. Discrete Math. 87(1), 41\u201352 (1991)","journal-title":"Discrete Math."},{"key":"322_CR32","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.tcs.2012.02.010","volume":"447","author":"X He","year":"2012","unstructured":"He, X., Wang, J.-J., Zhang, H.: Compact visibility representation of 4-connected plane graphs. Theor. Comput. Sci. 447, 62\u201373 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"322_CR33","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G Kant","year":"1997","unstructured":"Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theor. Comput. Sci. 172(1\u20132), 175\u2013193 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"322_CR34","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(97)00048-3","volume":"62","author":"G Kant","year":"1997","unstructured":"Kant, G., Liotta, G., Tamassia, R., Tollis, I.G.: Area requirement of visibility representations of trees. Inf. Process. Lett. 62(2), 81\u201388 (1997)","journal-title":"Inf. Process. Lett."},{"key":"322_CR35","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: Proceedings of the ESA 2012: 20th Annual European Symposium on Algorithms, Ljubljana, Slovenia, September 2012, pp. 671\u2013682 (2012)","DOI":"10.1007\/978-3-642-33090-2_58"},{"key":"322_CR36","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. Algorithmica 77(4), 1071\u20131104 (2017)","DOI":"10.1007\/s00453-016-0133-z"},{"key":"322_CR37","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":"322_CR38","doi-asserted-by":"crossref","unstructured":"Klav\u00edk, P., Kratochv\u00edl, J., Otachi, Y., Saitoh, T., Vysko\u010dil, T.: Extending partial representations of interval graphs. Algorithmica 1\u201323 (2016)","DOI":"10.1007\/s00453-016-0186-z"},{"key":"322_CR39","volume-title":"Kontaktprobleme der konformen Abbildung","author":"P Koebe","year":"1936","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Hirzel, Stuttgart (1936)"},{"issue":"2\u20133","key":"322_CR40","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0012-365X(87)90190-7","volume":"64","author":"F Luccio","year":"1987","unstructured":"Luccio, F., Mazzone, S., Wong, C.-K.: A note on visibility graphs. Discrete Math. 64(2\u20133), 209\u2013219 (1987)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"322_CR41","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0012-365X(93)90340-Y","volume":"117","author":"B Mohar","year":"1993","unstructured":"Mohar, B.: A polynomial time circle packing algorithm. Discrete Math. 117(1\u20133), 257\u2013263 (1993)","journal-title":"Discrete Math."},{"key":"322_CR42","doi-asserted-by":"crossref","unstructured":"Myers, E.W.: Efficient applicative data types. In: Proceedings of the POPL 84: 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, Salt Lake City, UT, USA, January 1984, pp. 66\u201375 (1984)","DOI":"10.1145\/800017.800517"},{"key":"322_CR43","unstructured":"Otten, R.H.J.M., van Wijk, J.G.: Graph representations in interactive layout design. In: Proceedings of the IEEE International Symposium on Circuits and Systems, New York, NY, USA, May 1978, pp. 914\u2013918 (1978)"},{"issue":"5","key":"322_CR44","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":"322_CR45","first-page":"259","volume":"2","author":"M Schlag","year":"1985","unstructured":"Schlag, M., Luccio, F., Maestrini, P., Lee, D.-T., Wong, C.-K.: A visibility problem in VLSI layout compaction. Adv. Comput. Res. 2, 259\u2013282 (1985)","journal-title":"Adv. Comput. Res."},{"issue":"2","key":"322_CR46","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.3230140202","volume":"14","author":"JA Storer","year":"1984","unstructured":"Storer, J.A.: On minimal-node-cost planar embeddings. Networks 14(2), 181\u2013212 (1984)","journal-title":"Networks"},{"issue":"4","key":"322_CR47","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1(4), 321\u2013341 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"322_CR48","doi-asserted-by":"crossref","first-page":"317","DOI":"10.7155\/jgaa.00260","volume":"16","author":"J-J Wang","year":"2012","unstructured":"Wang, J.-J., He, X.: Visibility representation of plane graphs with simultaneous bound for both width and height. J. Graph Algorithms Appl. 16(2), 317\u2013334 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"322_CR49","doi-asserted-by":"crossref","unstructured":"Wismath, S.K.: Characterizing bar line-of-sight graphs. In: Proceedings of the SCG 1985: 1st Annual Symposium on Computational Geometry, Baltimore, MD, USA, June 1985, pp. 147\u2013152 (1985)","DOI":"10.1145\/323233.323253"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0322-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0322-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0322-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T21:14:40Z","timestamp":1659042880000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0322-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,24]]},"references-count":49,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["322"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0322-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,24]]}}}