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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/603

Actions (login required)

View Item View Item