Drawings of projective graphs in orientable surfaces
by
Gelasio Salazar
IICO-UASLP

Let S be a fixed orientable surface. It is well-known that if a graph G has a sufficiently dense embedding in the projective plane, then G does not embed in S. It is natural then to ask what is the best way to draw G in S (necessarily allowing crossings of edges, since G does not embed in S). Thus, it is natural to ask what is the crossing number cr_S(G) of G in the surface S.

Naturally, one would expect that if G embeds in the projective plane more densely than H, then cr_S(G) > cr_S(H). Before proceeding to such an investigation, however, one must precisely define a parameter to measure how densely a graph G embeds in a surface (in this case the projective plane). Such possible parameters include the representativity (or face-width) r(G) (extensively used in the Robertson-Seymour theory), the edge-width ew(G), and the dual edge-width ew^*(G).

A couple of years ago we proved that for each orientable surface S, there is a constant c_S such that if G embeds in the projective plane with representativity r, then cr_S(G) > c_S r² (that is, the crossing number in S of projective graphs is quadratic in the representativity). However, it is easy to give examples of graphs that embed in the projective plane with small representativity, but whose crossing numbers (in the plane, for instance) are arbitrarily large.

These examples exhibit one common feature: their dual edge-width is very large. Moreover, since the crossing number of these graphs seems to be quadratic in their dual edge-width, it is natural to ask if the crossing number in S of projective graphs is quadratic in the dual edge-width. In this talk we show that this statement is indeed true, if (and only if) the projective graphs satisfy certain additional connectivity conditions.

Date received: November 29, 2000