Applications of the Crossing Number

J. Pach, F. Shahrokhi, M. Szegedy

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

Let G be a graph of n vertices that can be drawn in the plane by straight-line segments so that no k + 1 of them are pairwise crossing. We show that G has at most Ckn log2k-2 n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdos, Kupitz, Perles, and others. We also construct two point sets {p1, . . . , pn}, {q1 , . . . , qn} in the plane such that any piecewise linear one-to-one mapping f:R2 → R2 with f (pi) = qi (1 ≤ i ≤ n) is composed of at least Ω(n2) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.

Original languageEnglish (US)
Pages (from-to)111-117
Number of pages7
JournalAlgorithmica (New York)
Volume16
Issue number1
DOIs
StatePublished - Jul 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Bisection width
  • Crossing number
  • Geometric graph
  • Triangulation

Fingerprint

Dive into the research topics of 'Applications of the Crossing Number'. Together they form a unique fingerprint.

Cite this