The convex greedy embedding conjecture for 3-connected planar graphs and the Tutte spring-weight question

Greedy routing delivers a packet by always forwarding it to a neighbor strictly closer to the destination, and it is guaranteed to succeed precisely when the network graph is embedded at points forming a greedy embedding. Leighton and Moitra (2010) settled Papadimitriou and Ratajczak's greedy embedding conjecture by showing every 3-connected planar graph admits a Euclidean greedy embedding, and Da Lozzo, D'Angelo, and Frati (2018) strengthened this to planar greedy drawings — but it remains open whether the drawing can always be made convex: the convex greedy embedding conjecture, stated in the 2004 conference version of their paper. This problem asks whether every 3-connected planar graph admits a planar straight-line drawing, with every face bounded by a convex polygon, in which greedy routing always succeeds; in the strengthened form posed by Ghosh and Sinha (2009), whether the positive edge weights of Tutte's classical spring construction can always be chosen so that the resulting convex embedding is exactly greedy (weak-greedy ratio $\beta=1$). As of 2026, convex greedy drawings are known only for subclasses (triangulations, Halin graphs, and a few others), while the general conjecture and the Tutte-weight question remain open.

Background

In geographic (geometric) routing for ad-hoc and sensor networks, a node holding a packet for a destination $t$ simply forwards it to any neighbor that is closer to $t$ than itself. When nodes lack usable physical positions, one can instead assign virtual coordinates, which turns guaranteed-delivery routing into a question about graph drawings. A greedy embedding (also called a greedy drawing) of a graph $G=(V,E)$ in the Euclidean plane is an assignment $x:V\to\mathbb{R}^2$ such that for every ordered pair of distinct vertices $(s,t)$, the vertex $s$ has a neighbor $u$ (possibly $u=t$) with $|x(u)-x(t)|<|x(s)-x(t)|$; under this condition each packet can always make progress, so greedy routing never gets stuck at a node with no closer neighbor. The drawing is planar if the straight-line segments realizing the edges pairwise do not cross, and convex if it is planar and every face, including the outer face, is bounded by a convex polygon.

Papadimitriou and Ratajczak introduced this notion in 2004–2005 and identified 3-connected planar graphs (graphs that remain connected after deleting any two vertices and can be drawn without crossings; by Steinitz's theorem these are exactly the edge graphs of convex polyhedra) as the natural maximal candidate class: they constructed graphs admitting no Euclidean greedy embedding at all, including planar graphs that are not 3-connected and 3-connected graphs that are not planar. They posed two conjectures: (1) every 3-connected planar graph has a greedy embedding in the Euclidean plane, and (2) every 3-connected planar graph has a convex greedy embedding in the Euclidean plane. Conjecture (2), the subject of this problem, was stated in the 2004 conference version of their paper.

Conjecture (1) was settled affirmatively by Leighton and Moitra (FOCS 2008; journal version Discrete & Computational Geometry 2010): every circuit graph — by Barnette's definition, a graph obtained by deleting one vertex from a 3-connected planar graph — contains a spanning Christmas cactus graph (a connected cactus-like graph in which every two simple cycles share at most one vertex), and every Christmas cactus graph admits an explicit Euclidean greedy embedding; the same result was obtained independently by Angelini, Frati, and Grilli via triangulated binary cactuses (cactus-like graphs whose simple cycles are all triangles). However, these drawings are not planar in general and their coordinates require many bits. For the convex strengthening, the strongest known results are: every triangulation (maximal planar graph) has a greedy drawing, which is automatically a convex greedy drawing since all faces are triangles (Dhandapani 2010, an existential proof via randomly perturbed Schnyder drawings, where a Schnyder wood is a classical partition of a plane triangulation's interior edges into three edge-disjoint spanning trees rooted at the three outer vertices; a constructive algorithm was given by Angelini, Frati, and Grilli); every Halin graph — a graph obtained from a plane tree with no vertex of degree 2 by connecting its leaves into a cycle — admits a convex angle-monotone drawing on a polynomial grid, and angle-monotone drawings are greedy (Da Lozzo–D'Angelo–Frati 2020, where a drawing is angle-monotone if between any two vertices there is a path whose edges all lie in a closed wedge of bounded angle); and, most importantly, every 3-connected planar graph admits a planar greedy drawing (Da Lozzo–D'Angelo–Frati, SoCG 2017 and Discrete & Computational Geometry 2018/2020), obtained through a recursive structural decomposition of strong circuit graphs — the same authors report explicitly that they could not enforce convexity of faces within their decomposition and that the convex greedy embedding conjecture remains, in their words, an elusive goal. Thus the chain greedy, planar greedy, convex greedy is settled for its first two links and open for the third.

