B$_0$-VPG graphs are intersection graphs of axis-parallel line segments in the plane. In this paper, we show that all AT-free outerplanar graphs are B$_0$-VPG. We first prove that every AT-free outerplanar graph is an induced subgraph of a biconnected outerpath (biconnected outerplanar graphs whose weak dual is a path) and then we design a B$_0$-VPG drawing procedure for biconnected outerpaths. Our proofs are constructive and give a polynomial time B$_0$-VPG drawing algorithm for the class. We also characterize all subgraphs of biconnected outerpaths and name this graph class "linear outerplanar". This class is a proper superclass of AT-free outerplanar graphs and a proper subclass of outerplanar graphs with pathwidth at most 2. It turns out that every graph in this class can be realized both as an induced subgraph and as a spanning subgraph of (different) biconnected outerpaths.
翻译:B$_ 0$- VPG 图形是平面轴- 平行线段的交叉图。 在本文中, 我们显示所有 AT 空外平面图都是 B$_ 0$- VPG 。 我们首先证明, 每个 AT 空外平面图都是 双连接外路( 双向双向相弱的外平面图是一个路径) 的诱导子图, 然后我们为双连接外路设计一个 B$_ 0$- VPG 绘图程序 。 我们的证明具有建设性, 并给出了该类的多元时间 B$_ 0$- VPG 绘图算法 。 我们还标明了所有双连接外路段的子图类“ 线外平面 ” 。 这个类是 适当的 AT 空外平面图的超级分类, 以及 最多 2 的路径宽度外平面图的合适子类 。 它证明, 本类中的每个图表都可以作为 引导子图和( 不同) 两端外部路段的子图 。