{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T10:03:41Z","timestamp":1766311421881,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T00:00:00Z","timestamp":1529971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG MU 1129\/10-1"],"award-info":[{"award-number":["DFG MU 1129\/10-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Compacting orthogonal drawings is a challenging task. Usually, algorithms try to compute drawings with small area or total edge length while preserving the underlying orthogonal shape. We suggest a moderate relaxation of the orthogonal compaction problem, namely the one-dimensional monotone flexible edge compaction problem with fixed vertex star geometry. We further show that this problem can be solved in polynomial time using a network flow model. An experimental evaluation shows that by allowing additional bends could reduce the total edge length and the drawing area.<\/jats:p>","DOI":"10.3390\/info9070153","type":"journal-article","created":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T10:40:50Z","timestamp":1530009650000},"page":"153","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["More Compact Orthogonal Drawings by Allowing Additional Bends \u2020"],"prefix":"10.3390","volume":"9","author":[{"given":"Michael","family":"J\u00fcnger","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Cologne, 50923 Cologne, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7621-971X","authenticated-orcid":false,"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Dortmund University, 44221 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christiane","family":"Spisla","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Dortmund University, 44221 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1109\/TSE.1986.6312901","article-title":"A layout algorithm for data flow diagrams","volume":"SE-12","author":"Batini","year":"1986","journal-title":"IEEE Trans. Softw. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1137\/0216030","article-title":"On Embedding a Graph in the Grid with the Minimum Number of Bends","volume":"16","author":"Tamassia","year":"1987","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/3-540-48447-7_7","article-title":"On the Complexity of Orthogonal Compaction","volume":"Volume 1663","author":"Patrignani","year":"1999","journal-title":"Algorithms and Data Structures, 6th International Workshop, WADS \u201999"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","article-title":"An Experimental Comparison of Four Graph Drawing Algorithms","volume":"7","author":"Garg","year":"1997","journal-title":"Comput. Geom."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lengauer, T. (1990). Combinatorial Algorithms for Integrated Circuit Layout, John Wiley & Sons, Inc.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"651","DOI":"10.7155\/jgaa.00263","article-title":"Inapproximability of Orthogonal Compaction","volume":"16","author":"Bannister","year":"2012","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_7","unstructured":"Di Battista, G., Eades, P., Tamassia, R., and Tollis, I.G. (1999). Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0925-7721(99)00054-1","article-title":"Turn-regularity and optimal area drawings of orthogonal representations","volume":"16","author":"Bridgeman","year":"2000","journal-title":"Comput. Geom."},{"key":"ref_9","first-page":"304","article-title":"Optimal Compaction of Orthogonal Grid Drawings","volume":"Volume 1610","author":"Burkard","year":"1999","journal-title":"International Conference on Integer Programming and Combinatorial Optimization"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kaufmann, M., and Wagner, D. (2001). Drawing Graphs, Methods and Models, Springer.","DOI":"10.1007\/3-540-44969-8"},{"key":"ref_11","unstructured":"Dai, W., and Kuh, E. (1987, January 10\u201312). Global spacing of building-block layout. Proceedings of the IFIP TC 10\/WG 10.5 International Conference on Very Large Scale Integration, Vancouver, BC, Canada."},{"key":"ref_12","unstructured":"Eiglsperger, M., and Kaufmann, M. (2001, January 23\u201326). Fast Compaction for Orthogonal Drawings with Vertices of Prescribed Size. Proceedings of the Graph Drawing, 9th International Symposium, GD 2001, Vienna, Austria. Revised Papers."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.amc.2005.03.007","article-title":"A better heuristic for area-compaction of orthogonal representations","volume":"172","author":"Hashemi","year":"2006","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-44541-2_5","article-title":"An Experimental Comparison of Orthogonal Compaction Algorithms","volume":"Volume 1984","author":"Marks","year":"2001","journal-title":"International Symposium on Graph Drawing"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/3-540-37623-2_10","article-title":"On Improving Orthogonal Drawings: The 4M-Algorithm","volume":"Volume 1547","author":"Whitesides","year":"1998","journal-title":"International Symposium on Graph Drawing"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/3-540-37623-2_23","article-title":"Refinement of Orthogonal Graph Drawings","volume":"Volume 1547","author":"Whitesides","year":"1998","journal-title":"International Symposium on Graph Drawing"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-11805-0_14","article-title":"Port Constraints in Hierarchical Layout of Data Flow Diagrams","volume":"Volume 5849","author":"Eppstein","year":"2010","journal-title":"International Symposium on Graph Drawing"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1379","DOI":"10.1016\/j.asoc.2011.11.023","article-title":"A fuzzy genetic algorithm for automatic orthogonal graph drawing","volume":"12","author":"Mesquita","year":"2012","journal-title":"Appl. Soft Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Freivalds, K., and Glagolevs, J. (2014, January 5\u20137). Graph Compact Orthogonal Layout Algorithm. Proceedings of the Combinatorial Optimization\u2014Third International Symposium, ISCO 2014, Lisbon, Portugal. Revised Selected Papers.","DOI":"10.1007\/978-3-319-09174-7_22"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Tamassia, R. (2013). Handbook on Graph Drawing and Visualization, Chapman and Hall\/CRC.","DOI":"10.1201\/b15385"},{"key":"ref_21","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc."},{"key":"ref_22","first-page":"67","article-title":"Efficient implementations of minimum-cost flow algorithms","volume":"4","year":"2012","journal-title":"Acta Univ. Sapientiae Inform."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"635","DOI":"10.7155\/jgaa.00265","article-title":"Accelerated Bend Minimization","volume":"16","author":"Cornelsen","year":"2012","journal-title":"J. Graph Algorithms Appl."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Orlin, J.B. (1988, January 2\u20134). A Faster Strongly Polynominal Minimum Cost Flow Algorithm. Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.21236\/ADA457044"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1720","DOI":"10.1007\/s10878-015-9865-y","article-title":"Budget-constrained minimum cost flows","volume":"31","author":"Holzhauser","year":"2016","journal-title":"J. Comb. Optim."},{"key":"ref_26","first-page":"254","article-title":"Drawing High Degree Graphs with Low Bend Numbers","volume":"Volume 1027","author":"Brandenburg","year":"1995","journal-title":"International Symposium on Graph Drawing"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/21.87055","article-title":"Automatic graph drawing and readability of diagrams","volume":"18","author":"Tamassia","year":"1988","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"J\u00fcnger, M., Klau, G.W., Mutzel, P., and Weiskircher, R. (2004). AGD\u2014A Library of Algorithms for Graph Drawing. Graph Drawing Software, Springer.","DOI":"10.1007\/978-3-642-18638-7"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Tamassia, R. (2013). The Open Graph Drawing Framework (OGDF). Handbook of Graph Drawing and Visualization, CRC Press. Chapter 17.","DOI":"10.1201\/b15385"},{"key":"ref_30","unstructured":"Klau, G.W. (2002). A Combinatorial Approach to Orthogonal Placement Problems. [Ph.D. Thesis, Saarland University]."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Yanardag, P., and Vishwanathan, S.V.N. (2015, January 10\u201313). Deep Graph Kernels. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia.","DOI":"10.1145\/2783258.2783417"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/7\/153\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:10:14Z","timestamp":1760195414000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/7\/153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,26]]},"references-count":31,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["info9070153"],"URL":"https:\/\/doi.org\/10.3390\/info9070153","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2018,6,26]]}}}