An analysis of some linear graph layout heuristics
The worst-case performances of some heuristics for the fixed linear crossing number problem (FLCNP) are analyzed. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal "node line" in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In FLCNP, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems Masuda et al., 1990. In this paper we show that for each of the heuristics described, there exist classes of n-vertex, m-edge graphs which force it to obtain a number of crossings which is a function of n or m when the optimal number is a small constant. This leaves open the problem of finding a heuristic with a constant error bound for the problem.
linear graph layout heuristic crossing number approximation algorithm