Ghosh and Sinha (arXiv:0905.3812; FCT 2009) approach the convex conjecture through the most classical source of convex drawings: Tutte's 1960 spring (rubber-band) theorem, which states that if the vertices of any face of a 3-connected planar graph are pinned on a convex polygon and every other vertex is placed at the barycenter — a weighted average with strictly positive edge weights — of its neighbors, then the unique equilibrium positions form a drawing in which every face is a convex polygon. Ghosh and Sinha define a $\beta$-weak greedy embedding as one in which, for every pair of non-adjacent vertices $s,t$, some neighbor $u$ of $s$ satisfies $|x(u)-x(t)|<\beta|x(s)-x(t)|$ for a fixed $\beta\ge 1$; their Definition 1.2 uses this strict inequality, so $\beta=1$ coincides with exact greediness on non-adjacent pairs (adjacent pairs are automatic, since $u=t$ qualifies), and the paper itself notes that a 1-weak greedy embedding makes the graph greedily embeddable. They prove that every 3-connected planar graph has a $\beta$-weak greedy convex embedding with $\beta\le 2\sqrt{2}\,d(G)$, where $d(G)$ is the ratio of the largest to the smallest pairwise vertex distance in the drawing, and that Tutte embeddings achieve this bound; but their cube example shows that a poor choice of spring weights destroys greediness ($\beta$ grows on the order of $d(G)$), so the selection of weights is the crux. They further characterize convex greedy embeddings of 3-connected planar graphs, for sufficiently large vertex count $|V|$, through the ratio of the total Euclidean edge lengths of the maximum-weight spanning tree $T$ and the minimum-weight spanning tree $\mathrm{MST}$ of the drawn graph: $x$ is a convex greedy embedding if and only if $\mathrm{wt}(T)/\mathrm{wt}(\mathrm{MST})\le(|V|-1)^{1-\delta}$ for some $\delta\in(0,1]$. Both directions of this characterization are existential: the admissible $\delta$ is not given as a function of any parameter, and the required threshold on $|V|$ is not quantified.

Several adjacent lines do not settle the problem. He and Zhang (Algorithmica 2014) showed Schnyder drawings of triangulations are greedy with respect to a metric $H$ satisfying $D_E\le H\le 2\sqrt{2}\,D_E$ relative to the Euclidean metric $D_E$, and Wang and He (2014) constructed for every 3-connected plane graph a succinct, planar, strictly convex drawing that is greedy with respect to a Schnyder-wood-derived metric — a metric relaxation, not the Euclidean greediness the conjecture demands. Kleinberg (INFOCOM 2007) embedded every tree greedily in the hyperbolic plane, and Eppstein and Goodrich (2011) gave succinct hyperbolic greedy routing; Angelini, Di Battista, and Frati (Networks 2012) proved that succinct greedy drawings — embeddings whose vertex coordinates use very few bits — do not always exist. For trees specifically, the greedy-drawable ones are now completely characterized (Nöllenburg–Prutkin 2017; Miyata–Nosaka 2022). Self-approaching drawings, in which any two vertices are joined by a path that gets strictly closer to the destination at every point along it and not only at the vertices — a strictly stronger property than greediness — and greedy rectilinear drawings (edges restricted to horizontal and vertical segments) are further active offshoots.

Problem Statement

The problem is a single existence question, pursuing a constructive theory of convex greedy embeddings of 3-connected planar graphs in the Euclidean plane.

