creators_name: Massow, Mareike
creators_name: Felsner, Stefan
editors_name: Kaufmann, Michael
editors_name: Wagner, Dorothea
editors_id: Kaufmann, Michael
editors_id: Wagner, Dorothea
type: confpaper
datestamp: 2007-05-04
lastmod: 2008-09-18 11:09:05
metadata_visibility: show
title: Thickness of Bar 1-Visibility Graphs
ispublished: pub
subjects: P.900
subjects: Z.999
full_text_status: none
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.
    
date: 2007
date_type: published
series: Lecture notes in Computer Science
publisher: Springer
pagerange: 330-342
refereed: FALSE
referencetext: P. Bose, A. M. Dean, J. P. Hutchinson, and T. C. Shermer, On rectangle visibility graphs, in Proceedings of Graph Drawing '96, vol. 1353 of Lecture Notes Comput. Sci., Springer, 1997, pp. 25-44.
F. J. Cobos, J. C. Dana, F. Hurtado, A. Marquez, and F. Mateos, On a visibility representation of graphs, in Proceedings of Graph Drawing '95, vol. 1027 of Lecture Notes Comput. Sci., Springer, 1995, pp. 152-161.
A. M. Dean, W. Evans, E. Gethner, J. D. Laison, M. A. Safari, and W. T. Trotter, Bar k-visibility graphs. Manuscript, 2005.
A. M. Dean, W. Evans, E. Gethner, J. D. Laison, M. A. Safari, and W. T. Trotter, Bar k-visibility graphs: Bounds on the number of edges, chromatic number, and thickness, in Proceedings of Graph Drawing '05, vol. 3843 of Lecture Notes Comput. Sci., Springer, 2006, pp. 73-82.
A. M. Dean, E. Gethner, and J. P. Hutchinson, Unit bar-visibility layouts of triangulated polygons., in Proceedings of Graph Drawing '04, vol. 3383 of Lecture Notes Comput. Sci., Springer, 2005, pp. 111-121.
M. B. Dillencourt, D. Eppstein, and D. S. Hirschberg, Geometric thickness of complete graphs, J. Graph Algorithms  Applications, 4 (2000), pp. 5-17. Special issue for Graph Drawing '98.
D. Eppstein, Separating thickness from geometric thickness, in Proceedings of Graph Drawing '02, vol. 2528 of Lecture Notes Comput. Sci., Springer, 2002, pp. 150-161.
S. G. Hartke, J. Vandenbussche, and P. Wenger, Further results on bar k-visibility graphs. Manuscript, November 2005.
J. Hutchinson, Arc- and circle-visibility graphs, Australas. Journal of Combin., 25 (2002), pp. 241-262.
J. P. Hutchinson, T. Shermer, and A. Vince, On representations of some thickness-two graphs, Comput. Geom. Theory Appl., 13 (1999), pp. 161-171.
A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Camb. Phil. Soc., 9 (1983), pp. 9-23.
P. Mutzel, T. Odenthal, and M. Scharbrodt, The thickness of graphs: A survey, Graphs and Combinatorics, 14 (1998), pp. 59-73.
R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Discrete Computational Geometry, 1 (1986), pp. 321-341.
S. K. Wismath, Characterizing bar line-of-sight graphs, in Proceedings of SCG  '85, ACM Press, 1985, pp. 147-152.
citation: Massow, Mareike and Felsner, Stefan (2007) Thickness of Bar 1-Visibility Graphs. [Conference Paper]