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, Karlsruhe, Germany , 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
ID Code:787

Repository Staff Only: item control page

References

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.