The Partial Visibility Representation Extension Problem

Chaplick, 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. 266-279(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_21).

Full text not available from this repository.

Abstract

For 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.999 Others
P Styles > P.900 Visibility
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1548

Actions (login required)

View Item View Item