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&nbsp;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.

### 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 (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.
##### Scheda breve Scheda completa Scheda completa (DC)
2023
978-3-031-43379-5
978-3-031-43380-1
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/11391/1564744`
• ND
• 2
• ND