Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons

DOI10.1007/978-3-642-25870-1_14zbMath1341.68136OpenAlexW1866667937MaRDI QIDQ3104772

Shantanu Das, Andreas Emil Feldmann, Peter Widmayer

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/67937

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Fast balanced partitioning is hard even on grids and trees ⋮ Balanced tree partition problems with virtual nodes ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons ⋮ Balanced partitions of trees and applications

Cites Work

• A parallel algorithm for bisection width in trees
• Parallel approximation schemes for problems on planar graphs
• Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids
• Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons
• The bisection width of grid graphs
• Unnamed Item
• Unnamed Item