Witness bar visibility

Description

Bar visibility graphs were introduced in the seventies as a model for some VLSI layout problems. They have been also studied since then by the graph drawing community, and recently several generalizations and restricted versions have been proposed. We introduce a generalization, witness-bar visibility graphs, and we prove that this class encompasses all the bar-visibility variations considered so far. In addition, we show that many classes of graphs are contained in this family, including in particular all planar graphs, interval graphs, circular arc graphs and permutation graphs.

Abstract

Ministerio de Economía y Competitividad

Abstract

Generalitat de Catalunya

Abstract

European Science Foundation

Abstract

Ministerio de Ciencia e Innovación

Additional details