A Characterization of Planar Graphs by Pseudo‐Line Arrangements

Let Γ be an arrangement of pseudo‐lines, i.e., a collection of unbounded x ‐monotone curves in which each curve crosses each of the others exactly once. A pseudo‐line graph (Γ, E) is a graph for which the vertices are the pseudo‐lines of Γ and the edges are some unordered pairs of pseudo‐lines of Γ. A diamond of a pseudo‐line graph (Γ, E) is a pair of edges {p,q} , {p',q'}∈ E , {p,q} ∩ {p',q'}= Ø, such that the crossing point of the pseudo‐lines p and q lies vertically between p' and q' and the crossing point of p' and q' lies vertically between p and q . We show that a graph is planar if and only if it is isomorphic to a diamond‐free pseudo‐line graph. An immediate consequence of this theorem is that the O(k1/3n) upper bound on the k ‐level complexity of an arrangement of straight lines, which was very recently discovered by Dey, holds for an arrangement of pseudo‐lines as well.