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: 1) We introduce a new hierarchy of graph families, called k+ -real face graphs; for any integer k ge q 1 , a graph G is a k+ -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 least k vertices of G ('k+ ' stands for k or more); 2) We give tight upper bounds on the edge density of k+ -real face graphs, namely we prove that n-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; 3) We characterize the complete graphs that admit a k+ -real face drawing or an outer k+ -real face drawing for any k ≥q 1. We also provide a clear picture for the majority of complete bipartite graphs; and 4) We establish relationships between k+ -real face graphs and other prominent beyond-planar graph families; notably, we show that for any k ≥q 1 , the class of k+ -real face graphs is not included in any family of beyond-planar graphs with hereditary property.

Binucci, C., Di Battista, G., Didimo, W., Dujmovic, V., Hong, S.-., Kaufmann, M., et al. (2024). Graphs Drawn With Some Vertices per Face: Density and Relationships. IEEE ACCESS, 12, 68828-68846 [10.1109/ACCESS.2024.3401078].

Graphs Drawn With Some Vertices per Face: Density and Relationships

Di Battista G.;
2024-01-01

Abstract

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: 1) We introduce a new hierarchy of graph families, called k+ -real face graphs; for any integer k ge q 1 , a graph G is a k+ -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 least k vertices of G ('k+ ' stands for k or more); 2) We give tight upper bounds on the edge density of k+ -real face graphs, namely we prove that n-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; 3) We characterize the complete graphs that admit a k+ -real face drawing or an outer k+ -real face drawing for any k ≥q 1. We also provide a clear picture for the majority of complete bipartite graphs; and 4) We establish relationships between k+ -real face graphs and other prominent beyond-planar graph families; notably, we show that for any k ≥q 1 , the class of k+ -real face graphs is not included in any family of beyond-planar graphs with hereditary property.
2024
Binucci, C., Di Battista, G., Didimo, W., Dujmovic, V., Hong, S.-., Kaufmann, M., et al. (2024). Graphs Drawn With Some Vertices per Face: Density and Relationships. IEEE ACCESS, 12, 68828-68846 [10.1109/ACCESS.2024.3401078].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/490757
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact