RECTANGULARLY DUALIZABLE GRAPHS: AREA-UNIVERSALITY

DOI10.17654/DM028010075zbMATH Open1499.68281arXiv2101.06912OpenAlexW3200465660MaRDI QIDQ5076161FDOQ5076161

Authors: Vinod Kumar, Krishnendra Shekhawat 

Publication date: 16 May 2022

Published in: Advances and Applications in Discrete Mathematics (Search for Journal in Brave)

Abstract: A plane graph is called a rectangular graph if each of its edges can be oriented either horizontally or vertically, each of its interior regions is a four-sided region and all interior regions can be fitted in a rectangular enclosure. If the dual of a plane graph is a rectangular graph, then the plane graph is a rectangularly dualizable graph. A rectangular dual is it area-universal if any assignment of areas to each of its regions can be realized by a combinatorially weak equivalent rectangular dual. It is still unknown that there exists no polynomial time algorithm to construct an area-universal rectangular dual for a rectangularly dualizable graph . In this paper, we describe a class of rectangularly dualizable graphs wherein each graph can be realized by an area-universal rectangular dual. We also present a polynomial time algorithm for its construction.

Full work available at URL: https://arxiv.org/abs/2101.06912

Recommendations

• A theory of rectangular dual graphs
• Rectangular duals of planar graphs
• On Finding the Rectangular Duals of Planar Triangular Graphs
• On area-universal quadrangulations
• Towards characterizing graphs with a sliceable rectangular dual
• On the area-universality of triangulations
• Dualizability of graphs
• Area-universal drawings of biconnected outerplane graphs
• Two algorithms for finding rectangular duals of planar graphs

zbMATH Keywords

cartogramrectangular dualVLSI circuitarea-universalityrectangularly dualizable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Area-universal and constrained rectangular layouts
• Area-universal drawings of biconnected outerplane graphs
• Computing cartograms with optimal complexity
• Drawing planar 3-trees with given face areas
• Rectangular duals of planar graphs
• Orthogonal Drawings for Plane Graphs with Specified Face Areas
• On rectangular cartograms
• A theory of rectangular dual graphs
• Floorplans, planar graphs, and layouts
• Drawing planar graphs with prescribed face areas
• Existence theorems for floorplans

Cited In (10)

• On Finding the Rectangular Duals of Planar Triangular Graphs
• Rectilinear duals using monotone staircase polygons
• A theory of rectangular dual graphs
• Area-universal and constrained rectangular layouts
• Towards characterizing graphs with a sliceable rectangular dual
• Uniqueness of rectangularly dualizable graphs
• Rectangular duals of planar graphs
• Transformations among rectangular partitions
• Rectangular dualization and rectangular dissections
• A theory of L-shaped floor-plans

This page was built for publication: RECTANGULARLY DUALIZABLE GRAPHS: AREA-UNIVERSALITY

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