On the characterization of rectangular duals

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

1. Ackerman, E., Barequet, G., & Pinter, R. Y. (2006). A bijection between permutations and floorplans, and its applications. Discrete Applied Mathematics, 154(12), 1674–1684.
2. 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.
3. 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.
4. Bhasker, J., & Sahni, S. (1988). A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica, 247–278.
5. 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.
6. Chiang, Y.-T., Lin, C.-C., & Lu, H.-I. (2005). Orderly spanning trees with applications. SIAM Journal on Computing, 34(4), 924–945.
7. 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.
8. Eppstein, D., Mumford, E., Speckmann, B., & Verbeek, K. (2012). Area-universal and constrained rectangular layouts. SIAM Journal on Computing, 41(3), 537–564.
9. 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.
10. He, B. D. (2014). A simple optimal binary representation of mosaic floorplans and Baxter permutations. Theoretical Computer Science, 532, 40–50.
11. He, X. (1999). On floor-plan of plane graphs. SIAM Journal on Computing, 28(6), 2150–2167.
12. 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.
13. Koźmiński, K., & Kinnen, E. (1985). Rectangular duals of planar graphs.  Networks, 15(2), 145–157.
14. Kumar, V., & Shekhawat, K. (2021). Rectangularly dualizable graphs: Area-universality. Advances and Applications in Discrete Mathematics, 28(1), 75–91.
15. Kumar, V., & Shekhawat, K. (2021). A transformation algorithm to construct a rectangular floorplan. Theoretical Computer Science, 871, 94–106.
16. Kumar, V., & Shekhawat, K. (2023). Transformations among rectangular  partitions. Transactions on Combinatorics, 12(3), 143–163.
17. Kumar, V., & Shekhawat, K. (2024). Uniqueness of rectangularly dualizable graphs. Communications in Combinatorics and Optimization, 9(1), 13–25.
18. Kusters, V., & Speckmann, B. (2015). Towards characterizing graphs with a sliceable rectangular dual. In: International Symposium on Graph Drawing. Springer, 460–471.
19. 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.
20. Lai, Y.-T., & Leinwand, S. M. (1990). A theory of rectangular dual graphs. Algorithmica, 5(1–4), 467–483.
21. Merino, A., & Mütze, T. (2023). Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70(1), 51–122.
22. Reading, N. (2012). Generic rectangulations. European Journal of Combinatorics, 33(4), 610–623.
23. 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.
24. Ś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.
25. Yamanaka, K., Rahman, M. S., & Nakano, S.-I. (2017). Floorplans with columns. In: International Conference on Combinatorial Optimization and Applications. Springer, 33–40.
26. Yeap, K.-H., & Sarrafzadeh, M. (1993). Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal on Computing, 22(3), 500–526.
27. 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).