An FPT algorithm for bipartite vertex splitting

DOI10.1007/978-3-031-22203-0_19MaRDI QIDQ6172201zbMATH OpenOpenAlexFDO

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)

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)

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$.

Cites work

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

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)