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 - 10.1007/978-3-031-22203-0_19

DO - 10.1007/978-3-031-22203-0_19

M3 - Conference contribution

AN - SCOPUS:85148687773

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 -