The Partial Visibility Representation Extension Problem
Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta · Lecture notes in computer science · 2016
For a graph G, a function $$\psi $$ is called a bar visibility representation of G when for each vertex $$v \in V(G)$$ , $$\psi (v)$$ is a horizontal line segment (bar) and $$uv \in E(G)$$ iff there is an unobstructed, vertical, $$\varepsilon $$ -wide line of sight between $$\psi (u)$$ and $$\psi (v)$$ . Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation $$\psi $$ of G, additionally, for each directed edge (u, v) of G, puts the bar $$\psi (u)$$ strictly below the bar $$\psi (v)$$ . We study a generalization of the recognition problem where a function $$\psi '$$ defined on a subset $$V'$$ of V(G) is given and the question is whether there is a bar visibility representation $$\psi $$ of G with $$\psi |V' = \psi '$$ . We show that for undirected graphs this problem together with closely related problems are $$\mathsf {NP}$$ -complete, but for certain cases involving directed graphs it is solvable in polynomial time.