RECTANGULARLY DUALIZABLE GRAPHS: AREA-UNIVERSALITY
From MaRDI portal
Publication:5076161
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)
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.
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
Cites work
- A theory of rectangular dual graphs
- 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
- Drawing planar graphs with prescribed face areas
- Existence theorems for floorplans
- Floorplans, planar graphs, and layouts
- On rectangular cartograms
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Rectangular duals of planar graphs
Cited in
(10)- Area-universal and constrained rectangular layouts
- Rectilinear duals using monotone staircase polygons
- Transformations among rectangular partitions
- Towards characterizing graphs with a sliceable rectangular dual
- Rectangular duals of planar graphs
- Rectangular dualization and rectangular dissections
- On Finding the Rectangular Duals of Planar Triangular Graphs
- Uniqueness of rectangularly dualizable graphs
- A theory of L-shaped floor-plans
- A theory of rectangular dual graphs
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)
