{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:06:15Z","timestamp":1742947575089,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_5","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"54-65","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Approximability of Orthogonal Order Preserving Layout Adjustment"],"prefix":"10.1007","author":[{"given":"Sayan","family":"Bandyapadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santanu","family":"Bhowmick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: A quasi-ptas for the two-dimensional geometric knapsack problem. In: SODA, pp. 1491\u20131505 (2015)","DOI":"10.1137\/1.9781611973730.98"},{"issue":"3\u20134","key":"5_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M.J., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3\u20134), 209\u2013218 (1998)","journal-title":"Comput. Geom."},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00281","volume":"17","author":"U Brandes","year":"2013","unstructured":"Brandes, U., Pampel, B.: Orthogonal-ordering constraints are tough. J. Graph Algorithms Appl. 17(1), 1\u201310 (2013)","journal-title":"J. Graph Algorithms Appl."},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/3-540-37623-2_5","volume-title":"Graph Drawing","author":"SS Bridgeman","year":"1999","unstructured":"Bridgeman, S.S., Tamassia, R.: Difference metrics for interactive orthogonal graph drawing algorithms. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 57\u201371. Springer, Heidelberg (1999)"},{"issue":"3","key":"5_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.7155\/jgaa.00053","volume":"6","author":"S Bridgeman","year":"2002","unstructured":"Bridgeman, S., Tamassia, R.: A user study in similarity measures for graph drawing. J. Graph Algorithms Appl. 6(3), 225\u2013254 (2002)","journal-title":"J. Graph Algorithms Appl."},{"key":"5_CR6","unstructured":"Eades, P., Lai, W., Misue, K., Sugiyama, K.: Preserving the mental map of a diagram. International Institute for Advanced Study of Social Information Science, Fujitsu Limited (1991)"},{"issue":"4","key":"5_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"5_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jagm.2002.1221","volume":"43","author":"DR Gaur","year":"2002","unstructured":"Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. J. Algorithms 43(1), 138\u2013152 (2002)","journal-title":"J. Algorithms"},{"issue":"2","key":"5_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.comgeo.2013.08.008","volume":"47","author":"R Harren","year":"2014","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., van Stee, R.: A (5\/3 + $$\\varepsilon $$)-approximation for strip packing. Comput. Geom. 47(2), 248\u2013267 (2014)","journal-title":"Comput. Geom."},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-03685-9_14","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"R Harren","year":"2009","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. LNCS, vol. 5687, pp. 177\u2013189. Springer, Heidelberg (2009)"},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(91)90011-K","volume":"30","author":"R Hassin","year":"1991","unstructured":"Hassin, R., Megiddo, N.: Approximation algorithms for hitting objects with straight lines. Discrete Appl. Math. 30(1), 29\u201342 (1991)","journal-title":"Discrete Appl. Math."},{"key":"5_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-37623-2_14","volume-title":"Graph Drawing","author":"K Hayashi","year":"1999","unstructured":"Hayashi, K., Inoue, M., Masuzawa, T., Fujiwara, H.: A layout adjustment problem for disjoint rectangles preserving orthogonal order. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 183\u2013197. Springer, Heidelberg (1999)"},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/2945.841119","volume":"6","author":"I Herman","year":"2000","unstructured":"Herman, I., Melan\u00e7on, G., Marshall, M.S.: Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics 6(1), 24\u201343 (2000)","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"issue":"14","key":"5_CR14","doi-asserted-by":"publisher","first-page":"2821","DOI":"10.1016\/j.ins.2007.02.016","volume":"177","author":"X Huang","year":"2007","unstructured":"Huang, X., Lai, W., Sajeev, A., Gao, J.: A new algorithm for removing node overlapping in graph visualization. Information Sciences 177(14), 2821\u20132844 (2007)","journal-title":"Information Sciences"},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0925-7721(99)00005-X","volume":"13","author":"MJ van Kreveld","year":"1999","unstructured":"van Kreveld, M.J., Strijk, T., Wolff, A.: Point labeling with sliding labels. Comput. Geom. 13(1), 21\u201347 (1999)","journal-title":"Comput. Geom."},{"key":"5_CR16","first-page":"131","volume":"45","author":"W Li","year":"2005","unstructured":"Li, W., Eades, P., Nikolov, N.S.: Using spring algorithms to remove node overlapping. APVIS. CRPIT 45, 131\u2013140 (2005)","journal-title":"APVIS. CRPIT"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0377-2217(02)00123-6","volume":"141","author":"A Lodi","year":"2002","unstructured":"Lodi, A., Martello, S., Monaci, M.: Two-dimensional packing problems: A survey. European Journal of Operational Research 141(2), 241\u2013252 (2002)","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"5_CR18","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/jvlc.1995.1010","volume":"6","author":"K Misue","year":"1995","unstructured":"Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of visual languages and computing 6(2), 183\u2013210 (1995)","journal-title":"Journal of visual languages and computing"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BFb0049416","volume-title":"Algorithms - ESA \u201994","author":"I Schiermeyer","year":"1994","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290\u2013299. Springer, Heidelberg (1994)"},{"issue":"2","key":"5_CR20","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401\u2013409 (1997)","journal-title":"SIAM J. Comput."},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/BFb0021833","volume-title":"Graph Drawing","author":"MAD Storey","year":"1996","unstructured":"Storey, M.A.D., M\u00fcller, H.A.: Graph layout adjustment strategies. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 487\u2013499. Springer, Heidelberg (1996)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T09:59:18Z","timestamp":1676973558000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}