On the angular resolution of planar graphs
On the angular resolution of planar graphs
复制标题
关于平面图的角分辨率
DOI：
10.1145/129712.129764
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
A. Papakostas
中科院分区：
文献类型：
--
作者：
S. Malitz;A. Papakostas
I. Fa 'ry的一个著名定理指出，任何平面图都可以在平面上绘制，使得所有的边都是直线段，并且没有两条边相交。该图的<斜体>角分辨率</斜体>是任意一对入射边所对应的最小角度。平面图形的<italic>角分辨率</italic>是该图形所有平面直线图的最大角分辨率。在forman et al.最近的一篇论文中，<斜体>在平面上绘制高分辨率的图形</斜体>,Symp。在发现。比较科学（1990），提出了以下问题：是否存在一个常数<斜体>r(d)</斜体> > 0，使得每一个最大度数<斜体>d</斜体>的平面图的角分辨率都≥<斜体>r(d)</斜体>？我们可以肯定地回答这个问题，证明任何最大度<斜体>d</斜体>的平面图，其角分辨率至少为α<上标><斜体>d</斜体></上标>弧度，其中0 < α< 1为常数。为了评估这个下界是否存在紧性（直到常数α），我们分析了一个非常自然的线性程序，该程序将任意固定平面图<斜体>G</斜体>从&OHgr；（1/<斜体>d</斜体>），虽然目前我们无法解决一般平面图的这个问题。对于内部三角化且最大度<斜体>d</斜体>的外平面图类，虽然目前我们还无法解决一般平面图的这个问题。对于一类内三角形化且最大度<斜体>d</斜体>的外平面图，我们不仅证明了&OHgr；（1/<italic>d</italic>）是角分辨率的下界，但实际上，在平面直线图中，所有内部面都是<斜体>类似的</斜体>等腰三角形，可以达到这个角分辨率。其他结果包含在论文全文中。
A famous theorem of I. Fa`ry states that any planar graph can be drawn in the plane so that all edges are straight-line segments and no two edges cross. The <italic>angular resolution</italic> of such a drawing is the minimum angle subtended by any pair of incident edges. The <italic>angular resolution</italic> of a planar graph is the maximum angular resolution over all such planar straight-line drawings of the graph. In a recent paper by Formann et al., <italic>Drawing graphs in the plane with high resolution</italic>, Symp. on Found. of Comp. Sci. (1990), the following question is posed: does there exist a constant <italic>r(d)</italic> > 0 such that every planar graph of maximum degree <italic>d</italic> has angular resolution ≥ <italic>r(d)</italic>? We answer this question in the affirmative by showing that any planar graph of maximum degree <italic>d</italic> has angular resolution at least α<supscrpt><italic>d</italic></supscrpt> radians where 0 < α < 1 is a constant. In an effort to assess whether or not this lower bound is existentially tight (up to constant α), we analyze a very natural linear program that bounds the angular resolution of any fixed planar graph <italic>G</italic> from &OHgr;(1/<italic>d</italic>), although currently, we are unable to settle this issue for general planar graphs. For the class of outerplanar graphs with triangulated interior and maximum degree <italic>d</italic>, although currently, we are unable to settle this issue for general planar graphs. For the class of outerplanar graphs with triangulated interior and maximum degree <italic>d</italic>, we show not only that &OHgr;(1/<italic>d</italic>) is lower bound on angular resolution, but in fact, this angular resolution can be achieved in a planar straight-line drawing where all interior faces are <italic>similar</italic> isosceles triangles. Additional results are contained in the full paper.