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 Ω() 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 [ETCS 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 Ω() 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.
展开▼
