Name
Abstract | ||
|---|---|---|
We show that any set of n points in general position in the plane determines n1−o(1) pairwise crossing segments. The best previously known lower bound, Ω(√n), was proved more than 25 years ago by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3313276.3316328 | Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |
Keywords | Field | DocType |
avoiding edges, comparability graphs, computational geometry, crossing edges, extremal combinatorics, geometric graphs, intersection graphs, partial orders | Pairwise comparison,Discrete mathematics,Graph,General position,Combinatorics,Constructive,Upper and lower bounds,Omega,Planar,Mathematics | Journal |
Volume | ISSN | ISBN |
abs/1904.08845 | 0737-8017 | 978-1-4503-6705-9 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Natan Rubin | 2 | 92 | 11.03 |
| Gábor Tardos | 3 | 0 | 0.34 |