Characterization and a 2D Visualization of B₀-VPG Cocomparability Graphs

DOI10.1007/978-3-030-68766-3_16MaRDI QIDQ6346550arXivFDO

Authors Sreejith K. Pallathumadam, Deepak Rajendraprasad

Publication date 5 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-68766-3_16

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

cs.DMmath.CO

Abstract: 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.

This page was built for publication: Characterization and a 2D Visualization of B$_0$-VPG Cocomparability Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346550)