{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T07:51:10Z","timestamp":1772005870492,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030358013","type":"print"},{"value":"9783030358020","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-35802-0_29","type":"book-chapter","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T23:02:50Z","timestamp":1574895770000},"page":"379-392","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9794-1928","authenticated-orcid":false,"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2886-9694","authenticated-orcid":false,"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,28]]},"reference":[{"issue":"1","key":"29_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23\u201349 (2018). https:\/\/doi.org\/10.7155\/jgaa.00457","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"29_CR2","doi-asserted-by":"publisher","first-page":"577","DOI":"10.7155\/jgaa.00479","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577\u2013606 (2018). https:\/\/doi.org\/10.7155\/jgaa.00479","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"TC Biedl","year":"1998","unstructured":"Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998)","journal-title":"Comput. Geom."},{"issue":"4","key":"29_CR4","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2500118","volume":"9","author":"TC Biedl","year":"2013","unstructured":"Biedl, T.C., Lubiw, A., Petrick, M., Spriggs, M.J.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4), 29:1\u201329:24 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s00453-012-9705-8","volume":"68","author":"T Bl\u00e4sius","year":"2014","unstructured":"Bl\u00e4sius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with flexibility constraints. Algorithmica 68(4), 859\u2013885 (2014)","journal-title":"Algorithmica"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.comgeo.2016.03.001","volume":"55","author":"T Bl\u00e4sius","year":"2016","unstructured":"Bl\u00e4sius, T., Lehmann, S., Rutter, I.: Orthogonal graph drawing with inflexible edges. Comput. Geom. 55, 26\u201340 (2016)","journal-title":"Comput. Geom."},{"issue":"6","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-319-03898-8_5","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Bonsma, P., Lokshtanov, D.: The fine details of fast dynamic programming over tree decompositions. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 41\u201353. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_5"},{"issue":"2","key":"29_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c$${}^{\\text{ k }}$$ n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-540-30140-0_16","volume-title":"Algorithms \u2013 ESA 2004","author":"H Chan","year":"2004","unstructured":"Chan, H.: A parameterized algorithm for upward planarity testing. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 157\u2013168. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30140-0_16"},{"key":"29_CR11","unstructured":"Chang, Y., Yen, H.: On bend-minimized orthogonal drawings of planar 3-graphs. In: SOCG 2017. LIPIcs, vol. 77, pp. 29:1\u201329:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"key":"29_CR12","volume-title":"Graph Drawing","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Upper Saddle River (1999)"},{"issue":"6","key":"29_CR13","doi-asserted-by":"publisher","first-page":"1764","DOI":"10.1137\/S0097539794262847","volume":"27","author":"G Di Battista","year":"1998","unstructured":"Di Battista, G., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764\u20131811 (1998)","journal-title":"SIAM J. Comput."},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Sketched representations and orthogonal planarity of bounded treewidth graphs. CoRR abs\/1908.05015 (2019). http:\/\/arxiv.org\/abs\/1908.05015","DOI":"10.1007\/978-3-030-35802-0_29"},{"issue":"4","key":"29_CR15","doi-asserted-by":"publisher","first-page":"1842","DOI":"10.1137\/070696854","volume":"23","author":"W Didimo","year":"2009","unstructured":"Didimo, W., Giordano, F., Liotta, G.: Upward spirality and upward planarity testing. SIAM J. Discrete Math. 23(4), 1842\u20131899 (2009). https:\/\/doi.org\/10.1137\/070696854","journal-title":"SIAM J. Discrete Math."},{"key":"29_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/3-540-49381-6_10","volume-title":"Algorithms and Computation","author":"W Didimo","year":"1998","unstructured":"Didimo, W., Liotta, G.: Computing orthogonal drawings in a variable embedding setting. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 80\u201389. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-49381-6_10"},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-030-04414-5_34","volume-title":"Graph Drawing and Network Visualization","author":"W Didimo","year":"2018","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: Bend-minimum orthogonal drawings in quadratic time. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 481\u2013494. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_34"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2018.08.003","volume":"99","author":"W Didimo","year":"2019","unstructured":"Didimo, W., Liotta, G., Patrignani, M.: HV-planarity: algorithms and complexity. J. Comput. Syst. Sci. 99, 72\u201390 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR19","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, Heidelberg (1999)"},{"issue":"2","key":"29_CR20","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","volume":"52","author":"V Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fellows, M.R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Whitesides, S., Wood, D.R.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267\u2013292 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"29_CR21","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jda.2006.12.008","volume":"6","author":"V Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms 6(2), 313\u2013323 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"29_CR22","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00453-004-1093-2","volume":"40","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica 40(1), 15\u201331 (2004)","journal-title":"Algorithmica"},{"key":"29_CR23","unstructured":"Duncan, C.A., Goodrich, M.T.: Planar orthogonal and polyline drawing algorithms. In: Handbook of Graph Drawing and Visualization, pp. 223\u2013246. Chapman and Hall\/CRC (2013)"},{"key":"29_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-642-54423-1_14","volume-title":"LATIN 2014: Theoretical Informatics","author":"S Durocher","year":"2014","unstructured":"Durocher, S., Felsner, S., Mehrabi, S., Mondal, D.: Drawing HV-restricted planar graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 156\u2013167. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_14"},{"issue":"2","key":"29_CR25","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(2), 601\u2013625 (2001)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"29_CR26","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1142\/S0129054106004285","volume":"17","author":"P Healy","year":"2006","unstructured":"Healy, P., Lynch, K.: Two fixed-parameter tractable algorithms for testing upward planarity. Int. J. Found. Comput. Sci. 17(5), 1095\u20131114 (2006). https:\/\/doi.org\/10.1142\/S0129054106004285","journal-title":"Int. J. Found. Comput. Sci."},{"key":"29_CR27","series-title":"LNCS","volume-title":"Treewidth, Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994)"},{"issue":"1","key":"29_CR28","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/ietisy\/E88-D.1.23","volume":"88\u2013D","author":"MS Rahman","year":"2005","unstructured":"Rahman, M.S., Egi, N., Nishizeki, T.: No-bend orthogonal drawings of subdivisions of planar triconnected cubic graphs. IEICE Trans. 88\u2013D(1), 23\u201330 (2005)","journal-title":"IEICE Trans."},{"issue":"3","key":"29_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"3","key":"29_CR30","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R Tamassia","year":"1987","unstructured":"Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"29_CR31","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/060667621","volume":"22","author":"X Zhou","year":"2008","unstructured":"Zhou, X., Nishizeki, T.: Orthogonal drawings of series-parallel graphs with minimum bends. SIAM J. Discrete Math. 22(4), 1570\u20131604 (2008)","journal-title":"SIAM J. Discrete Math."}],"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-35802-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T01:05:00Z","timestamp":1701133500000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-35802-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030358013","9783030358020"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-35802-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"28 November 2019","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":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/kam.mff.cuni.cz\/gd2019\/","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":"113","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":"34","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":"8","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":"30% - 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.11","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":"12.55","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":"This content has been made available to all.","name":"free","label":"Free to read"}]}}