Rectangle Visibility Graphs: Characterization, Construction, and Compaction

1. H. Alt, M. Godau, and S. Whitesides. Universal 3-dimensional visibility representations for graphs. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD’ 95), vol. 1027 of Lecture Notes Comput. Sci., pp. 8–19. Springer-Verlag, 1996.

   Google Scholar 

2. G. Brightwell and P. Winkler. Counting linear extensions is #P-complete. Proc. STOC 23, pp. 175–181, 1991.

   Google Scholar 

3. K.S. Booth and G.S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput.System Sci. 13, pp. 335–379, 1976.

   MATH  MathSciNet  Google Scholar 

4. P. Bose, A. Dean, J. Hutchinson, and T. Shermer. On rectangle visibility graphs I: k-trees and caterpillar forests. Tech. report, DIMACS and Simon Fraser U., May 1996.

   Google Scholar 

5. P. Bose, H. Everett, S. P. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides. On a visibility representation for graphs in three dimensions. In D. Avis and P. Bose, eds., Snapshots in Computational and Discrete Geometry, Vol. III, pp. 2–25. McGill U., July 1994. McGill tech. report SOCS-94.50.

   Google Scholar 

6. P. Bose, H. Everett, Michael E. Houle, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, G. Rote, T. Shermer, S. Whitesides, and Christian Zelle. A visibility representation for graphs in three dimensions. J. Graph Algorithms and Applications, vol. 2, no. 3, pp. 1–16, 1998.

   MathSciNet  Google Scholar 

7. P. Bose, A. Josefczyk, J. Miller, and J. O’Rourke. K ₄₂ is a box visibility graph. In Snapshots of Computational and Discrete Geometry, vol. 3, pp. 88–91. School Comput. Sci., McGill U., Montreal, July 1994. Tech. report SOCS-94.50.

   Google Scholar 

8. A. M. Dean and J. P. Hutchinson. Rectangle-visibility representations of bipartite graphs. In R. Tamassia and I. G. Tollis, eds., Graph Drawing (Proc. GD’ 94), vol. 894 of Lecture Notes Comput. Sci., pp. 159–166. Springer-Verlag, 1995.

   Google Scholar 

9. G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing: Algorithms for the visualization of graphs. Prentice Hall, Upper Saddle River NJ, 1999.

   Google Scholar 

10. Jeong-In Doh and Kyung-Yong Chwa. Visibility problems for orthogonal objects in two or three dimensions. Visual Comput., vol. 4, no. 2, pp. 84–97, July 1988.

    Article  Google Scholar 

11. S. P. Fekete, M. E. Houle, and S. Whitesides. New results on a visibility representation of graphs in 3-d. In F. Brandenburg, ed., Graph Drawing’ 95, vol. 1027 of Lecture Notes Comput. Sci., pp. 234–241. Springer-Verlag, 1996.

    Google Scholar 

12. H. de Fraysseix and P. Rosenstiehl. L’algorithme gauche-droite pour le plongement des graphes dans le plan.

    Google Scholar 

13. Xin He and Ming-Yang Kao. Regular edge labelings and drawings of planar graphs. In Proc. Graph Drawing conf., pp. 96–103, 1994.

    Google Scholar 

14. J. Hopcroft and R. Tarjan. Efficient planarity testing. J. Assoc. Comput. Machin. 21, pp. 549–568, 1974.

    MATH  MathSciNet  Google Scholar 

15. J. P. Hutchinson, T. Shermer, and A. Vince. On representations of some thicknesstwo graphs. In F. Brandenburg, ed., Graph Drawing’ 95, vol. 1027 of Lecture Notes Comput. Sci., pp. 324–332. Springer-Verlag, 1995.

    Google Scholar 

16. A. Josefczyk, J. Miller, and J. O’Rourke. Arkin’s conjecture for rectangle and box visibility graphs. Tech. Report 036, Dept. Comput. Sci., Smith College, July 1994.

    Google Scholar 

17. D. G. Kirkpatrick and S. K. Wismath. Weighted visibility graphs of bars and related flow problems. In Proc. 1st Workshop Algorithms Data Struct., vol. 382 of Lecture Notes Comput. Sci., pp. 325–334. Springer-Verlag, 1989.

    Google Scholar 

18. A. Lempel, S. Even and I. Cederbaum. An algorithm for planarity testing of graphs. In (P. Rosenstiehl, ed., Theory of Graphs (Int. Symposium, Rome, 1966), pp. 215–232, Gordon and Breach, New York, 1967.

    Google Scholar 

19. E. Lodi and L. Pagli. A VLSI solution to the vertical segment visibility problem. IEEE Trans. Comput., vol. C-35, no. 10, pp. 923–928, 1986.

    Article  Google Scholar 

20. F. Luccio, S. Mazzone, and C. Wong. A note on visibility graphs. Discrete Math., vol. 64, pp. 209–219, 1987.

    Article  MATH  MathSciNet  Google Scholar 

21. M. H. Overmars and D. Wood. On rectangular visibility. J. Algorithms, vol. 9, pp. 372–390, 1988.

    Article  MATH  MathSciNet  Google Scholar 

22. K. Romanik. Directed rectangle-visibility graphs have unbounded dimension. In Proc. 7th Canad. Conf. Comput. Geom., pp. 163–167, 1995.

    Google Scholar 

23. Pierre Rosenstiehl and Robert Tarjan. Rectiliniar planar layouts and bipolar orientations of planar graphs. Discrete Comput Geom., vol. 1, pp. 343–353, 1986.

    Article  MATH  MathSciNet  Google Scholar 

24. T. Shermer. On rectangle visibility graphs III: External visibility and complexity. Tech. report, DIMACS and Simon Fraser U., April 1996.

    Google Scholar 

25. T. C. Shermer. On rectangle visibility graphs, III: External visibility and complexity. In Proc. 8th Canad. Conf. Comput. Geom., pp. 234–239, 1996.

    Google Scholar 

26. R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom., vol. 1, no. 4, pp. 321–341, 1986.

    Article  MATH  MathSciNet  Google Scholar 

27. S. K. Wismath. Characterizing bar line-of-sight graphs. In Proc. 1st Annu. ACM Sympos. Comput. Geom., pp. 147–152, 1985.

    Google Scholar 

28. S. K. Wismath. Bar-Representable Visibility Graphs and Related Flow Problems. Ph.D. thesis, Dept. Comput. Sci., U. British Columbia, 1989.

    Google Scholar 

Download references