queries for any pair of vertices in time with a simplecomparison.

Preprocessing performs the following steps. We add a new vertex which has an edge to each 0-indegree vertex, and another new vertex with edges from each 0-outdegree vertex. Note that the properties of allow us to do so while maintaining planarity, that is, there will still be no edge crossings after these additions. For each vertex we store the list of adjacencies (out-edges) in order of the planarity of the graph (for example, clockwise with respect to the graph's