ABSTRACT

Recall that in a rectilinear (also called geometric or straight-line) drawing of a graph, edges are realized by straight-line segments (without bends). The rectilinear crossing number, cr ¯   ( G ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315152394/76a56b35-285a-4240-990f-b454c3e374e6/content/eq287.tif"/> , of a graph G is the smallest number of crossings in any rectilinear drawing of G. If cr ¯   ( G )   =   0 https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315152394/76a56b35-285a-4240-990f-b454c3e374e6/content/eq288.tif"/> , then G is planar, and, as it turns out, the reverse is also true, a result known by many names.