Every Schnyder Drawing is a Greedy Embedding
2019
Abstract In this paper, we show that every Schnyder drawing is a greedy embedding. Schnyder drawings are used to represent planar (maximal) graphs. It is a way of getting coordinates in R 2 given a graph G = ( V , E ) such that the representation is planar. The Schnyder technique leads to a family of representations and previous results show that a particular representation may be chosen such that the drawing has additional properties like being greedy or monotone . In this article, we relax the definition of greediness to a definition that does not rely on the geometry and the Euclidean distance in R 2 , but rather on the combinatorial graph G . The construction of greedy paths valid for all Schnyder representations shows that, provided the relaxed definition, every Schnyder drawing is a greedy embedding.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
38
References
1
Citations
NaN
KQI