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 (Theor. Comput. Sci. 344(1):3–14, 2005) 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 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.

• Content Type Journal Article
• DOI 10.1007/s00454-009-9235-6
• Authors
  
  
  • Raghavan Dhandapani, New York University Courant Institute of Mathematical Sciences New York NY 10012 USA
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

Published by

Original source : http://www.springerlink.com/content/y71u68566g5623...