Thickness of Bar 1-Visibility Graphs

Massow, Mareike and Felsner, Stefan (2007) Thickness of Bar 1-Visibility Graphs. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 330-342(Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_32).

Full text not available from this repository.

Abstract

Bar k-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can traverse up to k bars. These graphs were introduced by Dean et al. [3] who conjectured that bar 1-visibility graphs have thickness at most 2. We construct a bar 1-visibility graph having thickness 3, disproving their conjecture. For a special case of bar 1-visibility graphs we present an algorithm partitioning the edges into two plane graphs, showing that for this class the thickness is indeed bounded by 2.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_32
Classifications: P Styles > P.900 Visibility
Z Theory > Z.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/787

Actions (login required)

View Item View Item