New bounds on the barycenter heuristic for bipartite graph drawing
The barycenter heuristic is often used to solve the NP-hard two-layer edge crossing minimization problem. It is well known that the barycenter heuristic can give solutions as bad as Omega (rootn) times the optimum. where n is the number of nodes in the graph. However, the example used in the proof has many isolated nodes. Makinen [EATCS Bull. 70 (2000) 156-158] conjectured that a better performance ratio is possible if isolated nodes are not present. We show that the performance ratio for the barycenter heuristic is still Omega (rootn) even for connected bipartite graphs. We also prove a tight constant ratio for the barycenter heuristic on bounded-degree graphs. The performance ratio is d - 1. where d is the maximum degree of a node in the layer that can be permuted. (C) 2001 Published by Elsevier Science B.V.
barycenter heuristic graph drawing performance ratio