An FPT Algorithm for Bipartite Vertex Splitting

Reyan Ahmed, Stephen Kobourov, Myroslav Kryven

Research output: Chapter in Book/Report/Conference proceedingConference 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 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
Pages261-268
Number of pages8
ISBN (Print)9783031222023
DOIs
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International Symposium on Graph Drawing and Network Visualization, GD 2022
Country/TerritoryJapan
CityTokyo
Period9/13/229/16/22

Keywords

  • Fixed parameter tractability
  • Graph drawing
  • Vertex splitting

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this