Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions

DOI10.1142/S0218195917600068MaRDI QIDQ5370573zbMATH OpenOpenAlexFDO

Authors Martin Nöllenburg, Roman Prutkin, 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)

Recommendations

• Partitioning graph drawings and triangulated simple polygons into greedily routable regions
• Greedy drawings of triangulations
• Partitioning Planar Graphs
• On Computational Aspects of Greedy Partitioning of Graphs
• Partitioning planar graphs with vertex costs: Algorithms and applications
• An optimal greedy routing algorithm for triangulated polygons
• Computational aspects of greedy partitioning of graphs
• scientific article; zbMATH DE number 2086813
• An Algorithm to Construct Greedy Drawings of Triangulations
• An Algorithm to Construct Greedy Drawings of Triangulations

Cites work

• A greedy algorithm for multicut and integral multiflow in rooted trees
• Decomposing a Polygon into Simpler Components
• Geometric versions of the three-dimensional assignment problem under general norms
• scientific article; zbMATH DE number 3986641 (Why is no real title available?)
• Increasing-chord graphs on point sets
• Minimal multicut and maximal integer multiflow: a survey
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• 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
• Planar Formulae and Their Uses
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Routing with guaranteed delivery in ad hoc wireless networks
• Self-approaching curves
• Self-approaching graphs
• The Problem of Compatible Representatives

Cited in

(2)

• Self-approaching paths in simple polygons
• 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 Q5370573)