A linear algorithm to find a rectangular dual of a planar triangulated graph

DOI10.1007/BF01762117MaRDI QIDQ1097704zbMATH OpenOpenAlexWikidataFDO

Authors Jayaram Bhasker, Sartaj Sahni

Publication date 1988

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01762117

zbMATH Keywords

linear algorithmplanar triangulated graphrectangular dual

Mathematics Subject Classification ID

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

Cites work

• A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph
• Rectangular duals of planar graphs

Cited in

(33)

• Simple and efficient floor-planning
• Floorplanning by graph dualization: \(L\)-shaped modules
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Rectangular grid drawings of plane graphs
• Realization and connectivity of the graphs of origami flat foldings
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
• Drawing planar graphs using the canonical ordering
• A transformation algorithm to construct a rectangular floorplan
• A theory of L-shaped floor-plans
• Drawings of planar graphs with few slopes and segments
• Improved floor-planning of graphs via adjacency-preserving transformations
• Linear algorithm to find the largest intriangles of a planar convex polygon
• scientific article; zbMATH DE number 841998 (Why is no real title available?)
• Planar L-Drawings of Bimodal Graphs
• Transformations among rectangular partitions
• Planar L-drawings of bimodal graphs
• INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
• Rectangular drawings of plane graphs without designated corners
• Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
• Planar confluent orthogonal drawings of 4-modal digraphs
• Rectangular grid drawings of plane graphs
• Uniqueness of rectangularly dualizable graphs
• Linear-time construction of floor plans for plane triangulations
• An annotated review on graph drawing and its applications
• Two algorithms for finding rectangular duals of planar graphs
• A graph theoretic approach for generating T-shaped floor plans
• Construction of floorplans for plane graphs over polygonal boundaries
• Efficient enumeration of transversal edge-partitions
• Linear-time algorithm for generating L-shaped floorplans using canonical ordering technique
• Existence and construction of a C-shaped module within a floorplan
• Dynamic maintenance of planar digraphs, with applications
• A theory of rectangular dual graphs
• Rectangular-radial drawings of cubic plane graphs

This page was built for publication: A linear algorithm to find a rectangular dual of a planar triangulated graph

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