Nonplanar Graph Drawings with k Vertices per Face

The study of nonplanar graph drawings with forbidden or desired crossing configurations has a long tradition in geometric graph theory, and received an increasing attention in the last two decades, under the name of beyond-planar graph drawing. In this context, we introduce a new hierarchy of graph families, called k+-real face graphs. For any integer (Formula presented), a graph G is a k+-real face graph if it admits a drawing (Formula presented) in the plane such that the boundary of each face (formed by vertices, crossings, and edges) contains at least k vertices of G. We give tight upper bounds on the maximum number of edges of k+-real face graphs. In particular, we show that 1+-real face and 2+-real face graphs with n vertices have at most 5n-10 and 4n-8 edges, respectively. Also, if all vertices are constrained to be on the boundary of the external face, then 1+-real face and 2+-real face graphs have at most 3n-6 and 2.5n-4 edges, respectively. We also study relationships between k+-real face graphs and beyond-planar graph families with hereditary property.