Bo-VPG graphs are intersection graphs of axis-parallel line segments in the plane. Cohen et al. (Order 33(1), 39-49, 2016) pose the question of characterizing Bo-VPG permutation graphs. We respond here by characterizing Bo-VPG cocomparability graphs. This helps us show that a simple necessary condition in fact characterizes Bo-VPG permutation graphs. The characterization also leads to a polynomial time recognition algorithm and its proof gives us a Bo-VPG drawing algorithm for the class of Bo-VPG cocomparability graphs. Our drawing algorithm starts by fixing any one of the many posets P whose cocomparability graph is the input graph G. On the set of axis-parallel line segments in the plane, we define a binary relation "＜2" as p ＜2 q if and only if they are non-intersecting and the bottom-left endpoint of p precedes the top-right endpoint of q in the product order on R~2. The reflexive closure ≤2 of the relation ＜2 restricted to the line segments of our drawing turns out to be a partial order isomorphic to the poset P.
展开▼
