• shareshare
  • link
  • cite
  • add
Other research product . 2017

On Planar Greedy Drawings of 3-Connected Planar Graphs

Da Lozzo, Giordano; D'Angelo, Anthony; Frati, Fabrizio;
Open Access
Published: 01 Jan 2017
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Country: Germany

A graph drawing is greedy if, for every ordered pair of vertices (x,y), there is a path from x to y such that the Euclidean distance to y decreases monotonically at every vertex of the path. Greedy drawings support a simple geometric routing scheme, in which any node that has to send a packet to a destination "greedily" forwards the packet to any neighbor that is closer to the destination than itself, according to the Euclidean distance in the drawing. In a greedy drawing such a neighbor always exists and hence this routing scheme is guaranteed to succeed. In 2004 Papadimitriou and Ratajczak stated two conjectures related to greedy drawings. The greedy embedding conjecture states that every 3-connected planar graph admits a greedy drawing. The convex greedy embedding conjecture asserts that every 3-connected planar graph admits a planar greedy drawing in which the faces are delimited by convex polygons. In 2008 the greedy embedding conjecture was settled in the positive by Leighton and Moitra. In this paper we prove that every 3-connected planar graph admits a planar greedy drawing. Apart from being a strengthening of Leighton and Moitra's result, this theorem constitutes a natural intermediate step towards a proof of the convex greedy embedding conjecture.

Subjects by Vocabulary

Dewey Decimal Classification: ddc:004

ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY


Greedy drawings, 3-connectivity, planar graphs, convex drawings, Data processing Computer science

28 references, page 1 of 3

S. Alamdari, T. M. Chan, E. Grant, A. Lubiw, and V. Pathak. Self-approaching graphs. In Didimo and Patrignani, editors, GD, volume 7704 of LNCS, pages 260-271, 2012.

Networks, 59(3):267-274, 2012.

P. Angelini, E. Colasante, G. Di Battista, F. Frati, and M. Patrignani. Monotone drawings of graphs. J. Graph Algorithms Appl., 16(1):5-35, 2012.

P. Angelini, F. Frati, and L. Grilli. An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl., 14(1):19-51, 2010. [OpenAIRE]

D. Barnette. Trees in polyhedral graphs. Canadian J. Math., 18:731-736, 1966. [OpenAIRE]

P. Bose, P. Morin, I. Stojmenović, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 7(6):609-616, 2001.

G. Chen and X. Yu. Long cycles in 3-connected graphs. J. Comb. Theory, Ser. B, 86(1):80- 99, 2002. [OpenAIRE]

G. Da Lozzo, A. D'Angelo, and F. Frati. On planar greedy drawings of 3-connected planar graphs. CoRR, 2016. URL: [OpenAIRE]

G. Da Lozzo, V. Dujmović, F. Frati, T. Mchedlidze, and V. Roselli. Drawing planar graphs with many collinear vertices. In Hu and Nöllenburg, editors, GD, volume 9801 of LNCS, pages 152-165, 2016. [OpenAIRE]

Graph Algorithms Appl., 19(2):761-778, 2015.

Funded by
  • Funder: Natural Sciences and Engineering Research Council of Canada (NSERC)
Combinatorics of Networks and Computation
  • Funder: European Commission (EC)
  • Project Code: 734922
  • Funding stream: H2020 | MSCA-RISE