Minimizing the Number of Edges via Edge Concentration in Dense Layered Graphs

Area of Science:

• Graph theory
• Computer science
• Data visualization

Background:

• Edge concentration techniques aim to simplify graph drawings by reducing edges and crossings.
• Newbery's conventional method focuses on minimizing edge crossings but may not reduce edge count, impacting graph readability.
• Minimizing edges is crucial for enhancing graph readability, yet no dedicated method existed.

Purpose of the Study:

• To propose a novel, efficient heuristic method for edge concentration specifically designed to minimize the number of edges in dense bipartite graphs.
• To evaluate the effectiveness of the proposed method in reducing edge count compared to existing techniques.

Main Methods:

• Development of a new heuristic algorithm for edge concentration.
• Comparative analysis using randomly generated dense bipartite graphs.
• Application of the method to a real-world biological causality network.

Main Results:

• The proposed heuristic method effectively minimizes edges during concentration.
• Newbery's method was found to be ineffective in reducing edges for large vertex counts.
• The novel method achieved average compression ratios ranging from 47% to 82% across various graph groups.

Conclusions:

• The developed heuristic provides an efficient solution for minimizing edges in bipartite graph drawings.
• This method offers significant improvements in graph readability, especially for large-scale networks.
• The technique has practical applications, demonstrated by its use in analyzing biological data causality networks.