Logo

Login | Create Account

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. [Conference Paper]

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
Classifications:Z Theory > Z.750 Topology
ID Code:603
Deposited By:Selbach, Anna
Deposited On:21 Jul 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=360

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

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

9. 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.

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

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

12. 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.

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

14. 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.

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

16. Odenthal, T., Personal communication, 2002.

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

18. 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.

19. 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.

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

21. 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.

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.