**Vinod Kumar and Krishnendra Shekhawat**

Notes on Number Theory and Discrete Mathematics

Print ISSN 1310–5132, Online ISSN 2367–8275

Volume 30, 2024, Number 1, Pages 141–149

DOI: 10.7546/nntdm.2024.30.1.141-149

**Full paper (PDF, 181 Kb)**

## Details

### Authors and affiliations

Vinod Kumar

*Department of Mathematics, BITS Pilani
Pilani Campus, Rajasthan-333031, India*

Krishnendra Shekhawat

*Department of Mathematics, BITS Pilani
Pilani Campus, Rajasthan-333031, India*

### Abstract

A rectangular partition is a partition of a rectangle into a finite number of rectangles. A rectangular partition is generic if no four of its rectangles meet at the same point. A plane graph is called a rectangularly dualizable graph if can be represented as a rectangular partition such that each vertex is represented by a rectangle in the partition and each edge is represented by a common boundary segment shared by the corresponding rectangles. Then the rectangular partition is called a rectangular dual of the RDG. In this paper, we have found a minor error in a characterization for rectangular duals given by Koźmiński and Kinnen in 1985 without formal proof, and we fix this characterization with formal proof.

### Keywords

- Planar graph
- Rectangularly dualizable graph
- Rectangular partition
- Rectangular dual

### 2020 Mathematics Subject Classification

- 68U05

### References

- Ackerman, E., Barequet, G., & Pinter, R. Y. (2006). A bijection between permutations and floorplans, and its applications.
*Discrete Applied Mathematics*, 154(12), 1674–1684. - Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S. G., & Ueckerdt, T. (2013). Computing cartograms with optimal complexity.
*Discrete & Computational Geometry*, 50(3), 784–810. - Bhasker, J., & Sahni, S. (1987). A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph.
*Networks*, 17(3), 307–317. - Bhasker, J., & Sahni, S. (1988). A linear algorithm to find a rectangular dual of a planar triangulated graph.
*Algorithmica*, 247–278. - Chaplick, S., Felsner, S., Kindermann, P., Klawitter, J., Rutter, I., & Wolff, A. (2022). Simple algorithms for partial and simultaneous rectangular duals with given contact orientations.
*Theoretical Computer Science*, 919, 66–74. - Chiang, Y.-T., Lin, C.-C., & Lu, H.-I. (2005). Orderly spanning trees with applications.
*SIAM Journal on Computing*, 34(4), 924–945. - Dasgupta, P., & Sur-Kolay, S. (2001). Slicible rectangular graphs and their optimal floorplans.
*ACM Transactions on Design Automation of Electronic Systems*, 6(4), 447–470. - Eppstein, D., Mumford, E., Speckmann, B., & Verbeek, K. (2012). Area-universal and constrained rectangular layouts.
*SIAM Journal on Computing*, 41(3), 537–564. - Felsner, S., Nathenson, A., & Tóth, C. D. (2022). Aspect ratio universal rectangular layouts. In
*: International Conference and Workshops on Algorithms and Computation*. Springer, 73–84. - He, B. D. (2014). A simple optimal binary representation of mosaic floorplans and Baxter permutations.
*Theoretical Computer Science*, 532, 40–50. - He, X. (1999). On floor-plan of plane graphs.
*SIAM Journal on Computing*, 28(6), 2150–2167. - Kant, G., & He, X. (1997). Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems.
*Theoretical Computer Science*, 172(1–2), 175–193. - Koźmiński, K., & Kinnen, E. (1985). Rectangular duals of planar graphs.
*Networks*, 15(2), 145–157. - Kumar, V., & Shekhawat, K. (2021). Rectangularly dualizable graphs: Area-universality.
*Advances and Applications in Discrete Mathematics*, 28(1), 75–91. - Kumar, V., & Shekhawat, K. (2021). A transformation algorithm to construct a rectangular floorplan.
*Theoretical Computer Science*, 871, 94–106. - Kumar, V., & Shekhawat, K. (2023). Transformations among rectangular partitions.
*Transactions on Combinatorics*, 12(3), 143–163. - Kumar, V., & Shekhawat, K. (2024). Uniqueness of rectangularly dualizable graphs.
*Communications in Combinatorics and Optimization*, 9(1), 13–25. - Kusters, V., & Speckmann, B. (2015). Towards characterizing graphs with a sliceable rectangular dual. In:
*International Symposium on Graph Drawing*. Springer, 460–471. - Lai, Y.-T., & Leinwand, S. M. (1988). Algorithms for floorplan design via rectangular dualization.
*IEEE Transactions on Computer-Aided Design of Integrated Circuits and**Systems*, 7(12), 1278–1289. - Lai, Y.-T., & Leinwand, S. M. (1990). A theory of rectangular dual graphs.
*Algorithmica*, 5(1–4), 467–483. - Merino, A., & Mütze, T. (2023). Combinatorial generation via permutation languages. III. Rectangulations.
*Discrete & Computational Geometry*, 70(1), 51–122. - Reading, N. (2012). Generic rectangulations.
*European Journal of Combinatorics*, 33(4), 610–623. - Rinsma, I. (1987). Nonexistence of a certain rectangular floorplan with specified areas and adjacency.
*Environment and Planning B: Planning and Design*, 14(2), 163–166. - Ślusarczyk, G., Strug, B., Paszyńska, A., Grabska, E., & Palacz, W. (2023). Semantic-driven graph transformations in floor plan design.
*Computer-Aided Design*, 158, 103480. - Yamanaka, K., Rahman, M. S., & Nakano, S.-I. (2017). Floorplans with columns. In:
*International Conference on Combinatorial Optimization and Applications*. Springer, 33–40. - Yeap, K.-H., & Sarrafzadeh, M. (1993). Floor-planning by graph dualization: 2-concave rectilinear modules.
*SIAM Journal on Computing*, 22(3), 500–526. - Zhang, H., & Sadasivam, S. (2011). Improved floor-planning of graphs via adjacency-preserving transformations.
*Journal of Combinatorial Optimization*, 22(4), 726–746.

### Manuscript history

- Received: 22 July 2023
- Revised: 10 December 2024
- Accepted: 7 March 2024
- Online First: 9 March 2024

### Copyright information

Ⓒ 2024 by the Authors.

This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

## Related papers

## Cite this paper

Kumar, V., & Shekhawat, K. (2024). On the characterization of rectangular duals. *Notes on Number Theory and Discrete Mathematics*, 30(1), 141-149, DOI: 10.7546/nntdm.2024.30.1.141-149.