An O(n) Algorithm for Determining the Subregion-Tree Representation of a Rectangular Dissection

DOI10.1137/0222008zbMATH Open0768.68021OpenAlexW2085528566MaRDI QIDQ4037686FDOQ4037686

Authors: Sukhamay Kundu 

Publication date: 16 May 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222008

Recommendations

• The optimal representation of disjoint iso-oriented rectangles in two-dimensional trees
• Rectangular duals of planar graphs
• A (4n − 4)-Bit Representation of a Rectangular Drawing or Floorplan
• Rectangular dualization and rectangular dissections
• On Finding the Rectangular Duals of Planar Triangular Graphs

zbMATH Keywords

depth-first searchacyclic digraphtransitive reductionrectangular dissectionsubregion-tree representationwall representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cited In (2)

• An optimal design of piping route in a CAD system for power plant
• \(8k\)-ary grid graph models of tabular forms

This page was built for publication: An $O(n)$ Algorithm for Determining the Subregion-Tree Representation of a Rectangular Dissection

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