Non-stretchable pseudo-visibility graphs |
| |
Authors: | Ileana Streinu |
| |
Institution: | Computer Science Department, Smith College, Northampton, MA 01063, USA |
| |
Abstract: | We exhibit a family of graphs which can be realized as pseudo-visibility graphs of pseudo-polygons, but not of straight-line polygons. The example is based on the characterization of vertex-edge pseudo-visibility graphs of O'Rourke and Streinu Proc. ACM Symp. Comput. Geometry, Nice, France, 1997, pp. 119–128] and extends a recent result of the author Proc. ACM Symp. Comput. Geometry, Miami Beach, 1999, pp. 274–280] on non-stretchable vertex-edge visibility graphs. We construct a pseudo-visibility graph for which there exists a unique compatible vertex-edge visibility graph, which is then shown to be non-stretchable. The construction is then extended to an infinite family. |
| |
Keywords: | Pseudoline arrangement Visibility graph Pseudo-visibility graph Stretchability Oriented matroid |
本文献已被 ScienceDirect 等数据库收录! |
|