TY - GEN
T1 - Succinct strictly convex greedy drawing of 3-connected plane graphs
AU - Wang, Jiun Jie
AU - He, Xin
PY - 2012
Y1 - 2012
N2 - 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. Papadimitriou and Ratajczak conjectured that every 3-connected plane graph has a greedy drawing in the plane [10]. Leighton and Moitra settled this conjecture positively in [9]. However, their drawings have two major drawbacks: (1) their drawings are not necessarily planar; and (2) Ω(nlogn) bits are needed to represent the coordinates of their drawings, which is too large for routing algorithms for wireless networks. Recently, He and Zhang [8] showed that every triangulated plane graph has a succinct (using O(logn) bit coordinates) greedy drawing in plane with respect to a metric function derived from Schnyder realizer. However, their method fails for 3-connected plane graphs. In this paper, we show that every 3-connected plane graph has drawing in the plane, that is succinct, planar, strictly convex, and is greedy with respect to a metric function based on parameters derived from Schnyder wood.
AB - 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. Papadimitriou and Ratajczak conjectured that every 3-connected plane graph has a greedy drawing in the plane [10]. Leighton and Moitra settled this conjecture positively in [9]. However, their drawings have two major drawbacks: (1) their drawings are not necessarily planar; and (2) Ω(nlogn) bits are needed to represent the coordinates of their drawings, which is too large for routing algorithms for wireless networks. Recently, He and Zhang [8] showed that every triangulated plane graph has a succinct (using O(logn) bit coordinates) greedy drawing in plane with respect to a metric function derived from Schnyder realizer. However, their method fails for 3-connected plane graphs. In this paper, we show that every 3-connected plane graph has drawing in the plane, that is succinct, planar, strictly convex, and is greedy with respect to a metric function based on parameters derived from Schnyder wood.
UR - https://www.scopus.com/pages/publications/84861217889
U2 - 10.1007/978-3-642-29700-7_2
DO - 10.1007/978-3-642-29700-7_2
M3 - Conference contribution
AN - SCOPUS:84861217889
SN - 9783642296994
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 25
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Proceedings
T2 - 6th International Frontiers of Algorithmics Workshop, FAW 2012 and 8th International Conference on Algorithmic Aspects of Information and Management, AAIM 2012
Y2 - 14 May 2012 through 16 May 2012
ER -