An FPT Algorithm for Bipartite Vertex Splitting

Reyan Ahmed; Stephen Kobourov; Myroslav Kryven

doi:10.1007/978-3-031-22203-0_19

An FPT Algorithm for Bipartite Vertex Splitting

Reyan Ahmed, Stephen Kobourov, Myroslav Kryven

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
Editors	Patrizio Angelini, Reinhard von Hanxleden
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	261-268
Number of pages	8
ISBN (Print)	9783031222023
DOIs	https://doi.org/10.1007/978-3-031-22203-0_19
State	Published - 2023
Event	30th International Symposium on Graph Drawing and Network Visualization, GD 2022 - Tokyo, Japan Duration: Sep 13 2022 → Sep 16 2022

Publication series

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

Conference

Conference	30th International Symposium on Graph Drawing and Network Visualization, GD 2022
Country/Territory	Japan
City	Tokyo
Period	9/13/22 → 9/16/22

Keywords

Fixed parameter tractability
Graph drawing
Vertex splitting

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Ahmed, R., Kobourov, S., & Kryven, M. (2023). An FPT Algorithm for Bipartite Vertex Splitting. In P. Angelini, & R. von Hanxleden (Eds.), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers (pp. 261-268). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22203-0_19

An FPT Algorithm for Bipartite Vertex Splitting. / Ahmed, Reyan; Kobourov, Stephen; Kryven, Myroslav.

Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. ed. / Patrizio Angelini; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. p. 261-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13764 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ahmed, R, Kobourov, S & Kryven, M 2023, An FPT Algorithm for Bipartite Vertex Splitting. in P Angelini & R von Hanxleden (eds), Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13764 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 261-268, 30th International Symposium on Graph Drawing and Network Visualization, GD 2022, Tokyo, Japan, 9/13/22. https://doi.org/10.1007/978-3-031-22203-0_19

Ahmed R, Kobourov S, Kryven M. An FPT Algorithm for Bipartite Vertex Splitting. In Angelini P, von Hanxleden R, editors, Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2023. p. 261-268. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-22203-0_19

Ahmed, Reyan ; Kobourov, Stephen ; Kryven, Myroslav. / An FPT Algorithm for Bipartite Vertex Splitting. Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers. editor / Patrizio Angelini ; Reinhard von Hanxleden. Springer Science and Business Media Deutschland GmbH, 2023. pp. 261-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{52176d754d1f4294a63ff5a7e1da150c,

title = "An FPT Algorithm for Bipartite Vertex Splitting",

abstract = "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.",

keywords = "Fixed parameter tractability, Graph drawing, Vertex splitting",

author = "Reyan Ahmed and Stephen Kobourov and Myroslav Kryven",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 30th International Symposium on Graph Drawing and Network Visualization, GD 2022 ; Conference date: 13-09-2022 Through 16-09-2022",

year = "2023",

doi = "10.1007/978-3-031-22203-0_19",

language = "English (US)",

isbn = "9783031222023",

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 = "261--268",

editor = "Patrizio Angelini and {von Hanxleden}, Reinhard",

booktitle = "Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - An FPT Algorithm for Bipartite Vertex Splitting

AU - Ahmed, Reyan

AU - Kobourov, Stephen

AU - Kryven, Myroslav

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 -