and all 0-outdegree vertices appear on the same face (often assumed to be the outer face), and it is possible to partition the boundary of that face into two parts such that all 0-indegree vertices appear on one part, and all0-outdegree vertices appear on the other (i.e. the two types of vertices do not alternate).

If exhibits these properties, then we can preprocess the graph in only time, and store only extra bits per vertex, answeringreachability