Partitioning graph drawings and triangulated simple polygons into greedily routable regions

M. Nöllenburg, R. Prutkin, I. Rutter

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
56 Downloads (Pure)

Abstract

A greedily routable region (GRR) is a closed subset of ℝ2, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected.

Original languageEnglish
Pages (from-to)121-158
Number of pages38
JournalInternational Journal of Computational Geometry and Applications
Volume27
Issue number1-2
DOIs
Publication statusPublished - 1 Jun 2017

Keywords

  • Decomposing graph drawings
  • Greedy region decomposition
  • Greedy routing in wireless sensor networks
  • Increasing-chord drawings

Fingerprint

Dive into the research topics of 'Partitioning graph drawings and triangulated simple polygons into greedily routable regions'. Together they form a unique fingerprint.

Cite this