On the rectilinear crossing number of complete graphs

U. Wagner, in:, SIAM, 2003, pp. 583–588.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published
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-01
Page
583 - 588
Conference
SODA: Symposium on Discrete Algorithms
IST-REx-ID

Cite this

Wagner U. On the rectilinear crossing number of complete graphs. In: SIAM; 2003:583-588.
Wagner, U. (2003). On the rectilinear crossing number of complete graphs (pp. 583–588). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.
Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs,” 583–88. SIAM, 2003.
U. Wagner, “On the rectilinear crossing number of complete graphs,” presented at the SODA: Symposium on Discrete Algorithms, 2003, pp. 583–588.
Wagner U. 2003. On the rectilinear crossing number of complete graphs. SODA: Symposium on Discrete Algorithms 583–588.
Wagner, Uli. On the Rectilinear Crossing Number of Complete Graphs. SIAM, 2003, pp. 583–88.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar