{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:51:11Z","timestamp":1777668671052,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            We give an algorithm to morph between two planar orthogonal drawings of a graph, preserving planarity and orthogonality. The morph uses a quadratic number of steps, where each step is a linear morph (a linear interpolation between two drawings). This is the first algorithm to provide planarity-preserving morphs with well-behaved complexity for a significant class of graph drawings. Our method is to morph until each edge is represented by a sequence of segments, with corresponding segments parallel in the two drawings. Then, in a result of independent interest, we morph such\n            <jats:italic>parallel<\/jats:italic>\n            planar orthogonal drawings, preserving edge directions and planarity.\n          <\/jats:p>","DOI":"10.1145\/2500118","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T18:14:28Z","timestamp":1380651268000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Morphing orthogonal planar graph drawings"],"prefix":"10.1145","volume":"9","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Lubiw","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Petrick","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Spriggs","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,10,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alt H. and Guibas L. 1999. Discrete geometric shapes: Matching interpolation and approximation. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Science Publishers B.V. North-Holland Amsterdam 121--153.  Alt H. and Guibas L. 1999. Discrete geometric shapes: Matching interpolation and approximation. In Handbook of Computational Geometry J.-R. Sack and J. Urrutia Eds. Elsevier Science Publishers B.V. North-Holland Amsterdam 121--153.","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90028-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1996.0018"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS","volume":"3153","author":"Biedl T.","year":"2004","unstructured":"Biedl , T. , Lubiw , A. , and Spriggs , M . 2004. Angles and lengths in reconfigurations of polygons and polyhedra . In Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS 2004 ). Lecture Notes in Computer Science , vol. 3153 , Springer, 748--759. Biedl, T., Lubiw, A., and Spriggs, M. 2004. Angles and lengths in reconfigurations of polygons and polyhedra. In Proceedings of the Symposium on Mathematical Foundations of Computer Science (MFCS 2004). Lecture Notes in Computer Science, vol. 3153, Springer, 748--759."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1519530.1519573"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_2"},{"key":"e_1_2_1_7_1","volume-title":"Drawing Graphs -- Methods and Models","author":"Branke J.","unstructured":"Branke , J. 2001. Dynamic graph drawing . In Drawing Graphs -- Methods and Models , D. Kaufmann and D. Wagner, Eds., Lecture Notes in Computer Science, vol. 2025 , Springer , 228--246. Branke, J. 2001. Dynamic graph drawing. In Drawing Graphs -- Methods and Models, D. Kaufmann and D. Wagner, Eds., Lecture Notes in Computer Science, vol. 2025, Springer, 228--246."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00025"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1944.11999082"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-0006-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"e_1_2_1_12_1","volume-title":"Origami, Polyhedra","author":"Demaine E. D.","unstructured":"Demaine , E. D. and O'Rourke , J. 2007. Geometric Folding Algorithms: Linkages , Origami, Polyhedra . Cambridge University Press . Demaine, E. D. and O'Rourke, J. 2007. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press."},{"key":"e_1_2_1_13_1","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista G.","year":"1999","unstructured":"Di Battista , G. , Eades , P. , Tamassia , R. , and Tollis , I . 1999 . Graph Drawing: Algorithms for the Visualization of Graphs . Prentice-Hall . Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. 1999. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794262847"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Eiglsperger M. Fekete S. and \n      Klau G\n  . \n  2001\n  . Orthogonal graph drawing. In Drawing Graphs -- Methods and Models D. Kaufmann and D. Wagner Eds. Lecture Notes in Computer Science vol. \n  2025 Springer 121--171.   Eiglsperger M. Fekete S. and Klau G. 2001. Orthogonal graph drawing. In Drawing Graphs -- Methods and Models D. Kaufmann and D. Wagner Eds. Lecture Notes in Computer Science vol. 2025 Springer 121--171.","DOI":"10.1007\/3-540-44969-8_6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Erten C. Kobourov S. and \n      Pitta C\n  . \n  2004\n  a. Intersection-free morphing of planar graphs. In Graph Drawing 2003 G. Liotta Ed. Lecture Notes in Computer Science vol. \n  2912 Springer 320--331.  Erten C. Kobourov S. and Pitta C. 2004a. Intersection-free morphing of planar graphs. In Graph Drawing 2003 G. Liotta Ed. Lecture Notes in Computer Science vol. 2912 Springer 320--331.","DOI":"10.1007\/978-3-540-24595-7_30"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997886"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(98)00202-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00057"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Friedrich C.\n     and \n      Houle M\n  . \n  2002\n  . Graph drawing in motion II. In Graph Drawing 2001 P. Mutzel M. J\u00fcnger and S. Leipert Eds. Lecture Notes in Computer Science vol. \n  2265 Springer 220--231.   Friedrich C. and Houle M. 2002. Graph drawing in motion II. In Graph Drawing 2001 P. Mutzel M. J\u00fcnger and S. Leipert Eds. Lecture Notes in Computer Science vol. 2265 Springer 220--231.","DOI":"10.1007\/3-540-45848-4_18"},{"key":"e_1_2_1_21_1","unstructured":"Gomes J. Darsa L. Costa B. and Velho L. 1999. Warping and Morphing of Graphical Objects. Morgan Kaufmann.   Gomes J. Darsa L. Costa B. and Velho L. 1999. Warping and Morphing of Graphical Objects. Morgan Kaufmann."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(00)00108-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/103016"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010017"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9145-7"},{"key":"e_1_2_1_26_1","volume-title":"Algorithms and Theory of Computation Handbook","author":"LaPaugh A.","unstructured":"LaPaugh , A. 1998. VLSI Layout Algorithms . In Algorithms and Theory of Computation Handbook , M. Atallah, Ed., CRC Press . LaPaugh, A. 1998. VLSI Layout Algorithms. In Algorithms and Theory of Computation Handbook, M. Atallah, Ed., CRC Press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00076-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00223"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109583"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jvlc.1995.1010"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 138--148","author":"Schnyder W.","year":"1990","unstructured":"Schnyder , W. 1990 . Embedding planar graphs on a grid . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 138--148 . Schnyder, W. 1990. Embedding planar graphs on a grid. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 138--148."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/502783.502784"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216030"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/31.34669"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90038-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214027"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2500118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:31Z","timestamp":1750232071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2500118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2500118"],"URL":"https:\/\/doi.org\/10.1145\/2500118","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}