# The Partial Visibility Representation Extension Problem

arXiv: https://arxiv.org/abs/1512.00174 · HTML: https://mlsanity.com/paper/1512.00174/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2015.

## Built on by (most cited first, 1 of 1)

- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)

## Abstract (arXiv)

For a graph G, a function psi is called a bar visibility representation of G when for each vertex v ∈ V(G), psi(v) is a horizontal line segment (bar) and uv ∈ 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, puts the bar psi(u) strictly below the bar psi(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' of V(G) is given and the question is whether there is a bar visibility representation psi of G with psi(v) = psi'(v) for every v ∈ V'. We show that for undirected graphs this problem together with closely related problems are NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time.