Crossing Numbers of Graphs, Lower Bound Techniques and Algorithms: A Survey

Shahrokhi, Farhad and Székely, László A. and Vrt'o, Imrich (1995) Crossing Numbers of Graphs, Lower Bound Techniques and Algorithms: A Survey. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 131-142 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_364).

Full text not available from this repository.

Abstract

We give a survey of recent techniques for deriving lower bounds and algorithms for constructing upper bounds for several variations of the crossing number problem. Our aim is to emphasize the more general results or those results which have an algorithmic flavor, including the recent results of the outhors.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_364
Classifications:Z Theory > Z.001 General
G Algorithms and Complexity > G.420 Crossings
A General Literature > A.001 Introductory and Survey
ID Code:129

Repository Staff Only: item control page

References

Ajtai, M., Chvátal, V., Newborn, M., M., Szemerédy, E., "Crossing-free subgraphs", Annals of Discrete Mathematics 12 (1982), 9-12.

Alon, N., Spencer, J.H., Erdös, P., "The Probabilistic Method", Wiley and Sons, New York, 1992.

Batini, C., Nardelli, E., Talamo, M., Tamassia, R., A graphtheoretic approach to aesthetic layout of information syste4ms diagrams, in: Proc. 10th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Trauner <verlag, Berlin, 1984, 9-18.

Beineke, L. W., Ringeisen, R.D, On the crossing number product of cycless and graphs of order four, J. Graph Theory4 (1980), 145-155.

Bienstock, D., Dean, N., "New results on rectilinear crossing Numbers and Plane Embeddings", J. Graph Theory, 16 (1992), 389-398.

Bienstock, D., Dean, N., "Bounds on the rectilinear crossing Numbers", J. Graph Theory 17 (1993), 333-348.

Bhatt, S., N., Leighton, F., T., "A framework for Solving VLSI Graph Layout Problems", Journal of Computer and System Sciences 28 (1984), 300-343.

Chung, F. R. K., Yau, S.T., "A near optimal algorithm for edge seperators", in: Proc. 26th Annual ACM Symposium on the Theory on Computing , ACM, New York, 1994, 1-8.

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

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

Fáry, I., "On Straight Line Representations of Graphs", Acta Univ. Szeged Sect. Sci. Math., 11, 1948, 229-233.

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

Gazit, H., Miller, G.L., Planar seperators and the Euclidean norm, in: Proc. Algorithms, Intl. Symp. SIGAL '90, Lecture Notes in Computer Science 450, Springer Verlag, Berlin, 1990, 338-347.

Gross, J. L., On infinite family of octahedral crossing numbers, J. Graph Theory 2 (1978), 171-178.

Guy, R.K., A combinatorial problem, Nabla (Bull. Malayan Math. Soc.) 7 (1960), 68-72.

Guy, R.K., Jenkins, T., Schaer, J., The toroidal crossing number of the complete graph, J. Combinatorial Theory 4 (1968), 376-390.

Guy, R.K., Jenkins, T., The toroidal crossing number of K_{m,n,} J. Combinatorial Theory 6 (1969), 235-250.

Kainen, P. C., A lower bound for crossing number of graphs with aplications to K_{n}, K_{p,q} and Q(d), J. Combinatorial Theory (B) 12 (1972), 287-298.

Kainen, P. C., White, A.T., On stable crossing numbers, J. Graph Theory 2 (1978) 181-187.

Kleitman, D. J., The crossing number of K_ {5,n}, J. Combinatorial Theory 9 (1970), 315-323.

Leighton, F. T., Complexity Issues in VLSI, MIT Press, Cambridge, 1983. Malitz, S.M., "Genus g Graphs have Pagenumber 0(\sqrt{g})", Journal of Algorithms, 17 (1), 84-109, 1994.

Madej, T., Bounds for the crossing number of the n-cube, J. Graph Theory 15 (1991), 81-97.

Pica, G., Pisanski., T., Ventre, A.G.S., "Cartesian product of graphs and their crossing numbers, Annals of Discrete Mathematics 30 (1986), 339-346.

Pach, J., Shahrokhi, F., Szegedy, M., Applications of crossing numbers, in: Proc. 10th Annual ACM Symposium on Computational Geometry, ACM, New York, 1994.

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt'o, I., The crossing number of a graph on a compact 2-manifold, Advances in Mathematics, to appear.

Shahrokhi, F., Székely, L.A., "Effective lower bounds for crossing number, bisection width and balanced vertex separators in terms of symmetry", in: Proc. 2nd IPCO Conf., Pittsburgh, 1992, 102-113, also to appear in Combinatorics, Probability and Computing.

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt'o, I., "Improved bounds for the crossing numbers on surfaces of genus g", in: Proc. 19-th Intl. Workshop on Graph-Theoretic Concepts in Computer Science WG'93, Lecture Notes in Computer Science, Springer Verlag, Berlin 1994, 388-395, to appear in Algorithmica.

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt'o, I., "On Book Embeddings and Crossing Numbers" to appear in Proc. 20-th Intl.Workshop on Graph-Theoretic Concepts in Computer Science WG'94, Lecture Notes in Computer Science, Springer Verlag, Berlin 1995.

Sýkora, O., Vrt'o, I., Edge separators for graphs of bounded genus with applications, Theoretical Computer Science 112 (1993), 419-429.

Sýkora, O., Vrt'o., On VLSI layout of the star graph and related networks, Integration, the VLSI Journal 17 (1994), 83-93.

White, A. T., Beineke, L. W., Topological graph theory, in: Selected Topics in Graph Theory, eds. L. W. Beineke and R. J. Wilson, Academic Press, 1978, 15-50.