Splitting Vertices in 2-Layer Graph Drawings

Area of Science:

• Graph theory
• Computational geometry
• Network analysis

Background:

• Bipartite graphs are essential for modeling relationships between two distinct sets of entities.
• 2-layer graph drawings visualize these relationships, placing entities on parallel lines.
• Minimizing edge crossings in these drawings is a key challenge.

Purpose of the Study:

• To investigate the effectiveness of vertex splitting for reducing edge crossings in bipartite graph drawings.
• To analyze the computational complexity of optimization problems associated with vertex splitting.
• To develop efficient algorithms for practical applications of bipartite graph visualization.

Main Methods:

• Vertex splitting: replacing a vertex with multiple copies to redistribute incident edges.
• Complexity analysis: determining NP-completeness for certain vertex splitting optimization problems.
• Algorithm development: designing polynomial-time algorithms for tractable variants of the problem.

Main Results:

• Demonstrated that vertex splitting can effectively reduce edge crossings in 2-layer bipartite graph drawings.
• Established the NP-completeness of some vertex splitting optimization problems.
• Developed polynomial-time algorithms for specific vertex splitting scenarios.
• Applied algorithms to benchmark datasets of human anatomical structures and cell type relationships.

Conclusions:

• Vertex splitting is a viable technique for improving the clarity of bipartite graph visualizations.
• The computational complexity of vertex splitting problems varies, with some being intractable and others efficiently solvable.
• The developed algorithms offer practical solutions for analyzing complex biological networks represented as bipartite graphs.