An FPT Algorithm for Bipartite Vertex Splitting

Reyan Ahmed, Stephen Kobourov, Myroslav Kryven

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


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 languageEnglish (US)
Title of host publicationGraph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
EditorsPatrizio Angelini, Reinhard von Hanxleden
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages8
ISBN (Print)9783031222023
StatePublished - 2023
Event30th International Symposium on Graph Drawing and Network Visualization, GD 2022 - Tokyo, Japan
Duration: Sep 13 2022Sep 16 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13764 LNCS


Conference30th International Symposium on Graph Drawing and Network Visualization, GD 2022


  • Fixed parameter tractability
  • Graph drawing
  • Vertex splitting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'An FPT Algorithm for Bipartite Vertex Splitting'. Together they form a unique fingerprint.

Cite this