Nonplanar Graph Drawings with k Vertices per Face

Abstract

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 $k \ge 1$, a graph G is a $k^+$-real face graph if it admits a drawing $\varGamma$ 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.

Research started at the Summer Workshop on Graph Drawing (SWGD) 2022, and partially supported by: (i) MIUR, grant 20174LF3T8 “AHeAD: efficient Algorithms for HArnessing networked Data”; (ii) Dipartimento di Ingegneria - Università degli Studi di Perugia, Ricerca di Base, grants RICBA21LG and RICBA22CB.