Existence question. Does every 3-connected planar graph admit a convex greedy embedding in the Euclidean plane — a planar straight-line drawing in which every face, including the outer face, is bounded by a convex polygon, and in which for every ordered pair of distinct vertices $(s,t)$ the vertex $s$ has a neighbor $u$ with $|x(u)-x(t)|<|x(s)-x(t)|$? This is Papadimitriou and Ratajczak's convex greedy embedding conjecture (2004). It may be answered in the strengthened form posed by Ghosh and Sinha: for every 3-connected planar graph $G$, does there exist a choice of outer face, pinned on a convex polygon, and an assignment of strictly positive edge weights such that the Tutte (spring/barycentric) embedding of $G$ under these weights is an exact greedy embedding — that is, a $\beta$-weak greedy convex embedding with $\beta=1$, where a $\beta$-weak greedy embedding is one in which for every pair of non-adjacent vertices $s,t$ some neighbor $u$ of $s$ satisfies $|x(u)-x(t)|<\beta\,|x(s)-x(t)|$? Ghosh and Sinha's question does not pin the outer face; the reading above makes the choice of pinned outer face existential, and an even stronger variant — weights that work for every choice of pinned outer face — is not required by this problem. A positive answer to the Tutte form implies the conjecture, since Tutte embeddings of 3-connected planar graphs with positive weights are convex; the conjecture could also hold through convex greedy drawings that are not Tutte embeddings, so an existence proof need not go through Tutte weights. Conversely, the conjecture itself would be refuted by a single 3-connected planar graph that admits no convex greedy embedding at all; a 3-connected planar graph for which no choice of outer face and strictly positive weights makes the Tutte embedding greedy would refute only the strengthened Tutte form, not the conjecture.

Completion boundary. The problem is complete when the existence question is settled in either polarity — a rigorous proof that every 3-connected planar graph admits a convex greedy embedding (with or without the Tutte-weight realization), or a rigorously proved counterexample to the conjecture, that is, a 3-connected planar graph shown to admit no convex greedy embedding at all. Refuting only the strengthened Tutte form does not complete the problem, since the conjecture could still hold through convex greedy drawings that are not Tutte embeddings. Partial-class results — convex greedy drawings for a properly specified superclass of the known classes (triangulations, Halin graphs, graphs with Hamiltonian paths) — likewise constitute progress, not completion. Designing practical, state-minimal routing algorithms that exploit $\beta$-weak greedy embeddings is an applied engineering direction with no scientific completion boundary and does not count toward completion.

References

