Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract)

Dean, Alice M. and Hutchinson, Joan P. (1995) Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 159-166 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_367).

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
Additional Information:10.1007/3-540-58950-3_367
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
ID Code:144

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.