The edge-length ratio of a straight-line drawing of a graph is the ratio between the lengths of the longest and of the shortest edge in the drawing. The planar edge-length ratio of a planar graph is the minimum edge-length ratio of any planar straight-line drawing of the graph. In this paper, we study the planar edge-length ratio of planar graphs. We prove that there exist n-vertex planar graphs whose planar edge-length ratio is in Ω(n); this bound is tight. We also prove upper bounds on the planar edge-length ratio of several families of planar graphs, including series-parallel graphs and bipartite planar graphs.
Borrazzo, M., Frati, F. (2020). On the planar edge-length ratio of planar graphs. JOURNAL OF COMPUTATIONAL GEOMETRY, 11(1), 137-155.
On the planar edge-length ratio of planar graphs
Manuel borrazzo;fabrizio frati
2020-01-01
Abstract
The edge-length ratio of a straight-line drawing of a graph is the ratio between the lengths of the longest and of the shortest edge in the drawing. The planar edge-length ratio of a planar graph is the minimum edge-length ratio of any planar straight-line drawing of the graph. In this paper, we study the planar edge-length ratio of planar graphs. We prove that there exist n-vertex planar graphs whose planar edge-length ratio is in Ω(n); this bound is tight. We also prove upper bounds on the planar edge-length ratio of several families of planar graphs, including series-parallel graphs and bipartite planar graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
