The Partial Visibility Representation Extension ProblemChaplick, Steven and Guśpiel, Grzegorz and Gutowski, Grzegorz and Krawczyk, Tomasz and Liotta, Giuseppe (2016) The Partial Visibility Representation Extension Problem. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 266279(Official URL: http://dx.doi.org/10.1007/9783319501062_21). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_21
AbstractFor a graph G, a function ψ is called a bar visibility representation of G when for each vertex v∈V(G), ψ(v) is a horizontal line segment (bar) and uv∈E(G) iff there is an unobstructed, vertical, εwide line of sight between ψ(u) and ψ(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, for each directed edge (u, v) of G, puts the bar ψ(u) strictly below the bar ψ(v). We study a generalization of the recognition problem where a function ψ′ defined on a subset V′ of V(G) is given and the question is whether there is a bar visibility representation ψ of G with ψ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.
Actions (login required)
