@inproceedings{49f4755accaf4d55b323dfaca8ca83f1,
title = "On the 2-Layer Window Width Minimization Problem",
abstract = "When interacting with a visualization of a bipartite graph, one of the most common tasks requires identifying the neighbors of a given vertex. In interactive visualizations, selecting a vertex of interest usually highlights the edges to its neighbors while hiding/shading the rest of the graph. If the graph is large, the highlighted subgraph may not fit in the display window. This motivates a natural optimization task: find an arrangement of the vertices along two layers that reduces the size of the window needed to see a selected vertex and all its neighbors. We consider two variants of the problem; for one we present an efficient algorithm, while for the other we show NP-hardness and give a 2-approximation.",
keywords = "2-layer drawings, Bipartite graphs, Graph drawing, Window width",
author = "Bekos, {Michael A.} and Henry F{\"o}rster and Michael Kaufmann and Stephen Kobourov and Myroslav Kryven and Axel Kuckuk and Lena Schlipf",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023 ; Conference date: 15-01-2023 Through 18-01-2023",
year = "2023",
doi = "10.1007/978-3-031-23101-8_14",
language = "English (US)",
isbn = "9783031231001",
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 = "209--221",
editor = "Leszek Gasieniec",
booktitle = "SOFSEM 2023",
address = "Germany",
}