78 CHAPTER 2. CROSSINGS AND PLANARIZATION
estimating the number of the produced crossings, ar e relatively simply. The hard part is to
show a matching lower bound in order to deduce the approximation factor.
In 2007, Gitler et al. s howed in [GHLS08] that cr(G) is approximable within a factor of
4.5∆
2
when considering projective graphs, i.e., graphs that are embeddable in the projective
plane. One may think of such a projective plane as a large circular area A, on which to draw
the graph without any cros si ngs . Any line leaving A re-enters A exactly at the opposite
position. Consequently, any vertex drawn on the border of A is mirrored on the opposite
side as well. The key idea of the approximation algorithm now is to take such a drawing,
paste