2015 | OriginalPaper | Buchkapitel
On Bar (1,j)-Visibility Graphs
(Extended Abstract)
Autoren: Franz J. Brandenburg, Niklas Heinsohn, Michael Kaufmann, Daniel Neuwirth
Verlag: Springer International Publishing
A graph is called a bar (1,
j
)-visibility graph if its vertices can be represented as horizontal vertex-segments (bars) and each edge as a vertical edge-segment connecting the bars of the end vertices such that each edge-segment intersects at most one other bar and each bar is intersected by at most
j
edge-segments. Bar (1,
j
)-visibility refines bar 1-visibility in which there is no bound on the number of intersections of bars.
We construct gadgets which show structural properties of bar (1,
j
)-visibility graphs, study bounds on the maximal number of edges and show that there is an infinite hierarchy of bar (1,
j
)-visibility graphs. Finally, we prove that it is
NP
-complete to test whether a graph is bar (1, ∞ )-visible.
