Bekos, M. A., Gronemann, M., Montecchiani, F., & Symvonis, A. (2022). Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution. In Combinatorial Algorithms (pp. 157–171). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-06678-8_12
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
Combinatorial Algorithms
-
ISBN:
978-3-031-06678-8
-
Volume:
13270
-
Date (published):
29-May-2022
-
Event name:
33rd International Workshop on Combinatorial Algorithms (IWOCA 2022)
en
Event date:
7-Jun-2022 - 9-Jun-2022
-
Event place:
Trier, Germany
-
Number of Pages:
15
-
Publisher:
Springer Nature Switzerland AG
-
Peer reviewed:
Yes
-
Keywords:
Area requirement; Convex grid drawings; Edge-vertex resolution; Graph drawing
en
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.
