Graphs Drawn With Some Vertices per Face: Density and Relationships
Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, Alessandra Tappini · IEEE Access · 2024
Graph drawing beyond planarity is a research area that has received an increasing attention in the last twenty years, driven by the necessity to mitigate the visual complexity inherent in geometric representations of non-planar graphs. This research area stems from the study of graph layouts with forbidden crossing configurations, a well-established subject in geometric and topological graph theory. In this context, the contribution of this paper is as follows: (i) We introduce a new hierarchy of graph families, calledk+-real face graphs; for any integerk≥ 1, a graphGis ak+-real face graph if it admits a drawing Γ in the plane such that the boundary of each face (formed by vertices, crossings, and edges) contains at leastkvertices ofG(“k+” stands forkor more). (ii) We give tight upper bounds on the edge density ofk+-real face graphs, namely we prove thatn-vertex 1+-real face and 2+-real face graphs have at most 5n–10 and 4n–8 edges, respectively. Furthermore, in a constrained scenario in which all vertices must lie on the boundary of the external face, 1+-real face and 2+-real face graphs have at most 3n–6 and 2.5n–4 edges, respectively. (iii) We characterize the complete graphs that admit ak+-real face drawing or an outerk+-real face drawing for anyk≥ 1. We also provide a clear picture for the majority of complete bipartite graphs. (iv) We establish relationships betweenk+-real face graphs and other prominent beyond-planar graph families; notably, we show that for anyk≥ 1, the class ofk+-real face graphs is not included in any family of beyond-planar graphs with hereditary property.