论文标题
b $ _0 $ -VPG表示免费外平面图的表示
B$_0$-VPG Representation of AT-free Outerplanar Graphs
论文作者
论文摘要
$ k $弯曲路径是由最多由$ k+1 $ axis-parallel线段制成的平面中的非自动交流层。 B $ _K $ -VPG是一类图形，可以表示为同一平面中$ k $的相交图。在本文中，我们表明所有无拟合的外平面图均为b $ _0 $ -VPG，即平面中水平和垂直线段的相交图。我们的证明是建设性的，并给出了多项式时间B $ _0 $ -VPG绘图算法的算法。 经过一系列的改进，Gonçalves，Isenmann和Pennarun [Soda 2018]表明，所有平面图均为b $ _1 $ -VPG。由于存在非B $ _0 $ -VPG的平面图，因此在平面图中表征B $ _0 $ -VPG图的表征变得很有趣。 Chaplick等人[WG 2012]表明，在B $ _ {k+1} $ -VPG中识别B $ _K $ -VPG图是NP的np完整。因此，识别b $ _1 $ _1 $ -VPG中的b $ _0 $ -VPG图是NP完整的，但是当限于平面图时，问题是开放的。有外平面图和无原始平面图不是b $ _0 $ -VPG。这激发了我们对无拟合外平面图的兴趣。
A $k$-bend path is a non-self-intersecting polyline in the plane made of at most $k+1$ axis-parallel line segments. B$_k$-VPG is the class of graphs which can be represented as intersection graphs of $k$-bend paths in the same plane. In this paper, we show that all AT-free outerplanar graphs are B$_0$-VPG, i.e., intersection graphs of horizontal and vertical line segments in the plane. Our proofs are constructive and give a polynomial time B$_0$-VPG drawing algorithm for the class. Following a long line of improvements, Gonçalves, Isenmann, and Pennarun [SODA 2018] showed that all planar graphs are B$_1$-VPG. Since there are planar graphs which are not B$_0$-VPG, characterizing B$_0$-VPG graphs among planar graphs becomes interesting. Chaplick et al.\ [WG 2012] had shown that it is NP-complete to recognize B$_k$-VPG graphs within B$_{k+1}$-VPG. Hence recognizing B$_0$-VPG graphs within B$_1$-VPG is NP-complete in general, but the question is open when restricted to planar graphs. There are outerplanar graphs and AT-free planar graphs which are not B$_0$-VPG. This piqued our interest in AT-free outerplanar graphs.
