Drawing graphs with k vertices per face: Complexity and algorithms

A drawing Γ of a graph G divides the plane into topologically connected regions, called faces (or cells). The boundary of each face is formed by vertices, crossings, and edge portions. Given a positive integer k, we say that Γ is a k+-real face drawing of G if the boundary of each face of Γ contains at least k vertices of G. Graphs that admit a k+-real face drawing are k+-real face graphs; they have been studied so far in terms of edge density and inclusion relationships with other notable classes of nonplanar graphs that can be drawn avoiding specific crossing configurations. In this paper, we investigate the complexity of recognizing k+-real face graphs, that is, the complexity of testing whether a given graph is k+-real face, for desired values of k. We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are drawn as straight-line segments. While we prove NP-completeness results for the unconstrained scenario, we describe efficient recognition algorithms for the 2-layer setting.