| Autor: |
Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, Alessandra Tappini |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
IEEE Access, Vol 12, Pp 68828-68846 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2169-3536 |
| DOI: |
10.1109/ACCESS.2024.3401078 |
| Popis: |
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 \geq 1$ , a graph G is a $k^{+}$ -real face graph if it admits a drawing $\Gamma $ 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 \geq 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 \geq 1$ , the class of $k^{+}$ -real face graphs is not included in any family of beyond-planar graphs with hereditary property. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
