On a conjecture related to geometric routing

DOI10.1016/j.tcs.2005.06.022zbMath1079.68078OpenAlexW2169273227WikidataQ123150669 ScholiaQ123150669MaRDI QIDQ2575088

David Ratajczak, Christos H. Papadimitriou

Publication date: 5 December 2005

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

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

zbMATH Keywords

planar graphsad hoc networksgreedy routinggeometric routingconvex embeddingsplanar embeddings

Mathematics Subject Classification ID

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

Related Items (41)

On \(k\)-greedy routing algorithms ⋮ Succinct greedy drawings do not always exist ⋮ (Weakly) self-approaching geometric graphs and spanners ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ Monotone Drawings of 3-Connected Plane Graphs ⋮ Greedy drawings of triangulations ⋮ Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions ⋮ Nearly optimal monotone drawing of trees ⋮ Compact Monotone Drawing of Trees ⋮ Some results on greedy embeddings in metric spaces ⋮ A generalized greedy routing algorithm for 2-connected graphs ⋮ Euclidean greedy drawings of trees ⋮ Category-based routing in social networks: membership dimension and the small-world phenomenon ⋮ Greedy routing via embedding graphs onto semi-metric spaces ⋮ A simple routing algorithm based on Schnyder coordinates ⋮ Revisiting Hyperbolic Voronoi Diagrams in Two and Higher Dimensions from Theoretical, Applied and Generalized Viewpoints ⋮ Monotone Drawings of Graphs with Fixed Embedding ⋮ Optimal Monotone Drawings of Trees ⋮ Enumeration of graphs with a heavy-tailed degree sequence ⋮ Space lower bounds for low-stretch greedy embeddings ⋮ Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition ⋮ An optimal greedy routing algorithm for triangulated polygons ⋮ Shifting strategy for geometric graphs without geometry ⋮ Some results of Christos Papadimitriou on internet structure, network routing, and web information ⋮ Succinct strictly convex greedy drawing of 3-connected plane graphs ⋮ On succinct greedy drawings of plane triangulations and 3-connected plane graphs ⋮ Greedy Routing via Embedding Graphs onto Semi-metric Spaces ⋮ Monotone drawings of graphs with few directions ⋮ Minimum weight convex Steiner partitions ⋮ On the area requirements of planar greedy drawings of triconnected planar graphs ⋮ Navigation in spatial networks: a survey ⋮ Greedy rectilinear drawings ⋮ On planar greedy drawings of 3-connected planar graphs ⋮ Greedy rectilinear drawings ⋮ Succinct Greedy Graph Drawing in the Hyperbolic Plane ⋮ Drawing graphs as spanners ⋮ An Algorithm to Construct Greedy Drawings of Triangulations ⋮ Manhattan orbifolds ⋮ Unnamed Item ⋮ Deterministic greedy routing with guaranteed delivery in 3D wireless sensor networks ⋮ Monotone drawings of graphs with fixed embedding

Cites Work

• Unnamed Item
• Rubber bands, convex embeddings and graph connectivity
• Steinitz representations of polyhedra and the Colin de Verdière number
• Geometric ad-hoc routing
• Convex Representations of Graphs
• Lectures on Polytopes
• Random Geometric Graphs
• Routing with guaranteed delivery in ad hoc wireless networks

This page was built for publication: On a conjecture related to geometric routing