We continue the study of the area requirement of 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 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 12 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 (3 n- 7 ) × (3 n- 7 )/ 2 by Chrobak, Goodrich and Tamassia.

Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution

Montecchiani F.;
2022

Abstract

We continue the study of the area requirement of 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 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 12 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 (3 n- 7 ) × (3 n- 7 )/ 2 by Chrobak, Goodrich and Tamassia.
978-3-031-06677-1
978-3-031-06678-8
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/1532675
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact