Corner cuts are close to optimal: from solid grids to polygons and back

DOI10.1016/j.dam.2012.12.002zbMath1262.05125OpenAlexW2083686860MaRDI QIDQ1949103

Shantanu Das, Andreas Emil Feldmann, Peter Widmayer

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.12.002

zbMATH Keywords

grid graphspolygonsbisectionmin-cutcorner cuts\(m\)-cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05)

Related Items (1)

An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs

Cites Work

• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
• Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• How Good is Recursive Bisection?
• The bisection width of grid graphs
• Maximum area with Minkowski measures of perimeter
• Optimal Rectangular Partitions

This page was built for publication: Corner cuts are close to optimal: from solid grids to polygons and back