Header menu link for other important links
X
Characterization and a 2D Visualization of B0 -VPG Cocomparability Graphs
S.K. Pallathumadam,
Published in Springer Science and Business Media Deutschland GmbH
2020
Volume: 12590 LNCS
   
Pages: 191 - 204
Abstract
B0 -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 B0 -VPG permutation graphs. We respond here by characterizing B0 -VPG cocomparability graphs. This characterization also leads to a polynomial time recognition and B0 -VPG drawing algorithm for the class. Our B0 -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. © 2020, Springer Nature Switzerland AG.