Suppose that the you have a polyhedron, $P$, which is not convex with $N$ vertices, $O(N)$ faces, and $O(N)$ edges. You are given the vertices of the polyhedron along with the edges incident on each vertex.
Is there a way to find all faces of $P$ in $O(N)$ time?