On the rectilinear crossing number of complete graphs
Wagner U. 2003. On the rectilinear crossing number of complete graphs. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. SODA: Symposium on Discrete Algorithms, 583–588.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Abstract
We prove a lower bound of 0.3288(4 n) for the rectilinear crossing number cr̄(Kn) of a complete graph on n vertices, or in other words, for the minimum number of convex quadrilaterals in any set of n points in general position in the Euclidean plane. As we see it, the main contribution of this paper is not so much the concrete numerical improvement over earlier bounds, as the novel method of proof, which is not based on bounding cr̄(Kn) for some small n.
Publishing Year
Date Published
2003-01-12
Proceedings Title
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms
Publisher
SIAM
Page
583 - 588
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Baltimore, MD, United States
Conference Date
2003-01-12 – 2003-01-14
ISBN
IST-REx-ID
Cite this
Wagner U. On the rectilinear crossing number of complete graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2003:583-588. doi:10.5555/644108.644206
Wagner, U. (2003). On the rectilinear crossing number of complete graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 583–588). Baltimore, MD, United States: SIAM. https://doi.org/10.5555/644108.644206
Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs.” In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 583–88. SIAM, 2003. https://doi.org/10.5555/644108.644206.
U. Wagner, “On the rectilinear crossing number of complete graphs,” in Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, MD, United States, 2003, pp. 583–588.
Wagner U. 2003. On the rectilinear crossing number of complete graphs. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. SODA: Symposium on Discrete Algorithms, 583–588.
Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs.” Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2003, pp. 583–88, doi:10.5555/644108.644206.
Google Scholar
ISBN Search