The pair (G,D) consisting of a planar graph \(G=(V,E)\) with n vertices together with a subset of d special vertices \(D\subseteq V\) is called k- planar if there is an embedding of G in the plane so that at most k faces of G are required to cover all of the vertices in D. Checking 1-planarity can be done in linear-time since it reduces to a problem of checking planarity of a related graph. We present an algorithm which given a graph G and a value k either determines that G is not k-planar or generates an appropriate embedding and associated minimum cover in \(O(c^ k n)\) time, where c is a constant. Hence, the algorithm runs in linear time for any fixed k. The fact that the time required by the algorithm grows exponentially in k is to be expected since we also show that for arbitrary k, the associated decision problem is strongly NP-complete, even when the planar graph has essentially a unique planar embedding, \(d=\theta (n)\), and all facial cycles have bounded length. These results provide a polynomial-time recognition algorithm for special cases of Steiner tree problems in graphs which are solvable in polynomial time.