Some results on greedy embeddings in metric spaces

DOI10.1007/S00454-009-9227-6MaRDI QIDQ603850zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ankur Moitra, Tom Leighton

Publication date 8 November 2010

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-009-9227-6

zbMATH Keywords

excluded minorChristmas cactus graphgreedy embeddingPapadimitriou-Ratajczak conjecture

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Greedy Routing via Embedding Graphs onto Semi-metric Spaces
• Greedy routing via embedding graphs onto semi-metric spaces
• On a conjecture related to geometric routing
• Algorithmic Aspects of Wireless Sensor Networks
• Space lower bounds for low-stretch greedy embeddings

Cites work

• scientific article; zbMATH DE number 5764804 (Why is no real title available?)
• 2-walks in circuit graphs
• On a conjecture related to geometric routing
• Routing with guaranteed delivery in ad hoc wireless networks
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• Trees in Polyhedral Graphs

Cited in

(42)

• A simple routing algorithm based on Schnyder coordinates
• Optimal monotone drawings of trees
• On the plane angle-monotone graphs
• Angle-monotonicity of Delaunay triangulation
• On planar greedy drawings of 3-connected planar graphs
• Distributed computation of virtual coordinates for greedy routing in sensor networks
• A generalized greedy routing algorithm for 2-connected graphs
• An Algorithm to Construct Greedy Drawings of Triangulations
• Succinct strictly convex greedy drawing of 3-connected plane graphs
• Competitive routing in the half-\(\theta_6\)-graph
• Computing Tutte paths
• Minimum weight convex Steiner partitions
• Monotone drawings of 3-connected plane graphs
• Succinct greedy drawings do not always exist
• (Weakly) self-approaching geometric graphs and spanners
• Greedy rectilinear drawings
• Greedy rectilinear drawings
• On k-greedy routing algorithms
• Greedy routing via embedding graphs onto semi-metric spaces
• Gabriel triangulations and angle-monotone graphs: local routing and recognition
• Monotone drawings of graphs with fixed embedding
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• Monotone Drawings of Graphs with Fixed Embedding
• Shifting strategy for geometric graphs without geometry
• GEA: a greedy graph embedding algorithm.
• Drawing graphs as spanners
• Space lower bounds for low-stretch greedy embeddings
• Succinct greedy geometric routing in the Euclidean plane
• Space lower bounds for low-stretch greedy embeddings
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• Every Schnyder drawing is a greedy embedding
• An optimal greedy routing algorithm for triangulated polygons
• Algorithmic Aspects of Wireless Sensor Networks
• Euclidean greedy drawings of trees
• Euclidean greedy drawings of trees
• Angles of arc-polygons and lombardi drawings of cacti
• Monotone drawings of graphs with few directions
• Succinct Greedy Graph Drawing in the Hyperbolic Plane
• On the area requirements of planar greedy drawings of triconnected planar graphs
• Category-based routing in social networks: membership dimension and the small-world phenomenon
• Compact monotone drawing of trees
• Greedy Routing via Embedding Graphs onto Semi-metric Spaces

This page was built for publication: Some results on greedy embeddings in metric spaces

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