Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

DOI10.1142/S0218195917600068zbMath1372.68270OpenAlexW2963776120MaRDI QIDQ5370573

Roman Prutkin, Martin Nöllenburg, Ignaz Rutter

Publication date: 20 October 2017

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195917600068

zbMATH Keywords

decomposing graph drawingsgreedy region decompositiongreedy routing in wireless sensor networksincreasing-chord drawings

Mathematics Subject Classification ID

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

Related Items

Self-approaching paths in simple polygons

Cites Work

• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Geometric versions of the three-dimensional assignment problem under general norms
• A greedy algorithm for multicut and integral multiflow in rooted trees
• On a conjecture related to geometric routing
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions
• Decomposing a Polygon into Simpler Components
• Planar Formulae and Their Uses
• The Problem of Compatible Representatives
• Self-approaching curves
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Self-approaching Graphs
• Increasing-Chord Graphs On Point Sets
• Routing with guaranteed delivery in ad hoc wireless networks