Class MedianGreedyTwoLayeredBipartiteLayout2D<V,E>

Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:

public class MedianGreedyTwoLayeredBipartiteLayout2D<V,E> extends TwoLayeredBipartiteLayout2D<V,E>
The median heuristic greedy algorithm for edge crossing minimization in two layered bipartite layouts. The algorithm draws a bipartite graph using straight edges. Vertices are arranged along two vertical or horizontal lines, trying to minimize crossings. This algorithm targets the one-sided problem where one of the two layers is considered fixed and the algorithm is allowed to adjust the positions of vertices in the other layer. The algorithm is described in the following paper: Eades, Peter, and Nicholas C. Wormald. "Edge crossings in drawings of bipartite graphs." Algorithmica 11.4 (1994): 379-403. The problem of minimizing edge crossings when drawing bipartite graphs as two layered graphs is NP-complete and the median heuristic is a 3-approximation algorithm.
Dimitrios Michail
  • Constructor Details

    • MedianGreedyTwoLayeredBipartiteLayout2D

      public MedianGreedyTwoLayeredBipartiteLayout2D()
      Create a new layout
    • MedianGreedyTwoLayeredBipartiteLayout2D

      public MedianGreedyTwoLayeredBipartiteLayout2D(Set<V> partition, Comparator<V> vertexComparator, boolean vertical)
      Create a new layout
      partition - one of the two partitions, can be null
      vertexComparator - vertex order, can be null
      vertical - draw on two vertical or horizontal lines
  • Method Details