Logo

Login | Create Account

Thickness of Bar 1-Visibility Graphs

Massow, Mareike and Felsner, Stefan (2007) Thickness of Bar 1-Visibility Graphs. [Conference Paper]

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
Classifications:P Styles > P.900 Visibility
Z Theory > Z.999 Others
ID Code:787
Deposited By:GDEA, Administration
Deposited On:04 May 2007
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springer.com/dal/home/computer/lncs?SGWID=1-164-22-173721109-0

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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.