Class BarycenterGreedyTwoLayeredBipartiteLayout2D<V,E>

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

public class BarycenterGreedyTwoLayeredBipartiteLayout2D<V,E> extends TwoLayeredBipartiteLayout2D<V,E>
The barycenter 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: K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man, and Cybernetics, 11(2):109–125, 1981. The problem of minimizing edge crossings when drawing bipartite graphs as two layered graphs is NP-complete. If the coordinates of the nodes in the fixed layer are allowed to vary wildly, then the barycenter heuristic can perform badly. If the coordinates of the nodes in the fixed layer are $1, 2, 3, \ldots, ...$ then it is an $\mathcal{O}(\sqrt{n})$-approximation algorithm.
Dimitrios Michail
  • Constructor Details

    • BarycenterGreedyTwoLayeredBipartiteLayout2D

      public BarycenterGreedyTwoLayeredBipartiteLayout2D()
      Create a new layout
    • BarycenterGreedyTwoLayeredBipartiteLayout2D

      public BarycenterGreedyTwoLayeredBipartiteLayout2D(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