Bipartite Crossing Numbers of Meshes and HypercubesShahrokhi, 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 1820, 1997 , pp. 3746(Official URL: http://dx.doi.org/10.1007/3540639381_48). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_48
AbstractLet 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 2dimensional meshes. E.g. for the ndimenional hypercube garph we get n4^{n2}O(4^{n})\leq bcr(Q_{n})\leq n4^{n1}. We also consider a more general setting of the method which uses eigenvalues, but as a tradeoff for generality, often gives weaker results.
Actions (login required)
