The Partial Visibility Representation Extension Problem

Abstract

For a graph $G$, a function $\psi$ is called a \emph{bar visibility representation} of $G$ when for each vertex $v\in V(G)$, $\psi (v)$ is a horizontal line segment (\emph{bar}) and $uv\in E(G)$ iff there is an unobstructed, vertical, $\epsilon$-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 }^{\prime }$ defined on a subset $V^{\prime }$ of $V(G)$ is given and the question is whether there is a bar visibility representation $\psi$ of $G$ with $\psi (v)={\psi }^{\prime }(v)$ for every $v\in V^{\prime }$. 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.

Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)