{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T00:08:05Z","timestamp":1769558885819,"version":"3.49.0"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T00:00:00Z","timestamp":1595808000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T00:00:00Z","timestamp":1595808000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["615640-ForEFront"],"award-info":[{"award-number":["615640-ForEFront"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GRK 2434"],"award-info":[{"award-number":["GRK 2434"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["GATO: ANR-16-CE40-0009-01"],"award-info":[{"award-number":["GATO: ANR-16-CE40-0009-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["DISTANCIA: ANR-17-CE40-0015"],"award-info":[{"award-number":["DISTANCIA: ANR-17-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["CAPPS: ANR17-CE40-0018"],"award-info":[{"award-number":["CAPPS: ANR17-CE40-0018"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Austrian Science Fund","award":["I 3340-N35"],"award-info":[{"award-number":["I 3340-N35"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the flip distance: Given two objects, what is the minimum number of flips needed to transform one into the other? We consider flip graphs on orientations of simple graphs, where flips consist of reversing the direction of some edges. More precisely, we consider so-called <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-orientations of a graph <jats:italic>G<\/jats:italic>, in which every vertex <jats:italic>v<\/jats:italic> has a specified outdegree <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha (v)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b1<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-orientations of a planar graph <jats:italic>G<\/jats:italic> is at most two is -complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids, or, alternatively, on an alcoved polytope. It therefore provides an interesting example of a flip distance question that is computationally intractable despite having a natural interpretation as a geodesic on a nicely structured combinatorial polytope. We also consider the dual question of the flip distance between graph orientations in which every cycle has a specified number of forward edges, and a flip is the reversal of all edges in a minimal directed cut. In general, the problem remains hard. However, if we restrict to flips that only change sinks into sources, or vice-versa, then the problem can be solved in polynomial time. Here we exploit the fact that the flip graph is the cover graph of a distributive lattice. This generalizes a recent result from Zhang et al. (Acta Math Sin Engl Ser 35(4):569\u2013576, 2019).<\/jats:p>","DOI":"10.1007\/s00453-020-00751-1","type":"journal-article","created":{"date-parts":[[2020,7,27]],"date-time":"2020-07-27T08:02:30Z","timestamp":1595836950000},"page":"116-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Flip Distances Between Graph Orientations"],"prefix":"10.1007","volume":"83","author":[{"given":"Oswin","family":"Aichholzer","sequence":"first","affiliation":[]},{"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[]},{"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[]},{"given":"Kolja","family":"Knauer","sequence":"additional","affiliation":[]},{"given":"Torsten","family":"M\u00fctze","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,27]]},"reference":[{"key":"751_CR1","unstructured":"Aguiar, M., Ardila, F.: Hopf Monoids and Generalized Permutahedra (2017). arXiv:1709.07504"},{"issue":"5","key":"751_CR2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s00373-007-0750-z","volume":"23","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Aurenhammer, F., Huemer, C., Vogtenhuber, B.: Gray code enumeration of plane straight-line graphs. Graphs Combin. 23(5), 467\u2013479 (2007)","journal-title":"Graphs Combin."},{"issue":"1\u20133","key":"751_CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1\u20133), 21\u201346 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"751_CR4","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":"751_CR5","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.jcta.2011.08.006","volume":"119","author":"O Bernardi","year":"2012","unstructured":"Bernardi, O., Fusy, \u00c9.: A bijection for triangulations, quadrangulations, pentagulations, etc. J. Combin. Theory Ser. A 119(1), 218\u2013244 (2012)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1","key":"751_CR6","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":"751_CR7","doi-asserted-by":"crossref","unstructured":"Blind, S., Knauer, K., Valicov, P.: Enumerating $k$-Arc-Connected Orientations (2019). arXiv:1908.02050","DOI":"10.1007\/s00453-020-00738-y"},{"key":"751_CR8","unstructured":"Brehm, E.: 3-orientations and schnyder-3-tree-decompositions. Diploma Thesis, Freie Universit\u00e4t Berlin (2000)"},{"key":"751_CR9","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1017\/S000497270004140X","volume":"1","author":"RA Brualdi","year":"1969","unstructured":"Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1, 161\u2013167 (1969)","journal-title":"Bull. Aust. Math. Soc."},{"key":"751_CR10","doi-asserted-by":"crossref","unstructured":"Bose, P., Verdonschot, S.:. A history of flips in combinatorial triangulations. In: Computational Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcal\u00e1 de Henares, Spain, June 27\u201330, 2011, Revised Selected Papers, pp. 29\u201344 (2011)","DOI":"10.1007\/978-3-642-34191-5_3"},{"issue":"3","key":"751_CR11","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s003730200038","volume":"18","author":"M Carmen Hernando","year":"2002","unstructured":"Carmen Hernando, M., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings. Graphs Combin. 18(3), 517\u2013532 (2002)","journal-title":"Graphs Combin."},{"issue":"16","key":"751_CR12","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., John, K.S.: Rotation distance is fixed-parameter tractable. Inf. Process. Lett. 109(16), 918\u2013922 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"751_CR13","doi-asserted-by":"crossref","first-page":"385","DOI":"10.7155\/jgaa.00212","volume":"14","author":"S Cleary","year":"2010","unstructured":"Cleary, S., John, K.S.: A linear-time approximation for rotation distance. J. Graph Algorithms Appl. 14(2), 385\u2013390 (2010)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"751_CR14","first-page":"14","volume":"20","author":"J Cardinal","year":"2018","unstructured":"Cardinal, J., Sacrist\u00e1n, V., Silveira, R.I.: A note on flips in diagonal rectangulations. Discrete Math. Theor. Comput. Sci. 20(2), 14 (2018)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"5","key":"751_CR15","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s00493-014-2959-9","volume":"35","author":"C Ceballos","year":"2015","unstructured":"Ceballos, C., Santos, F., Ziegler, G.M.: Many non-equivalent realizations of the associahedron. Combinatorica 35(5), 513\u2013551 (2015)","journal-title":"Combinatorica"},{"key":"751_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-12971-1","volume-title":"Triangulations: Structures for Algorithms and Applications","author":"J De Loera","year":"2010","unstructured":"De Loera, J., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications, vol. 25. Springer, Berlin (2010)"},{"key":"751_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to Lattices and Order","author":"BA Davey","year":"2002","unstructured":"Davey, B.A., Priestley, H.A.: Introduction to Lattices and Order, 2nd edn. Cambridge University Press, New York (2002)","edition":"2"},{"issue":"1","key":"751_CR18","doi-asserted-by":"crossref","first-page":"24","DOI":"10.37236\/1777","volume":"11","author":"Stefan Felsner","year":"2004","unstructured":"Felsner, Stefan: Lattice structures from planar graphs. Electron. J. Combin. 11(1), 24 (2004)","journal-title":"Electron. J. Combin."},{"key":"751_CR19","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_12"},{"issue":"5","key":"751_CR20","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1017\/S0963548309010001","volume":"18","author":"S Felsner","year":"2009","unstructured":"Felsner, S., Knauer, K.: ULD-lattices and $\\Delta $-bonds. Combin. Probab. Comput. 18(5), 707\u2013724 (2009)","journal-title":"Combin. Probab. Comput."},{"issue":"1","key":"751_CR21","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ejc.2010.07.011","volume":"32","author":"S Felsner","year":"2011","unstructured":"Felsner, S., Knauer, K.: Distributive lattices, polyhedra, and generalized flows. Eur. J. Combin. 32(1), 45\u201359 (2011)","journal-title":"Eur. J. Combin."},{"key":"751_CR22","unstructured":"Felsner, S., Kleist, L., M\u00fctze, T., Sering, L.: Rainbow cycles in flip graphs. In: 34th International Symposium on Computational Geometry, SoCG 2018, June 11\u201314, 2018, Budapest, Hungary, pp. 38:1\u201338:14 (2018)"},{"key":"751_CR23","doi-asserted-by":"crossref","unstructured":"Felsner, S., Schrezenmaier, H., Steiner, R.: Equiangular polygon contact representations. In: Graph-Theoretic Concepts in Computer Science\u201444th International Workshop, WG 2018, Cottbus, Germany, June 27\u201329, 2018, Proceedings, pp. 203\u2013215 (2018)","DOI":"10.1007\/978-3-030-00256-5_17"},{"issue":"3","key":"751_CR24","doi-asserted-by":"crossref","first-page":"39","DOI":"10.37236\/7216","volume":"25","author":"S Felsner","year":"2018","unstructured":"Felsner, S., Schrezenmaier, H., Steiner, R.: Pentagon contact representations. Electron. J. Combin. 25(3), 39 (2018)","journal-title":"Electron. J. Combin."},{"issue":"3","key":"751_CR25","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank, A., Tardos, E.: Generalized polymatroids and submodular flows. Math. Program. 42(3), 489\u2013563 (1988)","journal-title":"Math. Program."},{"issue":"1","key":"751_CR26","first-page":"229","volume":"23","author":"PM Gilmer","year":"1986","unstructured":"Gilmer, P.M., Litherland, R.A.: The duality conjecture in formal knot theory. Osaka J. Math. 23(1), 229\u2013247 (1986)","journal-title":"Osaka J. Math."},{"issue":"1","key":"751_CR27","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00454-012-9400-1","volume":"48","author":"D Gon\u00e7alves","year":"2012","unstructured":"Gon\u00e7alves, D., L\u00e9v\u00eaque, B., Pinlou, A.: Triangle contact representations and duality. Discrete Comput. Geom. 48(1), 239\u2013254 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"751_CR28","doi-asserted-by":"crossref","first-page":"1509","DOI":"10.1016\/j.dam.2008.06.018","volume":"157","author":"C Huemer","year":"2009","unstructured":"Huemer, C., Hurtado, F., Noy, M., Oma\u00f1a-Pulido, E.: Gray codes for non-crossing partitions and dissections of a convex polygon. Discrete Appl. Math. 157(7), 1509\u20131520 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"751_CR29","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s00373-005-0615-2","volume":"21","author":"ME Houle","year":"2005","unstructured":"Houle, M.E., Hurtado, F., Noy, M., Rivera-Campo, E.: Graphs of triangulations and perfect matchings. Graphs Combin. 21(3), 325\u2013331 (2005)","journal-title":"Graphs Combin."},{"issue":"1\u20133","key":"751_CR30","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0012-365X(01)00167-4","volume":"242","author":"S Iwata","year":"2002","unstructured":"Iwata, S.: On matroid intersection adjacency. Discrete Math. 242(1\u20133), 277\u2013281 (2002)","journal-title":"Discrete Math."},{"key":"751_CR31","unstructured":"Knauer, K.: Partial orders on orientations via cycle flips. Master\u2019s thesis, Faculty of Mathematics, TU Berlin (2007)"},{"key":"751_CR32","unstructured":"Knauer, K.: Distributive lattices on graph orientations. In: Semigroups, Acts and Categories with Applications to Graphs, Volume\u00a03 of Mathematical Studies (Tartu), pp. 79\u201391. Est. Mathematical Society, Tartu (2008)"},{"issue":"2","key":"751_CR33","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s00454-017-9867-x","volume":"58","author":"I Kanj","year":"2017","unstructured":"Kanj, I., Sedgwick, E., Xia, G.: Computing the flip distance between triangulations. Discrete Comput. Geom. 58(2), 313\u2013344 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"21","key":"751_CR34","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1016\/j.ipl.2010.07.025","volume":"110","author":"F Luccio","year":"2010","unstructured":"Luccio, F., Mesa Enriquez, A., Pagli, L.: Lower bounds on the rotation distance of binary trees. Inf. Process. Lett 110(21), 934\u2013938 (2010)","journal-title":"Inf. Process. Lett"},{"key":"751_CR35","unstructured":"Lov\u00e1sz, L.: On covering of graphs. Theory of Graphs. In: Proceedings of the Colloquium Held at Tihany, Hungary 1966, pp. 231\u2013236 (1968)"},{"issue":"3","key":"751_CR36","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s00454-006-1294-3","volume":"38","author":"T Lam","year":"2007","unstructured":"Lam, T., Postnikov, A.: Alcoved polytopes. I. Discrete Comput. Geom. 38(3), 453\u2013478 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"751_CR37","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."},{"key":"751_CR38","doi-asserted-by":"crossref","unstructured":"Li, M., Zhang, L.: Better approximation of diagonal-flip transformation and rotation transformation. In: Computing and Combinatorics, 4th Annual International Conference, COCOON\u201998, Taipei, Taiwan, R.O.C., August 12\u201314, 1998, Proceedings, pp. 85\u201394 (1998)","DOI":"10.1007\/3-540-68535-9_12"},{"issue":"1","key":"751_CR39","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1023\/A:1024483217354","volume":"20","author":"PCB Lam","year":"2003","unstructured":"Lam, P.C.B., Zhang, H.: A distributive lattice on the set of perfect matchings of a plane bipartite graph. Order 20(1), 13\u201329 (2003)","journal-title":"Order"},{"issue":"1","key":"751_CR40","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF00383169","volume":"7","author":"H M\u00fcller","year":"1990","unstructured":"M\u00fcller, H.: Alternating cycle-free matchings. Order 7(1), 11\u201321 (1990)","journal-title":"Order"},{"issue":"1\u20133","key":"751_CR41","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0012-365X(93)E0101-9","volume":"135","author":"S Negami","year":"1994","unstructured":"Negami, S.: Diagonal flips in triangulations of surfaces. Discrete Math. 135(1\u20133), 225\u2013232 (1994)","journal-title":"Discrete Math."},{"issue":"3","key":"751_CR42","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/BF01588973","volume":"14","author":"CH Papadimitriou","year":"1978","unstructured":"Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-complete. Math. Program. 14(3), 312\u2013324 (1978)","journal-title":"Math. Program."},{"issue":"2","key":"751_CR43","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0166-218X(84)90101-X","volume":"8","author":"B P\u00e9roche","year":"1984","unstructured":"P\u00e9roche, B.: NP-completeness of some problems of partitioning and covering in graphs. Discrete Appl. Math. 8(2), 195\u2013208 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"751_CR44","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."},{"key":"751_CR45","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1093\/imrn\/rnn153","volume":"6","author":"A Postnikov","year":"2009","unstructured":"Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 6, 1026\u20131106 (2009)","journal-title":"Int. Math. Res. Not. IMRN"},{"key":"751_CR46","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.aim.2014.02.035","volume":"259","author":"L Pournin","year":"2014","unstructured":"Pournin, L.: The diameter of associahedra. Adv. Math. 259, 13\u201342 (2014)","journal-title":"Adv. Math."},{"key":"751_CR47","unstructured":"Propp, J.: Lattice structure for orientations of graphs (2002). arXiv:math\/0209005"},{"key":"751_CR48","unstructured":"Pilaud, V., Santos, F.: Quotientopes. arXiv:171105353 (2018)"},{"key":"751_CR49","unstructured":"Pulleyblank, W.R.: On minimizing setups in precedence constrained scheduling. Technical report, University of Bonn, 1975. Technical Report 81105-OR"},{"key":"751_CR50","doi-asserted-by":"crossref","unstructured":"Propp, J., Wilson, D.: Coupling from the past: a user\u2019s guide. In: Microsurveys in Discrete Probability (Princeton, NJ, 1997), Volume\u00a041 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 181\u2013192. American Mathematical Society, Providence, RI (1998)","DOI":"10.1090\/dimacs\/041\/09"},{"issue":"3","key":"751_CR51","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/S0895480196312462","volume":"11","author":"FJ Rispoli","year":"1998","unstructured":"Rispoli, F.J., Cosares, S.: A bound of $4$ for the diameter of the symmetric traveling salesman polytope. SIAM J. Discrete Math. 11(3), 373\u2013380 (1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"751_CR52","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/j.tcs.2004.03.020","volume":"322","author":"E R\u00e9mila","year":"2004","unstructured":"R\u00e9mila, E.: The lattice structure of the set of domino tilings of a polygon. Theor. Comput. Sci. 322(2), 409\u2013422 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"751_CR53","first-page":"75","volume":"12","author":"G Ringel","year":"1957","unstructured":"Ringel, G.: \u00dcber Geraden in allgemeiner Lage. Elem. Math. 12, 75\u201382 (1957)","journal-title":"Elem. Math."},{"key":"751_CR54","unstructured":"Rogers, R.O.: On finding shortest paths in the rotation graph of binary trees. In: Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), vol. 137, pp. 77\u201395 (1999)"},{"issue":"4","key":"751_CR55","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF00340778","volume":"3","author":"G Steiner","year":"1987","unstructured":"Steiner, G., Stewart, L.K.: A linear time algorithm to find the jump number of $2$-dimensional bipartite partial orders. Order 3(4), 359\u2013367 (1987)","journal-title":"Order"},{"issue":"1","key":"751_CR56","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187680","volume":"1","author":"RP Stanley","year":"1986","unstructured":"Stanley, R.P.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9\u201323 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"751_CR57","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":"8","key":"751_CR58","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1080\/00029890.1990.11995660","volume":"97","author":"WP Thurston","year":"1990","unstructured":"Thurston, W.P.: Conway\u2019s tiling groups. Am. Math. Monthly 97(8), 757\u2013773 (1990)","journal-title":"Am. Math. Monthly"},{"issue":"2\u20133","key":"751_CR59","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0012-365X(87)90198-1","volume":"64","author":"FJ Zhang","year":"1987","unstructured":"Zhang, F.J., Guo, X.F.: Hamilton cycles in directed Euler tour graphs. Discrete Math. 64(2\u20133), 289\u2013298 (1987)","journal-title":"Discrete Math."},{"issue":"4","key":"751_CR60","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/s10114-019-7403-z","volume":"35","author":"WJ Zhang","year":"2019","unstructured":"Zhang, W.J., Qian, J.G., Zhang, F.J.: Distance between $\\alpha $-orientations of plane graphs by facial cycle reversals. Acta Math. Sin. Engl. Ser. 35(4), 569\u2013576 (2019)","journal-title":"Acta Math. Sin. Engl. Ser."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00751-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00751-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00751-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,26]],"date-time":"2021-07-26T23:31:48Z","timestamp":1627342308000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00751-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,27]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["751"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00751-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,27]]},"assertion":[{"value":"25 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}