Improved upper bounds on the crossing number

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved upper bounds on the crossing number

Full text

Pdf (288 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twenty-fourth annual symposium on Computational geometry table of contents

College Park, MD, USA

SESSION: 10 table of contents

Pages 375-384

Year of Publication: 2008

ISBN:978-1-60558-071-5

Authors

Vida Dujmovic	Carleton University, Ottawa, Canada
Ken-ichi Kawarabayashi	National Institute of Informatics, Tokyo, Japan
Bojan Mohar	Simon Fraser University, Burnaby, Canada
David R. Wood	Universitat Politecnica de Catalunya, Barcelona, Spain

Sponsors

ACM: Association for Computing Machinery
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 81, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1377676.1377739 What is a DOI?

ABSTRACT

The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Δn), where G has n vertices and maximum degree Δ. This dependence on n and Ø is best possible. This result answers an open question of Wood and Telle [New York J. Mathematics, 2007], who proved the best previous bound of O(Ø²n).

In addition, we prove that every K₅-minor-free graph G has crossing number at most 2∑_v deg(v)², which again is the best possible dependence on the degrees of G. We also study the convex and rectilinear crossing numbers, and prove an O(Øn) bound for the convex crossing number of bounded pathwidth graphs, and a ∑_v deg(v)² bound for the rectilinear crossing number of K_3;3-minor-free graphs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jay Adamsson , R. Bruce Richter, Arrangements, circular arrangements and the crossing number of C7× Cn, Journal of Combinatorial Theory Series B, v.90 n.1, p.21-39, January 2004 [doi>10.1016/j.jctb.2003.05.001]
	2	Miklós Ajtai, Vašek Chvátal, Monroe M. Newborn, and Endre Szemerédi. Crossing-free subgraphs. In Theory and practice of combinatorics, vol. 60 of North-Holland Math. Stud., pp. 9--12. North-Holland, 1982.
	3	Sandeep N. Bhatt and F. Thomson Leighton. A framework for solving VLSI graph layout problems. J. Comput. System Sci., 28(2):300--343, 1984.
	4	Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4]
	5	Drago Bokal, On the crossing numbers of Cartesian products with paths, Journal of Combinatorial Theory Series B, v.97 n.3, p.381-384, May, 2007 [doi>10.1016/j.jctb.2006.06.003]
	6	Drago Bokal, Éva Czabarka, László A. Székely, and Imrich Vrt'o. Graph minors and the crossing number of graphs. Electron. Notes Discrete Math., 28:169--175, 2007.
	7	Drago Bokal , Gasper Fijavz , Bojan Mohar, The Minor Crossing Number, SIAM Journal on Discrete Mathematics, v.20 n.2, p.344-356, 2006 [doi>10.1137/05062706X]
	8	Drago Bokal, Gašper Fijavz, and David R. Wood. The minor crossing number of graphs with an excluded minor. Electron. J. Combin., 15(R4), 2008.
	9	Károly Böröczky, János Pach, and Géza Tóth. Planar crossing numbers of graphs embeddable in another surface. Int.. J. Found. Comput. Sci., 17(5):1005--1015, 2006.
	10	Lane H. Clark and Roger C. Entringer. The bisection width of cubic graphs. Bull. Austral. Math. Soc., 39(3):389--396, 1989.
	11	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Ken-ichi Kawarabayashi, Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.637-646, October 23-25, 2005 [doi>10.1109/SFCS.2005.14]
	12	J. Díaz , N. Do , M. J. Serna , N. C. Wormald, Bounds on the max and min bisection of random cubic and random 4-regular graphs, Theoretical Computer Science, v.307 n.3, p.531-547, 14 October 2003 [doi>10.1016/S0304-3975(03)00236-6]
	13	Reinhard Diestel , Daniela Kühn, Graph minor hierarchies, Discrete Applied Mathematics, v.145 n.2, p.167-182, 15 January 2005 [doi>10.1016/j.dam.2004.01.010]
	14	Hristo N. Djidjev and Imrich Vrt'o. Crossing numbers and cutwidths. J. Graph Algorithms Appl., 7(3):245--251, 2003.
	15	Hristo N. Djidjev and Imrich Vrt'o. Planar crossing numbers of genus g graphs. In Michele. Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Proc. 33rd Int. Colloquium on Automata, Languages and Programming (ICALP '06), vol. 4051 of Lecture Notes in Comput. Sci., pp. 419--430, 2006.
	16	Paul Erdõs and Richard K. Guy. Crossing number problems. Amer. Math. Monthly, 80:52--58, 1973.
	17	Enrique Garcia-Moreno , Gelasio Salazar, Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree, Journal of Graph Theory, v.36 n.3, p.168-173, March 2001 [doi>10.1002/1097-0118(200103)36:3<>1.0.CO;2-S]
	18	Micahel R. Garey and David S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312--316, 1983.
	19	J. F. Geelen , R. B. Richter , G. Salazar, Embedding grids in surfaces, European Journal of Combinatorics, v.25 n.6, p.785-792, August 2004 [doi>10.1016/j.ejc.2003.07.007]
	20	Lev Yu. Glebsky , Gelasio Salazar, The crossing number of C_m × C_n is as conjectured for n ≥ m(m + 1), Journal of Graph Theory, v.47 n.1, p.53-72, September 2004 [doi>10.1002/jgt.v47:1]
	21	Petr Hliněny, Crossing-number critical graphs have bounded path-width, Journal of Combinatorial Theory Series B, v.88 n.2, p.347-367, July 2003 [doi>10.1016/S0095-8956(03)00037-6]
	22	Petr Hliněný, Crossing number is hard for cubic graphs, Journal of Combinatorial Theory Series B, v.96 n.4, p.455-471, July 2006 [doi>10.1016/j.jctb.2005.09.009]
	23	Robert E. Jamison and Renu Laskar. Elimination orderings of chordal graphs. In Combinatorics and Applications, pp. 192--200. Indian Statist. Inst., 1984.
	24	Ken-Ichi Kawarabayashi , Bojan Mohar, Some Recent Progress and Applications in Graph Minor Theory, Graphs and Combinatorics, v.23 n.1, p.1-46, February 2007 [doi>10.1007/s00373-006-0684-x]
	25	Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250848]
	26	F. Thomson Leighton. Complexity Issues in VLSI. MIT Press, 1983.
	27	F. Thomson Leighton. New lower bound techniques for VLSI. Math. Systems Theory, 17(1):47--70, 1984.
	28	Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Press, 2001.
	29	Nagi H. Nahas. On the crossing number of K_m;n. Electron. J. Combin., 10:N8, 2003.
	30	Seiya Negami, Crossing numbers of graph embedding pairs on closed surfaces, Journal of Graph Theory, v.36 n.1, p.8-23, January 2001 [doi>10.1002/1097-0118(200101)36:1<>1.0.CO;2-#]
	31	János Pach, Farhad Shahrokhi, and Mario Szegedy. Applications of the crossing number. Algorithmica, 16(1):111--117, 1996.
	32	János Pach , Micha Sharir, On the Number of Incidences Between Points and Curves, Combinatorics, Probability and Computing, v.7 n.1, p.121-127, March 1998 [doi>10.1017/S0963548397003192]
	33	János Pach , Géza Tóth, Which crossing number is it anyway?, Journal of Combinatorial Theory Series B, v.80 n.2, p.225-246, Nov. 2000 [doi>10.1006/jctb.2000.1978]
	34	János Pach and Géza Tóth. Crossing number of toroidal graphs. In Patrick Healy and Nikola S. Nikolov, editors, Proc. 13th Int. Symp. on Graph Drawing (GD '05), vol. 3843 of Lecture Notes in Comput. Sci., pp. 334--342, 2006.
	35	Michael J. Pelsmajer, Marcus Schaefer, and Daniel Stefankovic. Crossing number of graphs with rotation systems. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Proc. 15th Int. Symp. on Graph Drawing (GD '07), vol. 4875 of Lecture Notes in Comput. Sci., pp. 3--12, 2007.
	36	Helen C. Purchase, Which Aesthetic has the Greatest Effect on Human Understanding?, Proceedings of the 5th International Symposium on Graph Drawing, p.248-261, September 18-20, 1997
	37	Helen C. Purchase. Performance of layout algorithms: Comprehension, not computation. J. Visual Languages and Computing, 9:647--657, 1998.
	38	H. C. Purchase , R. F. Cohen , M. I. James, An experimental study of the basis for graph drawing algorithms, Journal of Experimental Algorithmics (JEA), 2, p.4-es, 1997 [doi>10.1145/264216.264222]
	39	Bruce A. Reed. Algorithmic aspects of tree width. In Bruce A. Reed and Cláudia L. Sales, editors, Recent Advances in Algorithms and Combinatorics, pp. 85--107, 2003.
	40	R. Bruce Richter , J. Širáň, The crossing number of K3,n in a surface, Journal of Graph Theory, v.21 n.1, p.51-54, Jan. 1996 [doi>10.1002/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.0.CO;2-L]
	41	R. Bruce Richter and Carsten Thomassen. Intersections of curve systems and the crossing number of C5 x C5. Discrete Comput. Geom., 13(2):149--159, 1995.
	42	R. Bruce Richter and Carsten Thomassen. Relations between crossing numbers of complete and complete bipartite graphs. Amer. Math. Monthly, 104(2):131--137, 1997.
	43	Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309--322, 1986.
	44	Neil Robertson , P. D. Seymour, Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory Series B, v.89 n.1, p.43-76, September 2003 [doi>10.1016/S0095-8956(03)00042-X]
	45	Neil Robertson , P. D. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory Series B, v.92 n.2, p.325-357, November 2004 [doi>10.1016/j.jctb.2004.08.001]
	46	Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, and Imrich Vrt'o. The crossing number of a graph on a compact 2-manifold. Adv. Math., 123(2):105--119, 1996.
	47	Farhad Shahrokhi and László A. Székely. On canonical concurrent flows, crossing number and graph expansion. Combin. Probab. Comput., 3(4):523--543, 1994.
	48	Farhad Shahrokhi, László A. Székely, Ondrej Sýkora, and Imrich Vrt'o. Drawings of graphs on surfaces with few crossings. Algorithmica, 16(1):118--131, 1996.
	49	László A. Székely, Crossing Numbers and Hard Erdös Problems in Discrete Geometry, Combinatorics, Probability and Computing, v.6 n.3, p.353-358, September 1997 [doi>10.1017/S0963548397002976]
	50	László A. Székely. A successful concept for measuring non-planarity of graphs: the crossing number. Discrete Math., 276(1{3):331--352, 2004.
	51	Imrich Vrt'o. Crossing numbers of graphs: A bibliography, 2007. ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf.
	52	David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor. New York J. Math., 13:117--146, 2007.