An FPT algorithm for bipartite vertex splitting

DOI10.1007/978-3-031-22203-0_19arXiv2208.12898OpenAlexW4317393696MaRDI QIDQ6172201FDOQ6172201

Authors: Reyan Ahmed, Stephen G. Kobourov, Myroslav Kryven 

Publication date: 16 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Bipartite graphs model the relationship between two disjoint sets of objects. They have a wide range of applications and are often visualized as a 2-layered drawing, where each set of objects is visualized as a set of vertices (points) on one of the two parallel horizontal lines and the relationships are represented by edges (simple curves) between the two lines connecting the corresponding vertices. One of the common objectives in such drawings is to minimize the number of crossings this, however, is computationally expensive 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 drawing exists after splitting at most $k$ vertices is fixed parameter tractable in $k$.

Full work available at URL: https://arxiv.org/abs/2208.12898

zbMATH Keywords

graph drawingvertex splittingfixed parameter tractability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• On the complexity of \(k\)-SAT
• Title not available (Why is that?)
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Planarizing graphs---a survey and annotated bibliography
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• Three ways to cover a graph
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Ranking and drawing in subexponential time
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Planarizing graphs and their drawings by vertex splitting
• SPLITTING NUMBER is NP-complete
• Graph Drawing

Cited In (6)

• Graph-Theoretic Concepts in Computer Science
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Splitting plane graphs to outerplanarity
• An FPTAS for the hardcore model on random regular bipartite graphs
• Splitting plane graphs to outerplanarity
• Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1

This page was built for publication: An FPT algorithm for bipartite vertex splitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172201)