论文标题
$ 3 $连接的平面图的严格键盘图
Strictly-Convex Drawings of $3$-Connected Planar Graphs
论文作者
论文摘要
$ 3 $连接的平面图的严格凸线直线图中的小区域形成了图形图中的经典研究主题。当前，如Bárány所示，最著名的图纸的最著名区域是$ O（n^2）\ times o（n^2）$（n^2）$，而死记硬背则是基于扰动（非刻板性）凸图的复杂技术。不幸的是，该区域中的隐藏常数为$ 10^4 $订单。 我们提出了一种新的易于实现的技术，该技术在整数$ 2（N-1）\ times（5n^3-4n^2）$上产生严格的键入直线平面图。
Strictly-convex straight-line drawings of $3$-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings is $O(n^2) \times O(n^2)$, as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non-strictly) convex drawings. Unfortunately, the hidden constants in such area bound are in the $10^4$ order. We present a new and easy-to-implement technique that yields strictly-convex straight-line planar drawings of $3$-connected planar graphs on an integer grid of size $2(n-1) \times (5n^3-4n^2)$.
