论文标题
B $ _0 $ -VPG可可比较图的表征和2D可视化图
Characterization and a 2D Visualization of B$_0$-VPG Cocomparability Graphs
论文作者
论文摘要
B $ _0 $ -VPG图是飞机上垂直线和水平线段的交点图。 Cohen，Golumbic，Trotter和Wang [Order，2016年]提出了表征B $ _0 $ -VPG置换图的问题。我们在此处通过表征B $ _0 $ -VPG可可比程图来做出回应。这种表征还导致多项式时间识别和B $ _0 $ -VPG绘图算法的算法。我们的B $ _0 $ -VPG图形算法首先修复了许多POSETS $ P $中的任何一种，其可可零件图是输入图$ g $。我们获得的图形不仅可以看到$ g $，因为一个人可以将可比对与无与伦比的对区分开，而且还可以从此可视化中识别出$ p $的可比较对中的哪个对。
B$_0$-VPG graphs are intersection graphs of vertical and horizontal line segments on a plane. Cohen, Golumbic, Trotter, and Wang [Order, 2016] pose the question of characterizing B$_0$-VPG permutation graphs. We respond here by characterizing B$_0$-VPG cocomparability graphs. This characterization also leads to a polynomial time recognition and B$_0$-VPG drawing algorithm for the class. Our B$_0$-VPG drawing algorithm starts by fixing any one of the many posets $P$ whose cocomparability graph is the input graph $G$. The drawing we obtain not only visualizes $G$ in that one can distinguish comparable pairs from incomparable ones, but one can also identify which among a comparable pair is larger in $P$ from this visualization.
