1 Search Results for "D'Angelo, Anthony"

Document
DOI: 10.4230/LIPIcs.SoCG.2017.33
On Planar Greedy Drawings of 3-Connected Planar Graphs

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

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2017.33,
  author =	{Da Lozzo, Giordano and D'Angelo, Anthony and Frati, Fabrizio},
  title =	{{On Planar Greedy Drawings of 3-Connected Planar Graphs}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.33},
  URN =		{urn:nbn:de:0030-drops-72095},
  doi =		{10.4230/LIPIcs.SoCG.2017.33},
  annote =	{Keywords: Greedy drawings, 3-connectivity, planar graphs, convex drawings}
}
  • Refine by Author
  • 1 D'Angelo, Anthony
  • 1 Da Lozzo, Giordano
  • 1 Frati, Fabrizio

  • Refine by Classification

  • Refine by Keyword
  • 1 3-connectivity
  • 1 Greedy drawings
  • 1 convex drawings
  • 1 planar graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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 Imprint Privacy Contact