Planar minimally rigid graphs and pseudo-triangulations

ABSTRACT

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

REFERENCES

• 1: O. Aichholzer, F. Aurenhammer, H. Krasser and B. Speckmann. Convexity minimizes pseudo-triangulations, Proc. 14th Canad. Conf. Comp. Geom., pp. 158--161, 2002.
• 2: O. Aichholzer, B. Speckmann, G. Rote and I. Streinu. The zigzag path of a pseudo-triangulation, manuscript, 2003.
• 3: P. Agarwal, J. Basch, L. J. Guibas, J. Herschberger and L. Zhang. Deformable free space tilings for kinetic collision detection, in Algorithmic and Computational Robotics: New Directions, Proc. 5th Workshop Algor. Found. Robotics (WAFR), 2001, pp. 83--96.
• 4: Alex R. Berg , Tibor Jordán, A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid, Journal of Combinatorial Theory Series B, v.88 n.1, p.77-97, May 2003 [doi>10.1016/S0095-8956(02)00037-0]
• 5: S. Bespamyatnikh. Enumerating pseudo-triangulations in the plane, in Proc. 14th Canad. Conf. Comp. Geom., 2002, pp. 162--166.
• 6: H. Bronnimann, L. Kettner, M. Pocchiola and J. Snoeyink. Counting and enumerating pseudo-triangulations with the greedy flip algorithm, manuscript, 2001.
• 7: Marek Chrobak , Michael T. Goodrich , Roberto Tamassia, Convex drawings of graphs in two and three dimensions (preliminary version), Proceedings of the twelfth annual symposium on Computational geometry, p.319-328, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237401]
• 8: E. Colin de Verdière, M. Pocchiola and G. Vegter. Tutte's barycenter method applied to isotopies. In Proc. 13th Canad. Conf. Comput. Geom., August 2001. pp. 57--60. Extended version in ECG Report ECG-TR-124300-01, http://www-sop.inria.fr/prisme/ECG/Results/Reports.html
• 9: R. Connelly , E. D. Demaine , G. Rote, Straightening polygonal arcs and convexifying polygonal cycles, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.432, November 12-14, 2000
• 10: G. Di Battista, P. Eades, R. Tamassia and I. Tollis. Graph Drawing, Prentice Hall, 1999.
• 11: T. Eren, W. Whiteley, A. Stephen Morse and P. Belhummeur. Sensor and Network Topologies of Formations with Distance-Direction Angle Constraints, submitted, March 2003.
• 12: I. Fary. On straight lines representation of planar graphs, Acta Sci. Math. Szeged 11 (1948), 229--233.
• 13: S. Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18 (2001), 19--37.
• 14: Michael S. Floater , Craig Gotsman, How to morph tilings injectively, Journal of Computational and Applied Mathematics, v.101 n.1-2, p.117-129, Jan. 15 1999 [doi>10.1016/S0377-0427(98)00202-7]
• 15: H. de Fraysseix, J. Pach and R. Pollack. How to draw a planar graph on a grid, Combinatorica 10 (1990), 41--51.
• 16: J. Graver, B. Servatius and H. Servatius. Combinatorial Rigidity, Graduate Studies in Mathematics, vol. 2, Amer. Math. Soc., 1993.
• 17: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 18: L. Henneberg. Die graphische Statik der starren Systeme, Leipzig 1911, Johnson Reprint 1968.
• 19: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 20: H. Imai. On combinatorial structures of line drawings of polyhedra, Discrete Applied Mathematics, 10 (1985), 79--92.
• 21: D. Jacobs, A. J. Rader, L. Kuhn, and M. Thorpe. Protein flexibility predictions using graph theory, Proteins 44 (2001), 150--165.
• 22: Lutz Kettner , David Kirkpatrick , Andrea Mantler , Jack Snoeyink , Bettina Speckmann , Fumihiko Takeuchi, Tight degree bounds for pseudo-triangulations of points, Computational Geometry: Theory and Applications, v.25 n.1-2, p.3-12, May 2003 [doi>10.1016/S0925-7721(02)00126-8]
• 23: G. Laman. On graphs and rigidity of plane skeletal structures, J. Engineering Math. 4 (1970), 331--340.
• 24: R. J. Lipton, D. J. Rose and R. E. Tarjan. Generalized nested dissection, SIAM J. Numer. Anal. 16 (1979), 346--358.
• 25: R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput. 9, 1980, 615--627
• 26: N. Mnëv. On manifolds of combinatorial types of projective configurations and convex polyhedra, Soviet Math. Doklady 32 (1985), 335--337.
• 27: Joseph O'Rourke , Ileana Streinu, Vertex-edge pseudo-visibility graphs: characterization and recognition, Proceedings of the thirteenth annual symposium on Computational geometry, p.119-128, June 04-06, 1997, Nice, France [doi>10.1145/262839.262915]
• 28: János Pach , Géza Tóth, Monotone Drawings of Planar Graphs, Proceedings of the 13th International Symposium on Algorithms and Computation, p.647-654, November 21-23, 2002
• 29: Michel Pocchiola , Gert Vegter, Pseudo-triangulations: theory and applications, Proceedings of the twelfth annual symposium on Computational geometry, p.291-300, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237398]
• 30: M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudo-triangulations, Discrete Comput. Geom. 16 (1996), 419--453.
• 31: D. Randall, G. Rote, F. Santos and J. Snoeyink Counting triangulations and pseudo-triangulations of wheels, in Proc. 13th Canad. Conf. Comput. Geom., 2001, pp. 149--152.
• 32: J. Richter-Gebert, Realization Spaces of Polytopes. Springer-Verlag, 1996.
• 33: G. Rote Two solvable cases of the traveling salesman problem, Ph.D. Thesis, Technische Universitat Graz, Institut für Mathematik, 1988.
• 34: G. Rote, F. Santos and I. Streinu Expansive motions and the polytope of pointed pseudo triangulations, in B. Aronov, S. Basu, J. Pach and M. Sharir (eds.), Discrete and Computational Geometry---The Goodman-Pollack Festschrift, Springer Verlag, to appear, 2003.
• 35: Bettina Speckmann , Csaba D. Tóth, Allocating vertex π-guards in simple polygons via pseudo-triangulations, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 36: Ileana Streinu, Stretchability of star-like pseudo-visibility graphs, Proceedings of the fifteenth annual symposium on Computational geometry, p.274-280, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304980]
• 37: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000
• 38: I. Streinu. Combinatorial roadmaps in configuration spaces of simple planar polygons, to appear in S. Basu and L. Gonzalez-Vega (eds.), Proc. DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, 2003.
• 39: Walter Schnyder, Embedding planar graphs on the grid, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.138-148, January 22-24, 1990, San Francisco, California, United States
• 40: K. Sugihara. Detection of structural inconsistency in systems of equations with degrees of freedom and its applications, Discrete Applied Mathematics, 10 (1985), 297--312.
• 41: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 42: T. S. Tay and W. Whiteley. Generating isostatic graphs, Structural Topology 11 (1985), 21--68.
• 43: M. F. Thorpe and P. M. Duxbury (eds.). Rigidity Theory and Applications, Kluwer Academic, 1999.
• 44: W. T. Tutte, How to draw a graph, Proc. London Math. Soc., III Ser. 13 (52), (1963) 743--768.
• 45: W. T. Tutte, Convex representations of graphs, Proc. London Math. Soc., III Ser. 10 (38), (1960), 304--320.
• 46: W. Whiteley. Rigidity of molecular structures: generic and geometric analysis, in Rigidity Theory and Applications (M. F. Thorpe and P. M. Duxbury, eds.), Kluwer, 1999, pp. 21--46.
• 47: W. Whiteley. Some matroids from discrete applied geometry, in J. E. Bonin et al. (ed.), Matroid theory, Contemporary Mathematics, vol. 197, Amer. Math. Soc., 1996, pp. 171--311,
• 48: Walter Whiteley, Rigidity and scene analysis, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
graph drawing, pseudo-triangulation, rigidity