Integral Unit Bar-Visibility Graphs
Published in CCCG, 2018
Recommended citation: Therese Biedl, Ahmad Biniaz, Veronika Irvine, Philipp Kindermann, Anurag Murty Naredla, and Alexi Turcotte. 2018. Integral Unit Bar-Visibility Graphs. Canadian Conference on Computational Geometry, CCCG, 7 pages. http://reallytg.github.io/files/papers/cccg18-unit-bar.pdf
In this paper, we take another look at unit bar-visibility representations, that is bar-visibility representations where every bar has the same width. Motivated by some applications in textile construction, we restrict the graphs further to integral unit bar-visibility representations (IUBVR), that is a bar-visibility representation where the bar of every vertex is a horizontal line segment [i−1, i], for some positive integer i, at some real-value y position.
We study which graph classes do/don’t have an IUBVR, both in the weak model and in the strong model. In the weak model, we show that it is NP-hard to test whether a graph has an IUBVR. We also present recursive algorithms to create IUBVRs for some graph classes, such as 2-connected outerplanar graphs with maximum degree 4. In the strong model, we provide a polynomial-time algorithm to test for the existence of a strong IUBVR. In the event of a positive answer, the algorithm also generates such a strong IUBVR.