Document Open Access Logo

On Planar Greedy Drawings of 3-Connected Planar Graphs

Authors Giordano Da Lozzo, Anthony D'Angelo, Fabrizio Frati

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.33.pdf
  • Filesize: 1 MB
  • 16 pages

Document Identifiers

Author Details

Giordano Da Lozzo
Anthony D'Angelo
Fabrizio Frati

Cite As Get BibTex

Giordano Da Lozzo, Anthony D'Angelo, and Fabrizio Frati. On Planar Greedy Drawings of 3-Connected Planar Graphs. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.33

Abstract

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.

Subject Classification

Keywords
  • Greedy drawings
  • 3-connectivity
  • planar graphs
  • convex drawings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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. Google Scholar
  2. P. Angelini, G. Di Battista, and F. Frati. Succinct greedy drawings do not always exist. Networks, 59(3):267-274, 2012. Google Scholar
  3. 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. Google Scholar
  4. P. Angelini, F. Frati, and L. Grilli. An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl., 14(1):19-51, 2010. Google Scholar
  5. D. Barnette. Trees in polyhedral graphs. Canadian J. Math., 18:731-736, 1966. Google Scholar
  6. 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. Google Scholar
  7. G. Chen and X. Yu. Long cycles in 3-connected graphs. J. Comb. Theory, Ser. B, 86(1):80-99, 2002. Google Scholar
  8. G. Da Lozzo, A. D'Angelo, and F. Frati. On planar greedy drawings of 3-connected planar graphs. CoRR, 2016. URL: http://arxiv.org/abs/1612.09277.
  9. 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. Google Scholar
  10. H. R. Dehkordi, F. Frati, and J. Gudmundsson. Increasing-chord graphs on point sets. J. Graph Algorithms Appl., 19(2):761-778, 2015. Google Scholar
  11. R. Dhandapani. Greedy drawings of triangulations. Discr. Comp. Geom., 43(2):375-392, 2010. Google Scholar
  12. G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci., 61:175-198, 1988. Google Scholar
  13. D. Eppstein and M. T. Goodrich. Succinct greedy geometric routing using hyperbolic geometry. IEEE Trans. Computers, 60(11):1571-1580, 2011. Google Scholar
  14. S. Felsner, A. Igamberdiev, P. Kindermann, B. Klemz, T. Mchedlidze, and M. Scheucher. Strongly monotone drawings of planar graphs. In Fekete and Lubiw, editors, SoCG, volume 51 of LIPIcs, pages 37:1-37:15, 2016. Google Scholar
  15. H. Frey, S. Rührup, and I. Stojmenović. Routing in wireless sensor networks. In Misra, Woungang, and Misra, editors, Guide to Wireless Sensor Networks, Computer Communications and Networks, chapter 4, pages 81-111. Springer, 2009. Google Scholar
  16. M. T. Goodrich and D. Strash. Succinct greedy geometric routing in the Euclidean plane. In Dong, Du, and Ibarra, editors, ISAAC, volume 5878 of LNCS, pages 781-791, 2009. Google Scholar
  17. X. He and H. Zhang. On succinct greedy drawings of plane triangulations and 3-connected plane graphs. Algorithmica, 68(2):531-544, 2014. Google Scholar
  18. P. Kindermann, A. Schulz, J. Spoerhase, and A. Wolff. On monotone drawings of trees. In Duncan and Symvonis, editors, GD, volume 8871 of LNCS, pages 488-500, 2014. Google Scholar
  19. E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In CCCG, 1999. URL: http://www.cccg.ca/proceedings/1999/c46.pdf.
  20. F. Kuhn, R. Wattenhofer, and A. Zollinger. An algorithmic approach to geographic routing in ad hoc and sensor networks. IEEE/ACM Trans. Netw., 16(1):51-62, 2008. Google Scholar
  21. T. Leighton and A. Moitra. Some results on greedy embeddings in metric spaces. Discr. Comp. Geom., 44(3):686-705, 2010. Google Scholar
  22. M. Nöllenburg and R. Prutkin. Euclidean greedy drawings of trees. In Bodlaender and Italiano, editors, ESA, volume 8125 of LNCS, pages 767-778, 2013. Google Scholar
  23. M. Nöllenburg, R. Prutkin, and I. Rutter. On self-approaching and increasing-chord drawings of 3-connected planar graphs. J. Comp. Geom., 7(1):47-69, 2016. Google Scholar
  24. C. H. Papadimitriou and D. Ratajczak. On a conjecture related to geometric routing. In Nikoletseas and Rolim, editors, ALGOSENSORS, volume 3121 of LNCS, pages 9-17, 2004. Google Scholar
  25. C. H. Papadimitriou and D. Ratajczak. On a conjecture related to geometric routing. Theor. Comput. Sci., 344(1):3-14, 2005. Google Scholar
  26. A. Rao, C. H. Papadimitriou, S. Shenker, and I. Stoica. Geographic routing without location information. In Johnson, Joseph, and Vaidya, editors, MOBICOM, pages 96-108, 2003. Google Scholar
  27. C. Siva Ram Murthy and B. S. Manoj. Ad Hoc Wireless Networks: Architectures and Protocols. Prentice Hall, 2004. Google Scholar
  28. C. K. Toh. Ad Hoc Mobile Wireless Networks: Protocols and Systems. Prentice Hall, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact