New bounds on crossing numbers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New bounds on crossing numbers

Full text

Pdf (897 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifteenth annual symposium on Computational geometry table of contents

Miami Beach, Florida, United States

Pages: 124 - 133

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

János Pach	Courant Institute, NYU and Hungarian Academy of Sciences
Joel Spencer	Courant Institute, NYU
Géza Tóth	Massachusetts Institute of Technology and Hungarian Academy of Sciences

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/304893.304943 What is a DOI?

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.

	ACNS82	M. Ajtai, V. Chv#tal, M. Newborn, and E. Szemer#di, Crossing-free subgraphs, in: Theory and Practice o/ Combinatorics, North-Holland Math. Stud. 60# North-Holland, Amsterdam-New York, 1982, 9-12.
	ARS98	N. Alon, L. R6nyai, and T. Szab6, Normgraphs: variations and applications, to appear.
	AST90	N. Alon, P. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, J. Amer. Math. Soc. 3 (1990), 801-808.
	AST94	Noga Alon , Paul Seymour , Robin Thomas, Planar Separators, SIAM Journal on Discrete Mathematics, v.7 n.2, p.184-193, May 1994 [doi>10.1137/S0895480191198768]
	Be66	C. Benson, Minimal regular graphs of girth eight and twelve, Canadian J. Mathematics 18 (1966), 1091-1094.
	BS74	J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory, Set. B 16 (1974), 97-105.
	B66	W. G. Brown, On graphs that do not contain a Thomsen graph, Canadian Mathematical Bulletin 9 (1966), 281-285.
	D98	T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry 19 (1998), 373-382.
	EG73	P. Erd6s and R. K. Guy, Crossing number problems, American Mathematical Monthly 80 (1973), 52- 58.
	ER62	P. Erd6s and A. R#nyi, On a problem in the theory of graphs, (in Hungarian), Magyar Tud. Akad. Mat. Kutatd Int. Kiizl. 7 (1962), 623-641.
	F96	Zoltán Füredi, New asymptotics for bipartite Tura´n numbers, Journal of Combinatorial Theory Series A, v.75 n.1, p.141-144, July 1996 [doi>10.1006/jcta.1996.0067]
	GJ83	M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4 (1983), 312-316.
	G72	R. K. Guy, Crossing numbers of graphs, in: Graph theory and applications (Proc. Conf. Western Michigan Univ., Kalamazoo, Mich., 1972) Lecture Notes in Mathematics 303, Springer, Berlin, 111-124.
	KST54	T. K6v#ri, V. T. S6s, and P. Tur~n, On a problem of K. Zarankiewicz, Colloquium Mathematicum 3 (1954), 50-57.
	L83	F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983.
	L84	F. T. Leighton, New lower bound techniques for VLSI, Math. Systems Theory 17' (1984), 47-70.
	LT79	R. Lipton and R. Tarjan, A separator theorem for planar graphs, SIAM J. Applied Mathematics 3{} (1979), 177-189.
	PSS96	J. Pach, F. Shahrokhi, and M. Szegedy, Applications of the crossing number, Algorithmica 16 (1996), 111-117.
	PS98	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]
	PT97	J. Pach and G. T6th, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), 427-439.
	R58	I. Reiman, #)ber ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9 (1958), 269-279.
	RT97	R. B. Richter and C. Thomassen, Relations between crossing numbers of complete and complete bipartite graphs, American Mathematical Monthly, February 1997, 131-137.
	RY68	G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438-445.
	S97	M. Simonovits, personal communication.
	S66	R. Singleton, On minimal graphs of maximum even girth, J. Combinatorial Theory 1 (1966), 306- 332.
	S98	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]
	W91	R. Wenger, Extremal graphs with no C4,s, or C10,s, Journal of Combinatorial Theory Series B, v.52 n.1, p.113-116, May 1991 [doi>10.1016/0095-8956(91)90097-4]
	WB78	A. T. White and L. W. Beineke, Topological graph theory, in: Selected Topics in Graph Theory (L. W. Beineke and R. J. Wilson., eds.), Academic Press, Inc. {Harcourt Brace Jovanovich, Publishers}, London- New York, 1983, 15-49.