math.CO cs.DM
Characterization and a 2D Visualization of B 0 VPG Cocomparability Graphs. 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.