Logo

Login

Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract)

Dean, Alice M. and Hutchinson, Joan P. (1995) Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract). [Conference Paper]

Full text not available from this repository.

Abstract

The paper considers representations of bipartite graphs as rectangle-visibility graphs, i.e., graphs whose vertices are rectangles in the plane, with adjacency determined by horizontal and vertical visibility. It is shown that, for p \leq p, K_{p,q} has a representation with no rectangles having collinear sides if and only if p < 3 or p = 3 and q \leq 4. More generally, it is shown that K_{p,q} is a rectangle-visibility graph if and only if p \leq 4. Finally, it is shown that every bipartite rectangle-visibility graph on n \geq 4 vertices has at most 4n - 12 edges.

Item Type:Conference Paper
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
ID Code:144
Deposited By:Selbach, Anna
Deposited On:02 Dec 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

T. Andreae, Some results on visibility graphs, Disc. Appl. Math. 40 (1992), 5-18.

L.W. Beineke, F. Harary, and J. W. Moon, On the thickness of the complete bipartite graph, Proc. Cambridge Philo. Soc. 60 (1964), 1-5.

P. Bose, A. Josefczyk, J. Miller, and J. O'Rourke, K_{42} is a box visibility graph, Tech. Report #034, Smith College (1994).

M. R. Garey, D. S. Johnson, and H. C. So, An application of graph coloring to printed circuit testing, IEEE Trans. Circuits and Systems CAS-23 (1976), 591-599.

J. Hopcroft and R. Tarjan, Efficient planarity testing, J. Assoc. Comput. Mach. 21 (1974), 549-568.

J. P. Hutchinson, Coloring ordinary maps of empires, and maps of the Moon, Mathematics Magazine 66 (1993), 211-226.

J. P. Hutchinson, T. Shermer, and A. Vince, Representations of thickness two graphs, preprint.

D. G. Kirkpatrick and S. K. Wismath, Weighted visibility graphs of bars and related flow problems, Lecture Notes in Computer Science (Proc. 1st Workshop Algorithms Data Struct.), vol. 382, Springer-Verlag, 1989, pp. 325-334.

F. Luccio, S. Mazzone, and C. K. Wong, A note on visibility graphs, Disc. Math. 64 (1987), 209-219.

A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Camb. Phil. Soc. 93 (1983), 9-23.

J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, N.Y., 1987.

R. Tamassia and I.G. Tollis, A unified approach to visibility representations of planar graphs, Disc. and Comp. Geom. 1 (1986), 321-341.

S. K. Wismath, Characterizing bar line-of-sight graphs, Proc. 1st Symp. Comp. Geom., ACM (1985), 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.