A drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straight-line segments. Every cubic planar 3-connected graph with $n$ vertices has such a drawing with only $n/2 + 3$ segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings. We introduce two new algorithms that also produce drawings with $n/2 + 3$ segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.
展开▼
机译：图的绘制可以理解为几何对象的排列。在最自然的情况下，该布置由直线段形成。每个具有$ n $个顶点的立方平面3连通图都有一个这样的图形，其中只有$ n / 2 + 3 $个线段，与下限匹配。此结果归因于Mondal等。 [J.梳子Opt。，第25页]，他给出了构建此类图纸的算法。我们介绍了两种新算法，它们也可以生成具有$ n / 2 + 3 $线段的图形。一种算法基于双重边缘收缩的序列，另一种算法基于嵌套循环的递归。我们还在Mondal等人的算法中显示了一个缺陷。并提出解决方案。然后，我们通过测量构造图的角分辨率，边缘长度和面部纵横比来比较这三种算法的性能。我们观察到Mondal等人的修正算法。尤其是在角度分辨率方面，其性能要优于其他算法。但是，新算法在边缘长度和最小的面部长宽比方面表现更好。
展开▼
