Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
The Partial Visibility Representation Extension Problem
verfasst von : Steven Chaplick, Grzegorz Guśpiel, Grzegorz Gutowski, Tomasz Krawczyk, Giuseppe Liotta
Erschienen in: Graph Drawing and Network Visualization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
For a graph G, a function \(\psi \) is called a bar visibility representation of G when for each vertex \(v \in V(G)\), \(\psi (v)\) is a horizontal line segment (bar) and \(uv \in 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, for each directed edge (u, v) of G, puts the bar \(\psi (u)\) strictly below the bar \(\psi (v)\). 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 '\). We show that for undirected graphs this problem together with closely related problems are \(\mathsf {NP}\)-complete, but for certain cases involving directed graphs it is solvable in polynomial time.