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

fixed parameter tractabilitygraph drawingvertex splitting

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

• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Graph Drawing
• scientific article; zbMATH DE number 2084271 (Why is no real title available?)
• 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

(10)

• An FPTAS for the hardcore model on random regular bipartite graphs
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Graph-Theoretic Concepts in Computer Science
• Splitting plane graphs to outerplanarity
• Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
• Splitting plane graphs to outerplanarity
• Cluster editing with overlapping communities
• Parameterized algorithms for planar 2-layer drawing by vertex splitting on a given subset
• On the complexity of establishing hereditary graph properties via vertex splitting
• Improved kernelization and fixed-parameter algorithm for bipartite one-sided vertex explosion

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)