TY - GEN
T1 - An FPT Algorithm for Bipartite Vertex Splitting
AU - Ahmed, Reyan
AU - Kobourov, Stephen
AU - Kryven, Myroslav
N1 - Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as 2-layered drawings, where each set of objects is visualized as vertices (points) on one of two parallel horizontal lines and the relationships are represented by (usually straight-line) edges between the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings. This, in general, is an NP-hard problem and may still result in drawings with so many crossings that they affect the readability of the drawing. We consider a recent approach to remove crossings in such visualizations by splitting vertices, where the goal is to find the minimum number of vertices to be split to obtain a planar drawing. We show that determining whether a planar 2-layered drawing exists after splitting at most k vertices is fixed parameter tractable in k.
AB - Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as 2-layered drawings, where each set of objects is visualized as vertices (points) on one of two parallel horizontal lines and the relationships are represented by (usually straight-line) edges between the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings. This, in general, is an NP-hard problem and may still result in drawings with so many crossings that they affect the readability of the drawing. We consider a recent approach to remove crossings in such visualizations by splitting vertices, where the goal is to find the minimum number of vertices to be split to obtain a planar drawing. We show that determining whether a planar 2-layered drawing exists after splitting at most k vertices is fixed parameter tractable in k.
KW - Fixed parameter tractability
KW - Graph drawing
KW - Vertex splitting
UR - http://www.scopus.com/inward/record.url?scp=85148687773&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85148687773&partnerID=8YFLogxK
U2 - https://doi.org/10.1007/978-3-031-22203-0_19
DO - https://doi.org/10.1007/978-3-031-22203-0_19
M3 - Conference contribution
SN - 9783031222023
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 261
EP - 268
BT - Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
A2 - Angelini, Patrizio
A2 - von Hanxleden, Reinhard
PB - Springer Science and Business Media Deutschland GmbH
T2 - 30th International Symposium on Graph Drawing and Network Visualization, GD 2022
Y2 - 13 September 2022 through 16 September 2022
ER -