New Exact Results and Bounds for Bipartite Crossing Numbers of Meshes

Newton, Matthew and Sýkora, Ondrej and Uzovic, Martin and Vrt'o, Imrich (2004) New Exact Results and Bounds for Bipartite Crossing Numbers of Meshes. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 360-370 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_36).

Full text not available from this repository.

Abstract

The bipartite crossing number of a bipartite graph is the minimum number of crossings of edges when the partitions are placed on two parallel lines and edges are drawn as straight line segments between the lines. We prove exact results, asymtotics and new upper bounds for the bipartite crossing numbers of 2-dimensional mesh graphs. We especially show that bcr(P6 × Pn) = 35n – 47, for n >= 7. This research was supported by the EPSRC grant GR/R37395/01 and by VEGA grant No. 2/3164/23.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_36
Classifications:Z Theory > Z.750 Topology
ID Code:603

Repository Staff Only: item control page

References

Chung, F. R. K., A conjectured minimum valuation tree, SIAM Review 20 (1978), 601-604.

Demetrescu, C., Finocchi, I., Removing cycles for minimizing crossing, ACM Journal of Experimental Algorithms 6 (2001).

Di Battista, J., Eades, P., Tamassia, R., Tollis, I.G., Graph DRawing, Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

Erdös, P., Guy, R. P., Crossing number problem, American Mathematical Monthly 80 (1973), 52-58.

Eades, P., Wormald, 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 Journal on 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.

Jünger, M., Mutzel, P., 2-layer straight line crossing minimization: performance of exact and heuristic algorithms, Journal of Graph Algorithms and Applications 1 (1997), 1-25.

Leighton, F. T., Complexity Issues in VLSI, MIT Press, 1983.

Martí, R., A tabu search algorithm for the bipartite drawing problem, European Journal of Operation Research 106 (1998), 558-569.

Matuszewski, C., Schönfeld, R., Molitor, P., Using sifting for k-layer crossing minimization, in: Proc. 7th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 1731, Springer, Berlin, 2001, 217-224.

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

Newton, M., Sýkora, O., Vrt'o, I., Two new heuristic for two-sided bipartite graph drawings, in: Proc. 10th Intl. Symposium on Graph Drawing, Lecture Notes in Computer Science 2528, Springer, Berlin, 2002, 312-319.

Pach, J., Agarwal, P. K., Combinatorial Geometry, Wiley and Sons, New York, 1995.

Odenthal, T., Personal communication, 2002.

Sarrafzadeh, M., An Introduction to VLSI Physical Design, McGraw-Hill, New York, 1995.

Shahrokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I.: On the bipartite drawings and the linear arrangement problem, 5th Intl. Workshop on Algorithms and data Structures, Lecture Notes in Computer Science 1272, Springer, Berlin, 1997, 55-68.

Shahrokhi, F., Sýkora, O., Székely, L. A., Vrt'o, I., A new lower bound for the bipartite crossing number with applications, Theoretical Computer Science 245 (2000), 281-294.

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.

Warfield, J., Crossing theory and hierarchy mapping, IEEE Transactions on Systems, Man and Cybernetic 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.