On the computational complexity of edge concentration Original Research Article

Suppose that G=(U,L,E) is a bipartite graph with vertex set U∪L and edge set E⊆U×L. A typical convention for drawing G is to put the vertices of U on a horizontal line and the vertices of L on another horizontal line, and then to represent edges by line segments between the vertices that determine them. “Edge concentration” is known as an effective method to draw dense bipartite graphs clearly. The key in the edge concentration method is to reduce the number of edges, while the graph structural information is retained. The problem of having a maximal reduction on the number of edges by the edge concentration method was left open. In this paper we show that this problem is NP-hard.