Greedy drawings of triangulations

ABSTRACT

Greedy Routing is a class of routing algorithms in which the packets are forwarded in a manner that reduces the distance to the destination at every step. In an attempt to provide theoretical guarantees for a class of greedy routing algorithms, Papadimitriou and Ratajczak [19] came up with the following conjecture:

Any 3-connected planar graph can be drawn in the plane such that for every pair of vertices s and t a distance decreasing path can be found. A path s = v₁, v₂,…,v_k=t in a drawing is said to be distance decreasing if ||v_i - t|| < ||v_i-1 -t||, 2 ≤ i ≤ k where || … || denotes the Euclidean distance.

We settle this conjecture in the affirmative for the case of triangulations.

A partitioning of the edges of a triangulation G into 3 trees, called the realizer of G, was first developed by Walter Schnyder who also gave a drawing algorithm based on this. We generalize Schnyder's algorithm to obtain a whole class of drawings of any given triangulation G. We show, using the Knaster-Kuratowski-Mazurkiewicz Theorem, that some drawing of G belonging to this class is greedy.

REFERENCES

• 1: Nicolas Bonichon , Stefan Felsner , Mohamed Mosbah, Convex Drawings of 3-Connected Plane Graphs, Algorithmica, v.47 n.4, p.399-420, March 2007 [doi>10.1007/s00453-006-0177-6]
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 3: E. Brehm. 3-orientations and schnyder 3-tree decompositions. Diplomarbeit, Freie Universitat, Berlin, 2000.
• 4: Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
• 5: S. Felsner. Convex drawings of planar graphs and the order dimension of 3-polytopes. Order, 18:19--37, 2001.
• 6: S. Felsner. Geometric Graphs and Arrangements. Vieweg Verlag, 2004.
• 7: Éric Fusy , Dominique Poulalhon , Gilles Schaeffer, Dissections and trees, with applications to optimal mesh encoding and to random sampling, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 9: 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]
• 10: G. Kant. Drawing planar graphs using the lmc-ordering. In Foundations of Computer Science, Proceedings., 33rd Annual Symposium on, pages 101--110, 1992.
• 11: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 12: Robert Kleinberg. Personal communication. 2006.
• 13: Robert Kleinberg. Geographic routing in hyperbolic space. In Workshop on Parallelism in Algorithms and Architectures. University of Maryland, College Park, May 12, 2006.
• 14: B. Knaster, C. Kuratowski, and C. Mazurkiewicz. Ein Beweis des Fixpunktsatzes fur n-dimensionale Simplexe. Fundamenta Mathematicae, 14:132--137, 1929.
• 15: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 16: N. Linial, L. Lovasz, and A. Wigderson. Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8(1):91--102, 1988.
• 17: Petar Maymounkov. Greedy embeddings, trees, and euclidean vs. lobachevsky geometry. Submitted, 2006.
• 18: Takao Nishizeki and Dr Md Saidur Rahman. Planar Graph Drawing. World Scientific Publishing, 2004.
• 19: Christos H. Papadimitriou , David Ratajczak, On a conjecture related to geometric routing, Theoretical Computer Science, v.344 n.1, p.3-14, 11 November 2005 [doi>10.1016/j.tcs.2005.06.022]
• 20: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 21: Günter Rote, Strictly convex drawings of planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 22: 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
• 23: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 24: W. T. Tutte. A theorem on planar graphs. Trans. Amer. Math. Soc., 82:99--116, 1956.
• 25: W. T. Tutte. Convex representations of graphs. In Proceedings of the London Mathematical Society, pages 304--320, 1960.

INDEX TERMS

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

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory