LAUSR

For a graph G, a function $$\psi $$ψ is called a bar visibility representation of G when for each vertex $$v \in V(G)$$v∈V(G), $$\psi (v)$$ψ(v) is a horizontal line segment (bar) and $$uv \in E(G)$$uv∈E(G) if and only if there is an unobstructed, vertical, $$\varepsilon $$ε-wide line of sight between $$\psi (u)$$ψ(u) and $$\psi (v)$$ψ(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 of G, additionally, puts the bar $$\psi (u)$$ψ(u) strictly below the bar $$\psi (v)$$ψ(v) for each directed edge (u, v) of G. We study a generalization of the recognition problem where a function $$\psi '$$ψ′ defined on a subset $$V'$$V′ of V(G) is given and the question is whether there is a bar visibility representation $$\psi $$ψ of G with $$\psi (v) = \psi '(v)$$ψ(v)=ψ′(v) for every $$v \in V'$$v∈V′. We show that for undirected graphs this problem, and other closely related problems, is $$\mathsf {NP}$$NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time.