Succinct strictly convex greedy drawing of 3-connected plane graphs

详细信息    查看全文

• 作者：Jiun-Jie Wang ; ^{jiunjiew@buffalo.edu" class="auth_mail} ; Xin He ^{xinhe@buffalo.edu" class="auth_mail}
• 关键词：3-connected plane graphs ; Succinct ; Convex greedy drawing
• 刊名：Theoretical Computer Science
• 出版年：1 May, 2014
• 年：2014
• 卷：532
• 期：Complete
• 页码：80-90
• 全文大小：324 K

文摘

Geometric routing by using virtual locations is an elegant way for solving network routing problems. Greedy routing, where a message is simply forwarded to a neighbor that is closer to the destination, is a simple form of geometric routing. A greedy drawing of a graph G is a drawing of G for which the greedy routing works. Papadimitriou and Ratajczak conjectured that every 3-connected plane graph has a greedy drawing on the plane (Papadimitriou and Ratajczak, 2005 ). Leighton and Moitra settled this conjecture positively in Leighton and Moitra (2010) . A similar result was obtained by Angelini et al. (2010) . However, their drawings have two major drawbacks: (1) their drawings are not necessarily planar; and (2) bits are needed to represent each coordinate of their drawings, which is too large for routing algorithms for certain networks. Recently, He and Zhang showed that every triangulated plane graph has a succinct (using bit coordinates) greedy drawing on the plane with respect to a metric function based on Schnyder realizers. However, their method does not work for 3-connected plane graphs.

In this paper, we show that every 3-connected plane graph has a drawing on the plane that is succinct, planar, strictly convex, and is greedy with respect to a metric function based on parameters derived from Schnyder woods.