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, Rome, Italy , pp. 37-46 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_48).

Full text not available from this repository.

Abstract

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
ID Code:174

Repository Staff Only: item control page

References

Ahlswede, R., Bezrukov, S.L., Edge isoperimetric theorems for integer point arrays, Appl. Math. Lett. 8 (1995), 75-80.

Bezrukov, S.L., Edge isoperimetric problems on graphs, Technical Report,Department of Computer Science, University of Paderborn, 1997.

Bollobás, B., Combinatorics, Chaper 16, Cambridge Uni. Press, 1986.

Bollobás, B.,Leader, I., Edge-isoperimetric inequalities in the grid, Combinatorica 11 (1991), 299-314.

Bollobás, B.,Leader, I., Matchings and paths in cubes, SIAM J. Discrete Mathematics, to appear.

Brandenburg, F.J., Jünger, M., Mutzel, P., Algorithms for automatic graph drawing, Technical Report, Max Planck Institute, MPI-I-97-1-007, Saarbrücken, March 1997, (in German).

Catarci, T., The assignment heuristics for crossing reduction, IEEE Transactions on Systems, Man and Cybernetics 25 (1995), 515-521.

Chung, F.R.K., Spectral Graph Theory, Regional Conference Series in Mathematics Number 92, American Mathematical Society, Providence, RI, 1997.

Chung, F.R.K., Füredi, Z., Graham, R.L., Seymour, P.D., On induced subgraphs of the cube, J. Combinatorial Theory (A) 49 (1988), 180-187.

Di Battista,J., Eades, P., Tamassia, R., Tollis, I.G., Algorithms for drawing graphs: an annotated bibliography, Computational Geometry 4 (1994), 235-282.

Eades, P., Wormland, N., Edge crossings in drawings of bipartite graphs, Algorithmica 11 (1994), 379-403.

Garey, M.R., Johnson, D.S., Crossing number is NP-complete, SIAM J. Algebraic and Discrete Methods 4 (1983), 312-316.

Harary, F., Determinants, permanents and bipartite graphs, Mathematical Magazine 42 (1969), 146-148.

Harary, F., Schwenk, A., A new crossing number for bipartite graphs, Utilitas Mathematica 1 (1972), 203-209.

Harper, L.H., Optimal assignements of numbers to vertices, SIAM J. Applied Mathematics 12 (1964), 131-135.

Jünger, M., Mutzel, P., Exact and heuristic algorithm for 2-layer straightline crossing number, in: Proc. Graph Drawing '95, Lecture Notes in Computer Science 1027, Springer Verlag, Berlin, 1996, 337-348.

Juvan, M., Mohar, B., Optimal linear labelings and eigenvalues of graphs, Discrete Applied Mathematics 36 (1992), 153-168.

Muradyan, D.O., Philiposian, T.E., Minimal numberings of vertices of a rectangular lattice, Akad. Nauk Armjan. SSR Doklady 70 (1980), 21-27, (in Russian).

May, M., Szkatula, K., On the bipartite crossing number, Control and Cybernetics 17 (1988), 85-98.

Shahrokhi, F., Sykora, O., Székely, L.A., Vrt'o, On bipartite crossings, biplanar subgraphs, and the linear arrangement problem, in: Proc. 5th Workshop Algorithms and Data Structures, (WADS '97), August 6-8, 1997 Halifax, Nova Scotia, Canada, Lecture Notes in Computer Science Vol. 1272, Springer-Verlag, 55-68.

F. Shahrokhi, L.A. Székely, I. Vrt'o, Crossing numbers of graphs, lower bound techniques and algorithms: a survey, in: Proc. DIMACS Workshop on Graph Drawing '94, Lecture Notes in Computer Science 894, Springer Verlag, Berlin, 1995, 131-142.

Spinrad, J., Brandstädt, A., Stewart, L., Bipartite permutation graphs, Discrete Applied Mathematics 19, 1987, 279-292.

Sugiyama, K., Tagawa, S., Toda, M., Methods for visual understanding of hierarchical systems structures, IEEE Transactions on Systems, Man and Cybernetics 11 (1981), 109-125.

Tutte, W.T., Graph Theory, Addison-Wesley Publishing Company, Reading, 1984.

Warfield, J., Crossing theory and hierarchy mapping, IEEE Transactions on Systems, Man and Cybernetics 7 (1977), 502-523.

Watkins, M.E., A special crossing number for bipartite graphs: a research problem, Annals of New York Academy Sciences 175 (1970), 405-410.