{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:50:00Z","timestamp":1764557400408},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T00:00:00Z","timestamp":1486684800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00454-017-9867-x","type":"journal-article","created":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T19:06:25Z","timestamp":1486753585000},"page":"313-344","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Computing the Flip Distance Between Triangulations"],"prefix":"10.1007","volume":"58","author":[{"given":"Iyad","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Eric","family":"Sedgwick","sequence":"additional","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,10]]},"reference":[{"key":"9867_CR1","unstructured":"Aichholzer, O., Alvarez, V., Hackl, T., Pilz, A., Speckmann, B., Vogtenhuber, B.: An improved lower bound on the minimum number of triangulations. In: 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics, vol. 51, pp. 7:1\u20137:16. Leibniz-Zentrum fuer Informatik, Dagstuhl (2016)"},{"issue":"2","key":"9867_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.comgeo.2004.02.003","volume":"29","author":"O Aichholzer","year":"2004","unstructured":"Aichholzer, O., Hurtado, F., Noy, M.: A lower bound on the number of triangulations of planar point sets. Comput. Geom. 29(2), 135\u2013145 (2004)","journal-title":"Comput. Geom."},{"issue":"2","key":"9867_CR3","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/s00454-015-9709-7","volume":"54","author":"O Aichholzer","year":"2015","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete Comput. Geom. 54(2), 368\u2013389 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9867_CR4","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. 42(1), 60\u201380 (2009)","journal-title":"Comput. Geom."},{"key":"9867_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Algorithms and Data Structures","author":"GS Brodal","year":"1999","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: Dehne, F., et al. (eds.) Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 1663, pp. 342\u2013351. Springer, Berlin (1999)"},{"issue":"16","key":"9867_CR6","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1016\/j.ipl.2009.04.023","volume":"109","author":"S Cleary","year":"2009","unstructured":"Cleary, S., St. John, K.: Rotation distance is fixed-parameter tractable. Inf. Process. Lett. 109(16), 918\u2013922 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9867_CR7","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics. Springer, Heidelberg (2010)"},{"key":"9867_CR8","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","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, New York (1999)"},{"issue":"4","key":"9867_CR9","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/s003730170006","volume":"17","author":"Z Gao","year":"2001","unstructured":"Gao, Z., Urrutia, J., Wang, J.: Diagonal flips in labelled planar triangulations. Graphs Comb. 17(4), 647\u2013657 (2001)","journal-title":"Graphs Comb."},{"issue":"8","key":"9867_CR10","first-page":"570","volume":"2","author":"S Hanke","year":"1996","unstructured":"Hanke, S., Ottmann, T., Schuierer, S.: The edge-flipping distance of triangulations. J. UCS 2(8), 570\u2013579 (1996)","journal-title":"J. UCS"},{"issue":"4","key":"9867_CR11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. Assoc. Comput. Mach. 21(4), 549\u2013568 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9867_CR12","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/800119.803896","volume-title":"Sixth Annual ACM Symposium on Theory of Computing","author":"JE Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Wong, J.K.: Linear time algorithm for isomorphism of planar graphs. In: Book, R.V., et al. (eds.) Sixth Annual ACM Symposium on Theory of Computing, pp. 172\u2013184. Association for Computing Machinery, New York (1974)"},{"issue":"3","key":"9867_CR13","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/PL00009464","volume":"22","author":"F Hurtado","year":"1999","unstructured":"Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22(3), 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"9867_CR14","unstructured":"Kanj, I., Xia, G.: Flip distance is in $$FPT$$ F P T Time $${\\cal{O}}(n+ k \\cdot c^k)$$ O ( n + k \u00b7 c k ) . In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 30, pp. 500\u2013512. Leibniz-Zentrum fuer Informatik, Dagstuhl (2015)"},{"key":"9867_CR15","doi-asserted-by":"crossref","DOI":"10.1201\/9781315272689","volume-title":"Graphs, Algorithms, and Optimization. Discrete Mathematics and Its Applications","author":"W Kocay","year":"2017","unstructured":"Kocay, W., Kreher, D.L.: Graphs, Algorithms, and Optimization. Discrete Mathematics and Its Applications, 2nd edn. CRC Press, Boca Raton (2017)","edition":"2"},{"issue":"4","key":"9867_CR16","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0012-365X(72)90093-3","volume":"3","author":"CL Lawson","year":"1972","unstructured":"Lawson, C.L.: Transforming triangulations. Discrete Math. 3(4), 365\u2013372 (1972)","journal-title":"Discrete Math."},{"key":"9867_CR17","doi-asserted-by":"crossref","unstructured":"De Loera, J.A., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications. Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-12971-1"},{"key":"9867_CR18","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"A Lubiw","year":"2015","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. 49, 17\u201323 (2015)","journal-title":"Comput. Geom."},{"issue":"12\u201313","key":"9867_CR19","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.ipl.2010.04.022","volume":"110","author":"JM Lucas","year":"2010","unstructured":"Lucas, J.M.: An improved kernel size for rotation distance in binary trees. Inf. Process. Lett. 110(12\u201313), 481\u2013484 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9867_CR20","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00373-002-0508-6","volume":"19","author":"R Mori","year":"2003","unstructured":"Mori, R., Nakamoto, A., Ota, K.: Diagonal flips in Hamiltonian triangulations on the sphere. Graphs Comb. 19(3), 413\u2013418 (2003)","journal-title":"Graphs Comb."},{"key":"9867_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/978-3-319-13075-0_36","volume-title":"Algorithms and Computation","author":"AE Mouawad","year":"2014","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V.: Vertex cover reconfiguration and beyond. In: Ahn, H.-K., et al. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, vol. 8889, pp. 452\u2013463. Springer, Cham (2014)"},{"key":"9867_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-319-03898-8_24","volume-title":"Parameterized and Exact Computation","author":"AE Mouawad","year":"2013","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. In: Gutin, G., Szeider, S. (eds.) Parameterized and Exact Computation. Lecture Notes in Computer Science, vol. 8246, pp. 281\u2013294. Springer, Cham (2013)"},{"key":"9867_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-319-13524-3_21","volume-title":"Parameterized and Exact computation","author":"AE Mouawad","year":"2014","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Wrochna, M.: Reconfiguration over tree decompositions. In: Cygan, M., Heggernes, P. (eds.) Parameterized and Exact computation. Lecture Notes in Computer Science, vol. 8894, pp. 246\u2013257. Springer, Cham (2014)"},{"key":"9867_CR24","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"9867_CR25","unstructured":"Okabe, A., Boots, B., Sugihara, K.: Spatial Tessellations: Concepts and Applications of Vorono\u012d Diagrams. Applied Probability and Statistics. Wiley Series in Probability and Mathematical Statistics, Wiley, Chichester (1992)"},{"issue":"5","key":"9867_CR26","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.comgeo.2014.01.001","volume":"47","author":"A Pilz","year":"2014","unstructured":"Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. 47(5), 589\u2013604 (2014)","journal-title":"Comput. Geom."},{"key":"9867_CR27","doi-asserted-by":"crossref","unstructured":"Saalfeld, A.: Joint triangulations and triangulation maps. In: CG87 Third Annual Symposium on Computational Geometry, pp. 195\u2013204. Association for Computing Machinery, New York (1987)","DOI":"10.1145\/41958.41979"},{"issue":"1","key":"9867_CR28","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/38.180117","volume":"13","author":"LL Schumaker","year":"1993","unstructured":"Schumaker, L.L.: Triangulations in CAGD. IEEE Comput. Graph. Appl. 13(1), 47\u201352 (1993)","journal-title":"IEEE Comput. Graph. Appl."},{"issue":"3","key":"9867_CR29","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/comjnl\/21.3.243","volume":"21","author":"R Sibson","year":"1978","unstructured":"Sibson, R.: Locally equiangular triangulations. Comput. J. 21(3), 243\u2013245 (1978)","journal-title":"Comput. J."},{"issue":"3","key":"9867_CR30","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1090\/S0894-0347-1988-0928904-4","volume":"1","author":"DD Sleator","year":"1988","unstructured":"Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. J. Am. Math. Soc. 1(3), 647\u2013681 (1988)","journal-title":"J. Am. Math. Soc."},{"issue":"3","key":"9867_CR31","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1137\/0405034","volume":"5","author":"DD Sleator","year":"1992","unstructured":"Sleator, D.D., Tarjan, R.E., Thurston, W.P.: Short encodings of evolving structures. SIAM J. Discrete Math. 5(3), 428\u2013450 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9867_CR32","first-page":"26","volume":"46","author":"K Wagner","year":"1936","unstructured":"Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresber. Dtsch. Math.-Ver. 46, 26\u201332 (1936)","journal-title":"Jahresber. Dtsch. Math.-Ver."},{"issue":"2","key":"9867_CR33","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0734-189X(83)90075-0","volume":"22","author":"DF Watson","year":"1983","unstructured":"Watson, D.F., Philip, G.M.: Systematic triangulations. Comput. Vis. Graph. Image Process. 22(2), 310 (1983)","journal-title":"Comput. Vis. Graph. Image Process."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9867-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9867-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9867-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T15:09:43Z","timestamp":1568819383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9867-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,10]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["9867"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9867-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,10]]}}}