A simple routing algorithm based on Schnyder coordinates

DOI10.1016/J.TCS.2013.01.017MaRDI QIDQ391094zbMATH OpenOpenAlexFDO

Authors Huaming Zhang, Xin He

Publication date 10 January 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2013.01.017

zbMATH Keywords

geometric routinggreedy routingnetwork routing problemsSchnyder coordinates

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Schnyder greedy routing algorithm
• An axiomatic approach to routing
• Succinct greedy geometric routing in the Euclidean plane
• A fast and simple Steiner routing heuristic
• Succinct Greedy Geometric Routing Using Hyperbolic Geometry
• An approximation algorithm for the general routing problem
• A minimax approach to a simple routing problem
• Algorithms for routing in planar graphs
• Shortest-Path Routing in Arbitrary Networks
• Compact routing on Euclidian metrics

Cites work

• A generalized greedy routing algorithm for 2-connected graphs
• An Algorithm to Construct Greedy Drawings of Triangulations
• Convex drawings of 3-connected plane graphs
• Convex drawings of planar graphs and the order dimension of 3-polytopes
• Distributed computation of virtual coordinates
• Distributed computation of virtual coordinates for greedy routing in sensor networks
• Geodesic embeddings and planar graphs
• Greedy drawings of triangulations
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• On a conjecture related to geometric routing
• On succinct convex greedy drawing of 3-connected plane graphs
• Output-sensitive reporting of disjoint paths
• Planar graphs and poset dimension
• Schnyder woods and orthogonal surfaces
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding
• Some results on greedy embeddings in metric spaces
• Succinct greedy drawings do not always exist
• Succinct greedy geometric routing in the Euclidean plane
• Succinct Greedy Graph Drawing in the Hyperbolic Plane

Cited in

(7)

• Every Schnyder drawing is a greedy embedding
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• Schnyder greedy routing algorithm
• Geographic routing on virtual raw anchor coordinate systems
• A generalized greedy routing algorithm for 2-connected graphs
• Toward Grünbaum's conjecture for 4-connected graphs
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs

This page was built for publication: A simple routing algorithm based on Schnyder coordinates

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