1. C. H. Papadimitriou and D. Ratajczak, 'On a conjecture related to geometric routing', Theoretical Computer Science 344(1):3–14, 2005. DOI: 10.1016/j.tcs.2005.06.022, https://doi.org/10.1016/j.tcs.2005.06.022 (the convex greedy embedding conjecture appears in the conference version 'On a Conjecture Related to Geometric Routing', ALGOSENSORS 2004, LNCS, pp. 9–17, DOI: 10.1007/978-3-540-27820-7_3)
2. S. K. Ghosh and K. Sinha, 'Some Results On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs', arXiv:0905.3812, 2009, https://arxiv.org/abs/0905.3812 (conference version: 'On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs', FCT 2009, pp. 145–156, DOI: 10.1007/978-3-642-03409-1_14)
3. W. T. Tutte, 'Convex Representations of Graphs', Proceedings of the London Mathematical Society s3-10(1):304–320, 1960. DOI: 10.1112/plms/s3-10.1.304, https://doi.org/10.1112/plms/s3-10.1.304
4. T. Leighton and A. Moitra, 'Some Results on Greedy Embeddings in Metric Spaces', Discrete & Computational Geometry 44(3):686–705, 2010. DOI: 10.1007/s00454-009-9227-6, https://doi.org/10.1007/s00454-009-9227-6 (conference version: FOCS 2008)
5. R. Dhandapani, 'Greedy drawings of triangulations', Discrete & Computational Geometry 43(2):375–392, 2010. DOI: 10.1007/s00454-009-9235-6, https://doi.org/10.1007/s00454-009-9235-6 (conference version: SODA 2008)
6. P. Angelini, F. Frati, and L. Grilli, 'An Algorithm to Construct Greedy Drawings of Triangulations', Journal of Graph Algorithms and Applications 14(1):19–51, 2010. DOI: 10.7155/jgaa.00197, https://jgaa.info/index.php/jgaa/article/view/paper197
7. G. Da Lozzo, A. D'Angelo, and F. Frati, 'On Planar Greedy Drawings of 3-Connected Planar Graphs', Discrete & Computational Geometry 63(1):114–157, 2020 (online 2018). DOI: 10.1007/s00454-018-0001-5, https://arxiv.org/abs/1612.09277 (conference version: SoCG 2017)
8. G. Da Lozzo, A. D'Angelo, and F. Frati, 'On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs', COCOON 2020, Lecture Notes in Computer Science 12273, pp. 435–447. DOI: 10.1007/978-3-030-58150-3_35, https://arxiv.org/abs/2003.00556
9. X. He and H. Zhang, 'On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs', Algorithmica 68(2):531–544, 2014. DOI: 10.1007/s00453-012-9682-y, https://doi.org/10.1007/s00453-012-9682-y
10. J.-J. Wang and X. He, 'Succinct strictly convex greedy drawing of 3-connected plane graphs', Theoretical Computer Science 532:80–90, 2014. DOI: 10.1016/j.tcs.2013.05.024, https://doi.org/10.1016/j.tcs.2013.05.024 (conference version: FAW-AAIM 2012, pp. 13–25, DOI: 10.1007/978-3-642-29700-7_2)
11. P. Leone, K. Samarasinghe, and J. D. P. Rolim, 'Every Schnyder drawing is a greedy embedding', Theoretical Computer Science 807:234–244, 2020. DOI: 10.1016/j.tcs.2019.07.021, https://doi.org/10.1016/j.tcs.2019.07.021 (preprint: arXiv:1609.04173, https://arxiv.org/abs/1609.04173, which lists only the first two authors)
12. R. Kleinberg, 'Geographic Routing Using Hyperbolic Space', IEEE INFOCOM 2007, pp. 1902–1909. DOI: 10.1109/INFCOM.2007.221, https://doi.org/10.1109/INFCOM.2007.221
13. D. Eppstein and M. T. Goodrich, 'Succinct Greedy Geometric Routing Using Hyperbolic Geometry', IEEE Transactions on Computers 60(11):1571–1580, 2011. DOI: 10.1109/TC.2010.257, https://doi.org/10.1109/TC.2010.257
14. P. Angelini, G. Di Battista, and F. Frati, 'Succinct greedy drawings do not always exist', Networks 59(3):267–274, 2012. DOI: 10.1002/net.21449, https://doi.org/10.1002/net.21449
15. M. Nöllenburg and R. Prutkin, 'Euclidean Greedy Drawings of Trees', Discrete & Computational Geometry 58(3):543–579, 2017. DOI: 10.1007/s00454-017-9913-8, https://arxiv.org/abs/1306.5224
16. H. Miyata and R. Nosaka, 'Complete combinatorial characterization of greedy-drawable trees', arXiv:2203.04664, 2022, https://arxiv.org/abs/2203.04664
17. S. Alamdari, T. M. Chan, E. Grant, A. Lubiw, and V. Pathak, 'Self-Approaching Graphs', arXiv:1306.5460, 2013, https://arxiv.org/abs/1306.5460 (conference version: GD 2012)
18. P. Angelini, M. A. Bekos, W. Didimo, L. Grilli, P. Kindermann, T. Mchedlidze, R. Prutkin, A. Symvonis, and A. Tappini, 'Greedy Rectilinear Drawings', Graph Drawing 2018, Lecture Notes in Computer Science, pp. 495–508. DOI: 10.1007/978-3-030-04414-5_35, https://arxiv.org/abs/1808.09063
19. R. Prutkin, 'A Note on the Area Requirement of Euclidean Greedy Embeddings of Christmas Cactus Graphs', arXiv:1605.09244, 2016, https://arxiv.org/abs/1605.09244