New bounds on the barycenter heuristic for bipartite graph drawing
✍ Scribed by Xiao Yu Li; Matthias F. Stallmann
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 105 KB
- Volume
- 82
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
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 ( √ n ) times the optimum, where n is the number of nodes in the graph. However, the example used in the proof has many isolated nodes. Mäkinen [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 ( √ n ) 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.