论文标题
线性时间的外平面图的平面直线图
Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
论文作者
论文摘要
我们展示了如何在线性时间测试外平面图是否允许平面直线图，这两个图形是否具有嵌入图形必须尊重的规定平面以及不符合的平面。如果该图允许，我们的算法将返回平面直线图。
We show how to test in linear time whether an outerplanar graph admits a planar rectilinear drawing, both if the graph has a prescribed plane embedding that the drawing has to respect and if it does not. Our algorithm returns a planar rectilinear drawing if the graph admits one.
