Every Schnyder drawing is a greedy embedding

DOI10.1016/J.TCS.2019.07.021MaRDI QIDQ2286747zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Leone, Kasun Samarasinghe, José Rolim

Publication date 22 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.04173

zbMATH Keywords

greedy embeddinggreedy routingmaximal planar graphsSchnyder drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Geographic routing is a routing paradigm, which uses geographic coordinates of network nodes to determine routes. Greedy routing, the simplest form of geographic routing forwards a packet to the closest neighbor towards the destination. A greedy embedding is a embedding of a graph on a geometric space such that greedy routing always guarantees delivery. A Schnyder drawing is a classical way to draw a planar graph. In this manuscript, we show that every Schnyder drawing is a greedy embedding, based on a generalized definition of greedy routing.

Recommendations

• On planar greedy drawings of 3-connected planar graphs
• On planar greedy drawings of 3-connected planar graphs
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• Euclidean greedy drawings of trees
• Euclidean greedy drawings of trees

Cites work

• A simple routing algorithm based on Schnyder coordinates
• Algorithmic Aspects of Wireless Sensor Networks
• An Algorithm to Construct Greedy Drawings of Triangulations
• Geographic routing on virtual raw anchor coordinate systems
• Greedy drawings of triangulations
• Greedy rectilinear drawings
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• Hyperbolic Embeddings for Near-Optimal Greedy Routing
• Monotone drawings of 3-connected plane graphs
• On succinct convex greedy drawing of 3-connected plane graphs
• On the efficiency of routing in sensor networks
• Planar graphs and poset dimension
• Routing with guaranteed delivery in ad hoc wireless networks
• Schnyder greedy routing algorithm
• Some results on greedy embeddings in metric spaces
• Succinct greedy geometric routing in the Euclidean plane
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• Succinct strictly convex greedy drawing of 3-connected plane graphs
• Virtual raw anchor coordinates: a new localization paradigm

This page was built for publication: Every Schnyder drawing is a greedy embedding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2286747)