×

Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains. (English) Zbl 0835.05065

Given a finite simple polygon, its visibility graph is obtained by connecting those pairs of vertices whose edge is not obstructed by exterior points of other vertices. Characterizing visibility graphs is not yet settled as to minimal complexity. Convex fans may play an important role in settling the question. In this interesting paper the subject is orthogonal complex fans (staircase polygons) whose visibility graphs are proven to be persistent graphs, where persistency is a property of the adjacency matrix of the graph under a suitable ordering of the vertices. Since simple polygons can be associated with maximal chains in the weak Bruhat order of the symmetric group \(S_n\), with \(n\) the number of vertices of the polygon, a polynomial-time algorithm which recovers representative maximal chains from the graph (in a certain class) would effectively answer the characterization question for visibility graphs if they were in that class. The polynomial-time algorithm constructed as a clever concatenation of two subalgorithms of independent interest recovers maximal chains for the class of persistent graphs in polynomial time \(O (n^5)\). The step from persistent graph to visibility graph of a staircase polygon as a logical next step has not been addressed in this paper, but elsewhere.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05E10 Combinatorial aspects of representation theory
06A07 Combinatorics of partially ordered sets
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] J. Abello, A study of an independence system arising in group choice via the weak Bruhat order, Ph.D. Dissertation, University of California, San Diego, CA, 1985.
[2] J. Abello, The weak Bruhat order ofSσ, consistent sets, and Catalan numbers,SIAM Journal of Discrete Mathematics,4 (1991), 1-16. · Zbl 0725.90005 · doi:10.1137/0404001
[3] J. Abello and O. Egecioglu, Visibility graphs of staircase polygons with uniform step length,International Journal of Discrete and Computational Geometry,3(1) (1993), 27-37. · Zbl 0771.68098 · doi:10.1142/S0218195993000038
[4] J. Abello, O. Egecioglu, and K. Kumar, Visibility graphs of staircase polygons and the weak Bruhat order, II: From maximal chains to polygons, Preprint. · Zbl 0835.05065
[5] J. Abello, O. Egecioglu, and K. Kumar, A combinatorial view of visibility graphs of simple polygons,Proceedings of the Fifth International Conference on Computing and Information, Ontario, 1993, pp. 87-92.
[6] J Abello, L. Hua, and S. Pisupati, On visibility graphs of simple polygons,Congressus Numerantium90 (1992), 119-128. · Zbl 0786.05077
[7] J. Abello and K. Kumar, Visibility graphs and oriented matroids,Proceedings of the Workshop on Graph Drawing, Princeton, NJ, October 1994. Lecture Notes in Computer Science, Vol. 894, Springer-Verlag, Berlin, 1995, pp 147-158.
[8] D. Avis and G. T. Toussaint, An efficient algorithm for decomposing a polygon into star shaped polygons,Pattern Recognition13 (1981), 295-298. · doi:10.1016/0031-3203(81)90002-9
[9] C. Coullard and A. Lubiw, Distance visibility graphs,Proceedings of the Seventh ACM Symposium on Computational Geometry, 1991, pp. 290-302. · Zbl 0783.68091
[10] H. S. M. Coxeter and W. O. J. Moser,Generators and Relations for Discrete Groups, 2nd edition Springer-Verlag, New York, 1965. · Zbl 0133.28002
[11] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[12] P. Edelman and C. Greene, Combinatorial correspondences for Young tableaux, balanced tableaux, and maximal chains in the weak Bruhat order,Contemporary Mathematics34 (1984), 220-255. · Zbl 0562.05008
[13] H. A. El-Gindy, Hierarchical decompositions of polygons with applications, Ph.D. Dissertation, School of Computer Science, McGill University, 1985.
[14] H. Everett, Visibility graph recognition., Ph.D. Dissertation, Department of Computer Science, University of Toronto, 1990.
[15] H. Everett and D. G. Corneil, Recognizing visibility graphs of spiral polygons,Journal of Algorithms11 (1990), 1-26. · Zbl 0694.68030 · doi:10.1016/0196-6774(90)90026-B
[16] S. K. Ghosh,On Recognizing and Characterizing Visibility Graphs of Staircase Polygons, Lecture Notes in Computer Science, Vol. 318, Springer-Verlag, Berlin, 1988, pp. 132-139.
[17] J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane,Journal of Combinatorial Theory, Series A29 (1980), 212-233. · Zbl 0465.51007 · doi:10.1016/0097-3165(80)90010-2
[18] J. E. Goodman and R. Pollack, Semispaces of Configurations, cell complexes of arrangements,Journal of Combinatorial Theory, Series A37 (1984), 84-102. · Zbl 0551.05002 · doi:10.1016/0097-3165(84)90050-5
[19] J. E. Goodman and R. Pollack, Upper bounds for configurations and polytopes inRd,Discrete and Computational Geometry1 (1986), 219-227. · Zbl 0609.52004 · doi:10.1007/BF02187696
[20] K. Kumar, Combinatorial aspects of point visibility, Ph.D. Dissertation, Department of Computer Science, Texas A & M University, 1993.
[21] J. O’Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, 1987. · Zbl 0653.52001
[22] F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[23] R. Tamassia and I. Tollis, A unified approach to visibility representations of planar graphs,Discrete and Computational Geometry1 (1986), 312-337. · Zbl 0607.05026 · doi:10.1007/BF02187705
[24] S. Wismath, Characterizing bar line-of-sight graphs,Proceedings of the 1st ACM Symposium on Computational Geometry, 1985, pp. 113-145.
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.