Bipartite Crossing Numbers of Meshes and Hypercubes

Shahrokhi, Farhad and Sýkora, Ondrej and Székely, László A. and Vrt'o, Imrich (1998) Bipartite Crossing Numbers of Meshes and Hypercubes. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 37-46(Official URL:

Full text not available from this repository.


Let G=(V_{0},V_{1},E) be a connected bipartite graph, where V_{0},V_{1} ist the bipartition of the vertex set V(G) into independent sets. A bipartite drawing of G consists of placing the vertices of V_{0} and V_{1} into distinct points on two parallel lines x_{0}, x_{1}, respectively, and then drawing each edge with one straight line segment which connects the points of x_{0} and x_{1} where the endvertices of the edge were placed. The bipartite crossing number of G, denoted by bcr(G) is the minimum number of crossings of edges over all bipartite drawings of G. We develop a new lower bound method for estimating bcr(G). It relates bipartite crossing numbers to edge isoperimetric inequalities and Laplacian eigenvalues of graphs. We apply the method, which is suitable for "well structured" graphs, to hypercubes and 2-dimensional meshes. E.g. for the n-dimenional hypercube garph we get n4^{n-2}-O(4^{n})\leq bcr(Q_{n})\leq n4^{n-1}. We also consider a more general setting of the method which uses eigenvalues, but as a trade-off for generality, often gives weaker results.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_48
Classifications: M Methods > M.999 Others
G Algorithms and Complexity > G.420 Crossings

Actions (login required)

View Item View Item