A Conjecture on the Error Bound of the Barycenter Heuristic
We reconsider the error bound calculations of the barycenter heuristic for drawing bipartite graphs with as few edge crossings as possible. We conjecture that, contrary to earlier results, the relative error done by the barycenter heuristic is bounded, provided that some natural assumptions are made. This result would explain why the barycenter heuristic performs so well in practice.