Header menu link for other important links
X
Characterization of B0-VPG Cocomparability Graphs and a 2D Visualization of their Posets
S.K. Pallathumadam,
Published in Springer Science and Business Media B.V.
2022
Volume: 39
   
Issue: 3
Pages: 1 - 20
Abstract
B0-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 B0-VPG permutation graphs. We respond here by characterizing B0-VPG cocomparability graphs. This helps us show that a simple necessary condition in fact characterizes B0-VPG permutation graphs. The characterization also leads to a polynomial time recognition algorithm and its proof gives us a B0-VPG drawing algorithm for the class of B0-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 ≺2q 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 ℝ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. © 2021, The Author(s), under exclusive licence to Springer Nature B.V.
About the journal
JournalData powered by TypesetOrder
PublisherData powered by TypesetSpringer Science and Business Media B.V.
ISSN01678094
Open AccessNo