Name
Abstract | ||
|---|---|---|
ABSTRACT The crossing number , cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane Denote by (n; e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges We prove a conjecture of P Erd}os and R Guy by showing that (n; e)n2=e3 tends to a positive constant as n ! 1 and n e n2 Similar results hold for graph drawings on any other surface of xed genus We prove better bounds for graphs satisfying some monotone properties In particular, we show that if G is a graph with n vertices and e 4n edges, which does not contain a cycle of length four (resp six), then its crossing number is at least ce4=n3 (resp ce =n4), where c > 0 is a suitable constant These results cannot be improved, apart from the value of the constant This settles a question of M Simonovits |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/s004540010011 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
Discrete Comput Geom,Decomposition Algorithm,Separator Theorem,Ella,Suitable Constant | Topology,Discrete mathematics,Graph,Combinatorics,Crossing number (graph theory),Vertex (geometry),Cycle graph,Conjecture,Mathematics,Monotone polygon | Conference |
Volume | Issue | ISSN |
24 | 4 | 0179-5376 |
ISBN | Citations | PageRank |
1-58113-068-6 | 24 | 1.60 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Joel Spencer | 2 | 41 | 4.73 |
| Géza Tóth | 3 | 581 | 55.60 |