{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:20:16Z","timestamp":1772119216977,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T00:00:00Z","timestamp":1743638400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T00:00:00Z","timestamp":1743638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Bipartite graphs are commonly used to visualize objects and their features. An object may possess several features and several objects may share a common feature. The standard visualization of bipartite graphs, with objects and features on two (say horizontal) parallel lines at integer coordinates and edges drawn as line segments, can often be difficult to work with. A common task in visualization of such graphs is to consider one object and all its features. This naturally defines a drawing window, defined as the smallest interval that contains the x-coordinates of the object and all its features. We show that if both objects and features can be reordered, minimizing the average window size is NP-hard. However, if the features are fixed, then we provide an efficient polynomial-time algorithm for arranging the objects, so as to minimize the average window size. Finally, we introduce a different way of visualizing the bipartite graph, by placing the nodes of the two parts on two concentric circles. For this setting we also show NP-hardness for the general case and a polynomial-time algorithm when the features are fixed.<\/jats:p>","DOI":"10.1007\/s00236-025-00483-1","type":"journal-article","created":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T14:11:27Z","timestamp":1743775887000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Visualization of bipartite graphs in limited window size"],"prefix":"10.1007","volume":"62","author":[{"given":"Alon","family":"Efrat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Evans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kassian","family":"K\u00f6ck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacob","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,3]]},"reference":[{"key":"483_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Efrat, A., Sharir, M.: Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. In: Proceedings of the eleventh annual symposium on Computational geometry, pp. 39\u201350 (1995)","DOI":"10.1145\/220279.220284"},{"issue":"3","key":"483_CR2","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1109\/MCG.2023.3264244","volume":"43","author":"R Ahmed","year":"2023","unstructured":"Ahmed, R., Angelini, P., Bekos, M.A., Di Battista, G., Kaufmann, M., Kindermann, P., Kobourov, S., N\u00f6llenburg, M., Symvonis, A., Villedieu, A., et al.: Splitting vertices in 2-layer graph drawings. IEEE Comput. Graph. Appl. 43(3), 24\u201335 (2023)","journal-title":"IEEE Comput. Graph. Appl."},{"key":"483_CR3","doi-asserted-by":"crossref","unstructured":"Baumann, J., Pfretzschner, M., Rutter, I.: Parameterized complexity of vertex splitting to pathwidth at most 1. arXiv preprint arXiv:2302.14725 (2023)","DOI":"10.1007\/978-3-031-43380-1_3"},{"key":"483_CR4","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"D Battista","year":"1999","unstructured":"Battista, D., Giuseppe, E., Peter, T., Roberto, T., Ioannis, G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Saddle River (1999)"},{"key":"483_CR5","doi-asserted-by":"crossref","unstructured":"Bekos, M.A., F\u00f6rster, H., Kaufmann, M., Kobourov, S., Kryven, M., Kuckuk, A., Schlipf, L.: On the 2-layer window width minimization problem. In: International Conference on Current Trends in Theory and Practice of Computer Science, pp. 209\u2013221. Springer (2023)","DOI":"10.1007\/978-3-031-23101-8_14"},{"key":"483_CR6","unstructured":"Bhat, K.V.S.: An $${O}(n^{2.5} \\log _2 n)$$ time algorithm for the bottleneck assignment problem. unpublished. AT &T Bell Laboratories, Napiendle (1984)"},{"issue":"1\u20132","key":"483_CR7","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-010-9456-3","volume":"62","author":"K Buchin","year":"2012","unstructured":"Buchin, K., Buchin, M., Byrka, J., N\u00f6llenburg, M., Okamoto, Y., Silveira, R., Wolff, A.: Drawing (complete) binary tanglegrams. Algorithmica 62(1\u20132), 309\u2013332 (2012). https:\/\/doi.org\/10.1007\/s00453-010-9456-3","journal-title":"Algorithmica"},{"key":"483_CR8","unstructured":"CCF ASCT+B reporter, 2010. URL: hubmapconsortium.github.io\/ccf-asct-reporter\/"},{"key":"483_CR9","doi-asserted-by":"crossref","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., Sachdeva, S.: Maximum flow and minimum-cost flow in almost-linear time. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 612\u2013623. IEEE (2022)","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"483_CR10","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2022","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press, Cambridge (2022)","edition":"4"},{"key":"483_CR11","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.H.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008). www.springer.com\/computer\/theoretical+computer+science\/book\/978-3-540-77973-5","DOI":"10.1007\/978-3-540-77974-2"},{"key":"483_CR12","doi-asserted-by":"crossref","unstructured":"Eades, P., de\u00a0Mendon\u00e7a\u00a0N., CFX: Vertex splitting and tension-free layout. In: Graph Drawing: Symposium on Graph Drawing, GD\u201995 Passau, Germany, September 20\u201322, 1995 Proceedings 3, pp. 202\u2013211. Springer (1996)","DOI":"10.1007\/BFb0021804"},{"issue":"4","key":"483_CR13","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"issue":"7","key":"483_CR14","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.jcss.2009.10.014","volume":"76","author":"H Fernau","year":"2010","unstructured":"Fernau, H., Kaufmann, M., Poths, M.: Comparing trees via crossing minimization. J. Comput. Syst. Sci. 76(7), 593\u2013608 (2010). https:\/\/doi.org\/10.1016\/j.jcss.2009.10.014","journal-title":"J. Comput. Syst. Sci."},{"key":"483_CR15","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"66","author":"HN Gabow","year":"1988","unstructured":"Gabow, H.N., Tarjan, R.E.: Algorithms for two bottleneck optimization problems. J. Algorithms 66, 411\u2013417 (1988)","journal-title":"J. Algorithms"},{"issue":"3","key":"483_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"483_CR17","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"66","author":"F Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in convex bipartite graphs. Naval Res. Logist. Q. 66, 313\u2013316 (1967)","journal-title":"Naval Res. Logist. Q."},{"key":"483_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8","volume-title":"Drawing Graphs, Methods and Models, volume 2025 of LNCS","year":"2001","unstructured":"Kaufmann, M., Wagner, D. (eds.): Drawing Graphs, Methods and Models, volume 2025 of LNCS. Springer, Berin (2001). https:\/\/doi.org\/10.1007\/3-540-44969-8"},{"issue":"1\u20132","key":"483_CR19","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2(1\u20132), 83\u201397 (1955)","journal-title":"Naval Res. Logist. Q."},{"issue":"4","key":"483_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(95)00145-3","volume":"56","author":"YD Liang","year":"1995","unstructured":"Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and Hamiltonian circuits. Inf. Process. Lett. 56(4), 215\u2013219 (1995)","journal-title":"Inf. Process. Lett."},{"key":"483_CR21","volume-title":"Graph Drawing and Network Visualization (GD\u201922), volume 13764 of LNCS","author":"M N\u00f6llenburg","year":"2022","unstructured":"N\u00f6llenburg, M., Sorge, M., Terziadis, S., Villedieu, A., Wu, H.-Y., Wulms, J.: Planarizing graphs and their drawings by vertex splitting. In: Angelini, P., von Hanxleden, R. (eds.) Graph Drawing and Network Visualization (GD\u201922), volume 13764 of LNCS. Springer, Berlin (2022)"},{"key":"483_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"66","author":"G Steiner","year":"1996","unstructured":"Steiner, G., Yeomans, J.S.: A linear time algorithm for determining maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 66, 91\u201396 (1996)","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"483_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K Sugiyama","year":"1981","unstructured":"Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109\u2013125 (1981). https:\/\/doi.org\/10.1109\/TSMC.1981.4308636","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"483_CR24","doi-asserted-by":"crossref","unstructured":"Vaidya, P.: Geometry helps in matching. In: Proceedings of the twentieth annual ACM symposium on theory of computing, pp. 422\u2013425 (1988)","DOI":"10.1145\/62212.62253"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00483-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00483-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00483-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T07:42:36Z","timestamp":1750146156000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00483-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["483"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00483-1","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4357108\/v1","asserted-by":"object"}]},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,3]]},"assertion":[{"value":"2 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"19"}}