A unified approach to visibility representations of planar graphs. (English) Zbl 0607.05026
In the so-called visibility representations of planar graphs, vertices are represented by horizontal segments and edges by vertical segments that intersect the horizontal ones in case of their incidence. The authors consider three types of visibility representations and give complete characterization of the classes of graphs that admit them. In particular, a problem of Mel’nikov, posed at the 6th Hung. Colloquium on Combinatorics, Eger 1981, is settled. Further, linear time algorithms for testing the existence of and constructing visibility representations of planar graphs are presented. Among them, a variant of the Otten - van Wijk algorithm [Circuits and Systems, Proc. IEEE Int. Symp. 914-918 (1978); see also P. Rosenstiehl and R. E. Tarjan, Discrete Comput. Geom. 1, 343-353 (1986; see the review below)] is contained.
Reviewer: J.Širáň
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68R10 | Graph theory (including graph drawing) in computer science |
Citations:
Zbl 0607.05027References:
| [1] | J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, North Holland, Amsterdam, 1976. · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2 |
| [2] | P. Duchet, Y. Hamidoune, M. Las Vergnas, and H. Meyniel, Representing a planar graph by vertical lines joining different levels,Discrete Math.46 (1983), 319-321. · Zbl 0516.05023 · doi:10.1016/0012-365X(83)90128-0 |
| [3] | S. Even,Graph Algorithms, Computer Science Press, Rockville, MD, 1979. · Zbl 0441.68072 |
| [4] | S. Even and R. E. Tarjan, Computing an st-numbering,Theoret. Comput. Sci.2, (1976), 339-344. · Zbl 0341.68029 · doi:10.1016/0304-3975(76)90086-4 |
| [5] | D. Gouyou-Beauchamps, The Hamiltonian circuit problem is polynomial for 4-connected planar graphs,SIAM J. Comput.11 (1982), 529-539. · Zbl 0486.68061 · doi:10.1137/0211042 |
| [6] | J. Hopcroft and R. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach.21 (1974), 549-568. · Zbl 0307.68025 · doi:10.1145/321850.321852 |
| [7] | Lempel, A.; Even, S.; Cederbaum, I.; Rosenstiehl, P. (ed.), An algorithm for planarity testing of graphs, Proceedings of an International Symposium, Rome, July 1966, New York · Zbl 0197.50204 |
| [8] | F. Luccio, S. Mazzone, and C. K. Wong, A note on visibility graphs, Manuscript, Pisa, 1983. · Zbl 0638.05050 |
| [9] | L. A. Melnikov,Problem at the Sixth Hungarian Colloquium on Combinatorics, Eger, 1981. |
| [10] | R. H. J. M. Otten and J. G. van Wijk, Graph representations in interactive layout design,Proceedings IEEE International Symposium on Circuits and Systems, 914-918, New York, 1978. |
| [11] | P. Rosenstiehl and R. E. Tarjan, Rectilinear planar layouts of planar graphs and bipolar orientations,Discrete Comput. Geom., to appear. · Zbl 0607.05027 |
| [12] | Schlag, M.; Luccio, F.; Maestrini, P.; Lee, D. T.; Wong, C. K.; Preparata, F. P. (ed.), A visibility problem in VLSI layout compaction, 259-282 (1985), Greenwich, CT |
| [13] | J. A. Storer, On minimal node-cost planar embeddings,Networks14 (1984), 181-212. · Zbl 0546.94033 · doi:10.1002/net.3230140202 |
| [14] | R. Tamassia and I. G. Tollis, Plane Representations of Graphs and Visibility Between Parallel Segments, Technical Report ACT-57, Coordinated Science Laboratory, University of Ilinois at Urbana-Champaign, Urbana, IL, 1985. |
| [15] | R. Tamassia and I. G. Tollis, A Provably Good Linear Algorithm for Embedding Graphs in the Rectilinear Grid, Technical Report ACT-64, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 1985. |
| [16] | Thomassen, C.; Bondy, J. A. (ed.); Murty, U. S. R. (ed.), Plane representations of graphs, 43-69 (1984), New York · Zbl 0554.05021 |
| [17] | W. T. Tutte, A theorem on planar graphs,Trans. Amer. Math. Soc.82 (1956), 99-116. · Zbl 0070.18403 · doi:10.1090/S0002-9947-1956-0081471-8 |
| [18] | S. K. Wismath, Characterizing bar line-of-sight graphs,Proceedings of the ACM Symposium on Computational Geometry, 147-152, Baltimore, Maryland, 1985. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
