@inproceedings{268277ed5f00492c98771f45670e63d7,
title = "Visualization of Bipartite Graphs in Limited Window Size",
abstract = "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.",
keywords = "NP-hardness, bipartite graphs, circle layout, two-layer drawing",
author = "William Evans and Kassian K{\"o}ck and Stephen Kobourov",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024 ; Conference date: 19-02-2024 Through 23-02-2024",
year = "2024",
doi = "10.1007/978-3-031-52113-3_14",
language = "English (US)",
isbn = "9783031521126",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "198--210",
editor = "Henning Fernau and Serge Gaspers and Ralf Klasing",
booktitle = "SOFSEM 2024",
address = "Germany",
}