Visualization of Bipartite Graphs in Limited Window Size

William Evans, Kassian Köck, Stephen Kobourov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationSOFSEM 2024
Subtitle of host publicationTheory and Practice of Computer Science - 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, Proceedings
EditorsHenning Fernau, Serge Gaspers, Ralf Klasing
PublisherSpringer Science and Business Media Deutschland GmbH
Pages198-210
Number of pages13
ISBN (Print)9783031521126
DOIs
StatePublished - 2024
Externally publishedYes
Event49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024 - Cochem, Germany
Duration: Feb 19 2024Feb 23 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14519 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024
Country/TerritoryGermany
CityCochem
Period2/19/242/23/24

Keywords

  • NP-hardness
  • bipartite graphs
  • circle layout
  • two-layer drawing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Visualization of Bipartite Graphs in Limited Window Size'. Together they form a unique fingerprint.

Cite this