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): 11, Downloads (12 Months): 33, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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 and R. Bruce Richter. Arrangements, circular arrangements and the crossing number of C7 x Cn. J. Combin. Theory Ser. B, 90(1):21--39, 2004.
	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. Theoret. Comput. Sci., 209(1-2):1--45, 1998.
	5	Drago Bokal. On the crossing numbers of cartesian products with paths. J. Combin. Theory Ser. B, 97(3):381--384, 2007.
	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, Gašper Fijavz, and Bojan Mohar. The minor crossing number. SIAM J. Discrete Math., 20(2):344--356, 2006.
	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, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS '05), pp. 637--646. IEEE, 2005.
	12	Josep Díaz, Norman Do, Maria J. Serna, and Nicholas C. Wormald. Bounds on the max and min bisection of random cubic and random 4-regular graphs. Theoret. Comput. Sci., 307(3):531--547, 2003.
	13	Reinhard Diestel and Daniela Kühn. Graph minor hierarchies. Discrete Appl. Math., 145(2):167--182, 2005.
	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 and Gelasio Salazar. Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree. J. Graph Theory, 36(3):168--173, 2001.
	18	Micahel R. Garey and David S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312--316, 1983.
	19	James F. Geelen, R. Bruce Richter, and Gelasio Salazar. Embedding grids in surfaces. European J. Combin., 25(6):785--792, 2004.
	20	Lev Yu. Glebsky and Gelasio Salazar. The crossing number of Cm x Cn is as conjectured for n ≥ m(m + 1). J. Graph Theory, 47(1):53--72, 2004.
	21	Petr Hlinény. Crossing-number critical graphs have bounded path-width. J. Combin. Theory Ser. B, 88(2):347--367, 2003.
	22	Petr Hlinény. Crossing number is hard for cubic graphs. J. Combin. Theory Ser. B, 96(4):455--471, 2006.
	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 and Bojan Mohar. Some recent progress and applications in graph minor theory. Graphs Combin., 23(1):1--46, 2007.
	25	Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. In Proc. 39th Annual ACM Symposium on Theory of Computing (STOC '07), pp. 382--390. ACM, 2007.
	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. J. Graph Theory, 36(1):8--23, 2001.
	31	János Pach, Farhad Shahrokhi, and Mario Szegedy. Applications of the crossing number. Algorithmica, 16(1):111--117, 1996.
	32	János Pach and Micha Sharir. On the number of incidences between points and curves. Combin. Probab. Comput., 7(1):121--127, 1998.
	33	János Pach and Géza Tóth. Which crossing number is it anyway? J. Combin. Theory Ser. B, 80(2):225--246, 2000.
	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? In Giuseppe Di Battista, editor, Proc. 5th Int. Symp. on Graph Drawing (GD '97), vol. 1353 of Lecture Notes in Comput. Sci., pp. 248--261, 1997.
	37	Helen C. Purchase. Performance of layout algorithms: Comprehension, not computation. J. Visual Languages and Computing, 9:647--657, 1998.
	38	Helen C. Purchase, Robert F. Cohen, and Murray I. James. An experimental study of the basis for graph drawing algorithms. ACM Journal of Experimental Algorithmics, 2(4), 1997.
	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 and Jozef Sirán. The crossing number of K_3;n in a surface. J. Graph Theory, 21(1):51--54, 1996.
	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 and Paul D. Seymour. Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory Ser. B, 89(1):43--76, 2003.
	45	Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner's conjecture. J. Combin. Theory Ser. B, 92(2):325--357, 2004.
	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. Combin. Probab. Comput., 6(3):353--358, 1997.
	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.