On the Planar Edge-Length Ratio of Planar Graphs

DOI10.1007/978-3-030-35802-0_13MaRDI QIDQ6323458arXivFDO

Authors Manuel Borrazzo, Fabrizio Frati

Publication date 9 August 2019

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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 $Omega(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.

This page was built for publication: On the Planar Edge-Length Ratio of Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323458)