{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:35:00Z","timestamp":1787506500094,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030044138","type":"print"},{"value":"9783030044145","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-030-04414-5_22","type":"book-chapter","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T13:20:45Z","timestamp":1545052845000},"page":"317-330","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On Contact Graphs of Paths on a Grid"],"prefix":"10.1007","author":[{"given":"Zakir","family":"Deniz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esther","family":"Galby","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Munaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernard","family":"Ries","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-319-12340-0_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"N Aerts","year":"2014","unstructured":"Aerts, N., Felsner, S.: Vertex contact graphs of paths on a grid. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 56\u201368. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-12340-0_5"},{"issue":"4","key":"22_CR2","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00373-017-1791-6","volume":"33","author":"L Alc\u00f3n","year":"2017","unstructured":"Alc\u00f3n, L., Bonomo, F., Mazzoleni, M.P.: Vertex intersection graphs of paths on a grid: characterization within block graphs. Graphs Comb. 33(4), 653\u2013664 (2017)","journal-title":"Graphs Comb."},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.7155\/jgaa.00253","volume":"16","author":"A Asinowski","year":"2012","unstructured":"Asinowski, A., Cohen, E., Golumbic, M.C., Limouzy, V., Lipshteyn, M., Stern, M.: Vertex intersection graphs of paths on a grid. J. Graph Algorithms Appl. 16, 129\u2013150 (2012)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"22_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"LW Beineke","year":"1970","unstructured":"Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory 9(2), 129\u2013135 (1970)","journal-title":"J. Comb. Theory"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-25870-1_29","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Chaplick","year":"2011","unstructured":"Chaplick, S., Cohen, E., Stacho, J.: Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 319\u2013330. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25870-1_29"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-642-45043-3_13","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Chaplick","year":"2013","unstructured":"Chaplick, S., Kobourov, S.G., Ueckerdt, T.: Equilateral L-contact graphs. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 139\u2013151. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45043-3_13"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-36763-2_16","volume-title":"Graph Drawing","author":"S Chaplick","year":"2013","unstructured":"Chaplick, S., Ueckerdt, T.: Planar graphs as VPG-graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 174\u2013186. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36763-2_16"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.dam.2014.06.020","volume":"178","author":"E Cohen","year":"2014","unstructured":"Cohen, E., Golumbic, M.C., Ries, B.: Characterizations of cographs as intersection graphs of paths on a grid. Discrete Appl. Math. 178, 46\u201357 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"22_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s11083-015-9349-9","volume":"33","author":"E Cohen","year":"2016","unstructured":"Cohen, E., Golumbic, M.C., Trotter, W.T., Wang, R.: Posets and VPG graphs. Order 33(1), 39\u201349 (2016)","journal-title":"Order"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-46648-7_35","volume-title":"Graph Drawing","author":"N de Castro","year":"1999","unstructured":"de Castro, N., Cobos, F.J., Dana, J.C., M\u00e1rquez, A., Noy, M.: Triangle-free planar graphs as segments intersection graphs. In: Kratochv\u00edyl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 341\u2013350. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-46648-7_35"},{"issue":"4","key":"22_CR11","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s00453-006-0157-x","volume":"47","author":"H de Fraysseix","year":"2007","unstructured":"de Fraysseix, H., de Mendez, P.O.: Representations by contact and intersection of segments. Algorithmica 47(4), 453\u2013463 (2007)","journal-title":"Algorithmica"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Deniz, Z., Munaro, A., Galby, E., Ries, B.: On contact graphs of paths on a grid. arXiv:1803.03468 (2018)","DOI":"10.1007\/978-3-030-04414-5_22"},{"key":"22_CR13","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.dam.2016.01.028","volume":"2016","author":"S Felsner","year":"2016","unstructured":"Felsner, S., Knauer, K., Mertzios, G.B., Ueckerdt, T.: Intersection graphs of L-shapes and segments in the plane. Discrete Appl. Math. 2016, 48\u201355 (2016)","journal-title":"Discrete Appl. Math."},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.dam.2016.07.007","volume":"215","author":"M Francis","year":"2016","unstructured":"Francis, M., Lahiri, A.: VPG and EPG bend-numbers of Halin graphs. Discrete Appl. Math. 215, 95\u2013105 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"22_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified $$ NP$$-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR17","doi-asserted-by":"publisher","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, 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"22_CR18","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00373-012-1133-7","volume":"29","author":"MC Golumbic","year":"2013","unstructured":"Golumbic, M.C., Ries, B.: On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs. Graphs Comb. 29(3), 499\u2013517 (2013)","journal-title":"Graphs Comb."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Gon\u00e7alves, D., Isenmann, L., Pennarun, C.: Planar graphs as L-intersection or L-contact graphs. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2018, pp. 172\u2013184. Society for Industrial and Applied Mathematics (2018)","DOI":"10.1137\/1.9781611975031.12"},{"issue":"C","key":"22_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.dam.2014.07.015","volume":"179","author":"D Heldt","year":"2014","unstructured":"Heldt, D., Knauer, K., Ueckerdt, T.: On the bend-number of planar and outerplanar graphs. Discrete Appl. Math. 179(C), 109\u2013119 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"22_CR21","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1006\/jctb.1998.1846","volume":"74","author":"P Hlin\u011bn\u00fd","year":"1998","unstructured":"Hlin\u011bn\u00fd, P.: Classes and recognition of curve contact graphs. J. Comb. Theory Ser. B 74(1), 87\u2013103 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(97)00075-9","volume":"81","author":"P Hlin\u011bn\u00fd","year":"1998","unstructured":"Hlin\u011bn\u00fd, P.: The maximal clique and colourability of curve contact graphs. Discrete Appl. Math. 81(1), 59\u201368 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"22_CR23","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0012-365X(00)00263-6","volume":"235","author":"P Hlin\u011bn\u00fd","year":"2001","unstructured":"Hlin\u011bn\u00fd, P.: Contact graphs of line segments are $$ NP$$-complete. Discrete Math. 235(1\u20133), 95\u2013106 (2001)","journal-title":"Discrete Math."},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Kobourov, S., Ueckerdt, T., Verbeek, K.: Combinatorial and geometric properties of planar Laman graphs. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2013, pp. 1668\u20131678. Society for Industrial and Applied Mathematics (2013)","DOI":"10.1137\/1.9781611973105.120"},{"issue":"7","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1016\/j.disc.2007.04.009","volume":"308","author":"VP Korzhik","year":"2008","unstructured":"Korzhik, V.P.: Minimal non-1-planar graphs. Discrete Math. 308(7), 1319\u20131327 (2008)","journal-title":"Discrete Math."},{"issue":"9","key":"22_CR26","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R Tamassia","year":"1989","unstructured":"Tamassia, R., Tollis, I.G.: Planar grid embedding in linear time. IEEE Trans. Circuits Syst. 36(9), 1230\u20131234 (1989)","journal-title":"IEEE Trans. Circuits Syst."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04414-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T09:19:52Z","timestamp":1710235192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04414-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030044138","9783030044145"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04414-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"18 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Barcelona","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dccg.upc.edu\/gd2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.25","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.92","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The book also contains 1 full invited paper and 1 contest report","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}