{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T10:21:55Z","timestamp":1725790915113},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544224"},{"type":"electronic","value":"9783642544231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54423-1_42","type":"book-chapter","created":{"date-parts":[[2014,3,25]],"date-time":"2014-03-25T03:02:27Z","timestamp":1395716547000},"page":"478-489","source":"Crossref","is-referenced-by-count":0,"title":["The Flip Diameter of Rectangulations and Convex Subdivisions"],"prefix":"10.1007","author":[{"given":"Eyal","family":"Ackerman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michelle M.","family":"Allen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gill","family":"Barequet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joshua","family":"Mermelstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diane L.","family":"Souvaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","unstructured":"Ackerman, E.: Counting Problems for Geometric Structures: Rectangulations, Floorplans, and Quasi-Planar Graphs, Ph.D. thesis, Technion\u2014Israel Inst. of Technology (2006)"},{"issue":"6","key":"42_CR2","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1016\/j.jcta.2005.10.003","volume":"113","author":"E. Ackerman","year":"2006","unstructured":"Ackerman, E., Barequet, G., Pinter, R.Y.: On the number of rectangulations of a planar point set, J. Combin. Theory, Ser. A.\u00a0113(6), 1072\u20131091 (2006)","journal-title":"Combin. Theory, Ser. A."},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Asinowski, A., Barequet, G., Bousquet-M\u00e9lou, M., Mansour, T., Pinter, R.Y.: Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations. Electr. J. Comb.\u00a020(2), P35 (2013)","DOI":"10.37236\/2607"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P. Bose","year":"1998","unstructured":"Bose, P., Buss, J., Lubiw, A.: Pattern matching for permutations. Inf. Proc. Lett.\u00a065, 277\u2013283 (1998)","journal-title":"Inf. Proc. Lett."},{"key":"42_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-22300-6_14","volume-title":"Algorithms and Data Structures","author":"K. Buchin","year":"2011","unstructured":"Buchin, K., Eppstein, D., L\u00f6ffler, M., N\u00f6llenburg, M., Silveira, R.I.: Adjacency-preserving spatial treemaps. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 159\u2013170. Springer, Heidelberg (2011)"},{"key":"42_CR6","first-page":"28","volume":"4","author":"A.L. Buchsbaum","year":"2008","unstructured":"Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Algorithms\u00a04, 28 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"42_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/net.10058","volume":"41","author":"F.C. Calheiros","year":"2003","unstructured":"Calheiros, F.C., Lucena, A., de Souza, C.C.: Optimal rectangular partitions. Networks\u00a041(1), 51\u201367 (2003)","journal-title":"Networks"},{"key":"42_CR8","unstructured":"Cardei, M., Cheng, X., Cheng, X., Du, D.Z.: A tale on guillotine cut. In: Proc. Novel Approaches to Hard Discrete Optimization, Ontario, Canada (2001)"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: The Discrepancy Method. Cambridge University Press (2000)","DOI":"10.1017\/CBO9780511626371"},{"issue":"1","key":"42_CR10","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/BF02574056","volume":"13","author":"H. Fraysseix de","year":"1995","unstructured":"de Fraysseix, H., de Mendez, P.O., Pach, J.: A left-first search algorithm for planar graphs. Discrete Comput. Geom.\u00a013(1), 459\u2013468 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(83)90128-0","volume":"46","author":"P. Duchet","year":"1983","unstructured":"Duchet, P., Hamidoune, Y., Las Vergnas, M., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math.\u00a046, 319\u2013321 (1983)","journal-title":"Discrete Math."},{"key":"42_CR12","unstructured":"Du, D.Z., Pan, L.Q., Shing, M.T.: Minimum edge length guillotine rectangular partition, Technical Report MSRI 02418-86, University of California, Berkeley, CA (1986)"},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/110834032","volume":"41","author":"D. Eppstein","year":"2012","unstructured":"Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal and constrained rectangular layouts. SIAM J. Comput.\u00a041(3), 537\u2013564 (2012)","journal-title":"SIAM J. Comput."},{"key":"42_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-319-03841-4_18","volume-title":"Graph Drawing","author":"S. Felsner","year":"2013","unstructured":"Felsner, S.: Exploiting air-pressure to map floorplans on point sets. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol.\u00a08242, pp. 196\u2013207. Springer, Heidelberg (2013)"},{"key":"42_CR15","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-1-4614-0110-0_12","volume-title":"Thirty Essays in Geometric Graph Theory","author":"S. Felsner","year":"2013","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays in Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)"},{"issue":"3","key":"42_CR16","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1016\/j.jcta.2010.03.017","volume":"118","author":"S. Felsner","year":"2011","unstructured":"Felsner, S., Fusy, \u00c9., Noy, M., Orden, D.: Bijections for Baxter families and related objects. J. Comb. Theory, Ser. A\u00a0118(3), 993\u20131020 (2011)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"42_CR17","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1016\/S0747-7171(89)80042-2","volume":"7","author":"T.F. Gonzalez","year":"1989","unstructured":"Gonzalez, T.F., Zheng, S.-Q.: Improved bounds for rectangular and guillotine partitions. J. of Symbolic Computation\u00a07, 591\u2013610 (1989)","journal-title":"J. of Symbolic Computation"},{"key":"42_CR18","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF01840375","volume":"5","author":"T.F. Gonzalez","year":"1990","unstructured":"Gonzalez, T.F., Zheng, S.-Q.: Approximation algorithms for partitioning a rectangle with interior points. Algorithmica\u00a05, 11\u201342 (1990)","journal-title":"Algorithmica"},{"key":"42_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-36065-7_31","volume-title":"WALCOM: Algorithms and Computation","author":"M.. M. Hasan","year":"2013","unstructured":"Hasan, M. M., Rahman, M. S., Karim, M. R.: Box-rectangular drawings of planar graphs. In: Ghosh, S.K., Tokuyama, T. (eds.) WALCOM 2013. LNCS, vol.\u00a07748, pp. 334\u2013345. Springer, Heidelberg (2013)"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover, and set packing problems. Discrete Appl. Math.\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"42_CR21","doi-asserted-by":"publisher","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.\u00a022(3), 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"key":"42_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/net.3230150202","volume":"15","author":"K. Ko\u017aimi\u0144ski","year":"1985","unstructured":"Ko\u017aimi\u0144ski, K., Kinnen, E.: Rectangular duals of planar graphs. Networks\u00a015, 145\u2013157 (1985)","journal-title":"Networks"},{"key":"42_CR23","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/B978-0-12-587260-7.50011-X","volume-title":"Mathematical Software III","author":"C. Lawson","year":"1977","unstructured":"Lawson, C.: Software for c 1 surface interpolation. In: Rice, J. (ed.) Mathematical Software III, pp. 161\u2013194. Academic Press, New York (1977)"},{"key":"42_CR24","doi-asserted-by":"crossref","unstructured":"Levcopoulos, C.: Fast heuristics for minimum length rectangular partitions of polygons. In: Proc. 2nd ACM Symp. on Computational Geometry, Yorktown Heights, NY, pp. 100\u2013108 (1986)","DOI":"10.1145\/10515.10526"},{"key":"42_CR25","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S0196-6774(03)00057-9","volume":"48","author":"C.C. Liao","year":"2003","unstructured":"Liao, C.C., Lu, H.I., Yen, H.C.: Compact floor-planning via orderly spanning trees. J. Algorithms\u00a048, 441\u2013451 (2003)","journal-title":"J. Algorithms"},{"key":"42_CR26","unstructured":"Lingas, A., Pinter, R.Y., Rivest, R.L., Shamir, A.: Minimum edge length rectilinear decompositions of rectilinear figures. In: Proc. 20th Allerton Conf. on Communication, Control, and Computing, Monticello, IL, pp. 53\u201363 (1982)"},{"key":"42_CR27","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/S0196-6774(03)00126-3","volume":"50","author":"M. Rahman","year":"2004","unstructured":"Rahman, M., Nishizeki, T., Ghosh, S.: Rectangular drawings of planar graphs. J.\u00a0Algorithms\u00a050, 62\u201378 (2004)","journal-title":"J.\u00a0Algorithms"},{"issue":"3","key":"42_CR28","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/208794","volume":"24","author":"E. Raisz","year":"1934","unstructured":"Raisz, E.: The rectangular statistical cartogram. Geogr. Rev.\u00a024(3), 292\u2013296 (1934)","journal-title":"Geogr. Rev."},{"issue":"1","key":"42_CR29","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jctb.1997.1750","volume":"70","author":"N. Robertson","year":"1997","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: The four-colour theorem. J. Combin. Theory, Ser. B\u00a070(1), 2\u201344 (1997)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"42_CR30","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0097-3165(03)00002-5","volume":"102","author":"F. Santos","year":"2003","unstructured":"Santos, F., Seidel, R.: A better upper bound on the number of triangulations of a planar point set. J. Combin. Theory, Ser. A\u00a0102, 186\u2013193 (2003)","journal-title":"J. Combin. Theory, Ser. A"},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: Random triangulations of planar point sets. In: Proc.\u00a022nd ACM Symp.\u00a0on Comput.\u00a0Geom., pp. 273\u2013281. ACM Press (2006)","DOI":"10.1145\/1137856.1137898"},{"key":"42_CR32","first-page":"647","volume":"1","author":"D. Sleator","year":"1988","unstructured":"Sleator, D., Tarjan, R., Thurston, W.: Rotations distance, triangulations and hyperbolic geometry. J.\u00a0AMS\u00a01, 647\u2013682 (1988)","journal-title":"J.\u00a0AMS"},{"key":"42_CR33","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., Tollis, I.G.: A unified approach to visibility representations of planar graphs. Dicrete Comput. Geom.\u00a01, 321\u2013341 (1986)","journal-title":"Dicrete Comput. Geom."},{"key":"42_CR34","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Math. Fiz. Lapok\u00a048, 436\u2013452 (1941) (in Hungarian)","journal-title":"Math. Fiz. Lapok"},{"key":"42_CR35","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1112\/jlms\/s1-28.3.336","volume":"28","author":"P. Ungar","year":"1953","unstructured":"Ungar, P.: On diagrams representing graphs. J. London Math. Soc.\u00a028, 336\u2013342 (1953)","journal-title":"J. London Math. Soc."},{"key":"42_CR36","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1145\/606603.606607","volume":"8","author":"B. Yao","year":"2003","unstructured":"Yao, B., Chen, H., Cheng, C.K., Graham, R.: Floorplan representations: Complexity and connections. ACM Trans. on Design Automation of Electronic Systems\u00a08, 55\u201380 (2003)","journal-title":"ACM Trans. on Design Automation of Electronic Systems"}],"container-title":["Lecture Notes in Computer Science","LATIN 2014: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54423-1_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,16]],"date-time":"2020-08-16T19:15:05Z","timestamp":1597605305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54423-1_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544224","9783642544231"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54423-1_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}