In this work, we continue the study of the area required for convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge in the drawing is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces, and computes a convex straight-line drawing with edge-vertex resolution at least [Formula presented] on an integer grid of size (n−2+a)×(n−2+a), where a=min⁡{n−3,f}. Our result improves the previously best-known area bound of (3n−7)×(3n−7)/2 by Chrobak, Goodrich and Tamassia.

### Convex grid drawings of planar graphs with constant edge-vertex resolution

#### Abstract

In this work, we continue the study of the area required for convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge in the drawing is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces, and computes a convex straight-line drawing with edge-vertex resolution at least [Formula presented] on an integer grid of size (n−2+a)×(n−2+a), where a=min⁡{n−3,f}. Our result improves the previously best-known area bound of (3n−7)×(3n−7)/2 by Chrobak, Goodrich and Tamassia.
##### Scheda breve Scheda completa Scheda completa (DC)
2024
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/1569359`
• ND
• 0
• 0