Partitioning graph drawings and triangulated simple polygons into greedily routable regions

DOI10.1007/978-3-662-48971-0_54zbMATH Open1372.68269arXiv1509.05635OpenAlexW2949922598MaRDI QIDQ3459901FDOQ3459901

Authors: Martin Nöllenburg, Roman Prutkin, Ignaz Rutter 

Publication date: 11 January 2016

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: A greedily routable region (GRR) is a closed subset of $mathbb{R}^2$, in which each destination point can be reached from each starting point by choosing 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 polygons 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, but can be solved optimally for trees in polynomial time. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected.

Full work available at URL: https://arxiv.org/abs/1509.05635

Recommendations

• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Greedy drawings of triangulations
• Succinct strictly convex greedy drawing of 3-connected plane graphs
• On succinct greedy drawings of plane triangulations and 3-connected plane graphs
• An optimal greedy routing algorithm for triangulated polygons

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (1)

• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

This page was built for publication: Partitioning graph drawings and triangulated simple polygons into greedily routable regions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459901)