---
OA_type: closed access
_id: '2422'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
author:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Wagner U. On the rectilinear crossing number of complete graphs. In: <i>Proceedings
    of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>. SIAM;
    2003:583-588. doi:<a href="https://doi.org/10.5555/644108.644206">10.5555/644108.644206</a>'
  apa: 'Wagner, U. (2003). On the rectilinear crossing number of complete graphs.
    In <i>Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms</i>
    (pp. 583–588). Baltimore, MD, United States: SIAM. <a href="https://doi.org/10.5555/644108.644206">https://doi.org/10.5555/644108.644206</a>'
  chicago: Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs.” In
    <i>Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    583–88. SIAM, 2003. <a href="https://doi.org/10.5555/644108.644206">https://doi.org/10.5555/644108.644206</a>.
  ieee: U. Wagner, “On the rectilinear crossing number of complete graphs,” in <i>Proceedings
    of the fourteenth annual ACM-SIAM symposium on Discrete algorithms</i>, Baltimore,
    MD, United States, 2003, pp. 583–588.
  ista: '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.'
  mla: Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs.” <i>Proceedings
    of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms</i>, SIAM,
    2003, pp. 583–88, doi:<a href="https://doi.org/10.5555/644108.644206">10.5555/644108.644206</a>.
  short: U. Wagner, in:, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on
    Discrete Algorithms, SIAM, 2003, pp. 583–588.
conference:
  end_date: 2003-01-14
  location: Baltimore, MD, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2003-01-12
date_created: 2018-12-11T11:57:34Z
date_published: 2003-01-12T00:00:00Z
date_updated: 2026-05-28T08:18:32Z
day: '12'
doi: 10.5555/644108.644206
extern: '1'
language:
- iso: eng
main_file_link:
- url: http://dl.acm.org/citation.cfm?id=644206
month: '01'
oa_version: None
page: 583 - 588
publication: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms
publication_identifier:
  isbn:
  - '9780898715385'
publication_status: published
publisher: SIAM
publist_id: '4503'
quality_controlled: '1'
status: public
title: On the rectilinear crossing number of complete graphs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2003'
...