Uniqueness of rectangularly dualizable graphs

Document Type : Original paper

Authors

Department of Mathematics, Birla Institute of Technology & Science, Pilani, Pilani Campus, Rajasthan−333031, India

Abstract

A generic rectangular partition   is a partition of a rectangle into a finite number of rectangles provided that no four of them meet at a point.  A graph $\mathcal{H}$ is called  dual of a plane graph $\mathcal{G}$ if there is one$-$to$-$one correspondence between the vertices of $\mathcal{G}$ and the regions of $\mathcal{H}$, and  two vertices of $\mathcal{G}$ are adjacent if and only if the corresponding regions of $\mathcal{H}$ are adjacent. A plane graph is a  rectangularly dualizable graph  if its dual  can be embedded as a  rectangular partition.   A rectangular dual  $\mathcal{R}$ of a plane graph $\mathcal{G}$ is a partition of a  rectangle  into $n-$rectangles such that (i) no four rectangles of $\mathcal{R}$ meet at a point, (ii)  rectangles in  $\mathcal{R}$ are mapped to vertices of $\mathcal{G}$,  and (iii)  two rectangles in $\mathcal{R}$ share a common boundary segment if and only if the corresponding vertices are adjacent in $\mathcal{G}$. In this paper, we derive a necessary and sufficient  for a rectangularly dualizable graph $\mathcal{G}$ to admit a unique rectangular dual upto combinatorial  equivalence. Further we show that $\mathcal{G}$ always admits   a slicible as well as an area$-$universal  rectangular dual.

Keywords

Main Subjects

References

[1] E. Ackerman, G. Barequet, and R.Y. Pinter, A bijection between permutations and floorplans, and its applications, Discrete Appl. Math. 154 (2006), no. 12, 1674–1684.  https://doi.org/10.1016/j.dam.2006.03.018
[2] J. Bhasker and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica 3 (1988), no. 1, 247–278.  http://dx.doi.org/10.1007/BF01762117
[3] T. Biedl, G. Kant, and M. Kaufmann, On triangulating planar graphs under the four-connectivity constraint, Algorithmica 19 (1997), no. 4, 427–446.  https://doi.org/10.1007/PL00009182
[4] K. Buchin, B. Speckmann, and S. Verdonschot, On the number of regular edge labelings, Discrete Math. Theor. Comput. Sci. 16 (2014), no. 3, 215–228.  http://dx.doi.org/10.46298/dmtcs.2085
[5] P. Dasgupta and S. Sur-Kolay, Slicible rectangular graphs and their optimal floor-plans, ACM Trans. Des. Autom. Electron. Syst. 6 (2001), no. 4, 447–470.  https://doi.org/10.1145/502175.502176
[6] D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek, Area-universal and constrained rectangular layouts, SIAM J. Comput. 41 (2012), no. 3, 537–564.  https://doi.org/10.1137/110834032
[7] É. Fusy, Transversal structures on triangulations: A combinatorial study and straight-line drawings, Discrete Math. 309 (2009), no. 7, 1870–1894.  https://doi.org/10.1016/j.disc.2007.12.093
[8] B.D. He, A simple optimal binary representation of mosaic floorplans and baxter permutations, Theoret. Comput. Sci. 532 (2014), 40–50.  https://doi.org/10.1016/j.tcs.2013.05.007
[9] X. He, On finding the rectangular duals of planar triangular graphs, SIAM J. Comput. 22 (1993), no. 6, 1218–1226. https://doi.org/10.1137/0222072
[10] G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems, Theoret. Comput. Sci. 172 (1997), no. 1-2, 175–193.  https://doi.org/10.1016/S0304-3975(95)00257-X
[11] K. Koźmiński and E. Kinnen, Rectangular duals of planar graphs, Networks 15 (1985), no. 2, 145–157.  https://doi.org/10.1002/net.3230150202
[12] K. Koźmiński and E. Kinnen, Rectangular dualization and rectangular dissections, IEEE Transactions on Circuits and Systems 35 (1988), no. 11, 1401–1416.  https://doi.org/10.1109/31.14464
[13] Y.T. Lai and S.M. Leinwand, Algorithms for floorplan design via rectangular dualization, IEEE transactions on computer-aided design of integrated circuits and systems 7 (1988), no. 12, 1278–1289.  https://doi.org/10.1109/43.16806
[14] Y.T. Lai and S.M. Leinwand, A theory of rectangular dual graphs, Algorithmica 5 (1990), no. 1-4, 467–483.  https://doi.org/10.1007/BF01840399
[15] N. Reading, Generic rectangulations, Eur. J. Combin. 33 (2012), no. 4, 610–623.  https://doi.org/10.1016/j.ejc.2011.11.004
[16] I. Rinsma, Nonexistence of a certain rectangular floorplan with specified areas and adjacency, Environment and Planning B: Planning and Design 14 (1987), no. 2, 163–166.  https://doi.org/10.1068/b140163
[17] I. Rinsma, Existence theorems for floorplans, Bull. Aust. Math. Soc. 37 (1988), no. 3, 473–475.
[18] K. Sakanushi, Y. Kajitani, and D.P. Mehta, The quarter-state-sequence floor-plan representation, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50 (2003), no. 3, 376–386.  https://doi.org/10.1109/TCSI.2003.809442
[19] K. Shekhawat, Enumerating generic rectangular floor plans, Automation in Construction 92 (2018), 151–165.  https://doi.org/10.1016/j.autcon.2018.03.037
[20] H. Tang and W.K. Chen, Generation of rectangular duals of a planar triangulated graph by elementary transformations, IEEE International Symposium on Circuits and Systems, IEEE, 1990, pp. 2857–2860.  https://doi.org/10.1109/ISCAS.1990.112606
[21] K. Yamanaka, M.S. Rahman, and S.I. Nakano, Floorplans with columns, International Conference on Combinatorial Optimization and Applications, Springer, 2017, pp. 33–40.
[22] B. Yao, H. Chen, C.K. Cheng, and R. Graham, Floorplan representations: Complexity and connections, ACM Trans. Des. Autom. Electron. Syst. 8 (2003), no. 1, 55–80.  https://doi.org/10.1145/606603.606607
[23] G.K.H. Yeap and M. Sarrafzadeh, Sliceable floorplanning by graph dualization, SIAM J. Discrete Math. 8 (1995), no. 2, 258–280.  https://doi.org/10.1137/S0895480191266700
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 13-25

Files

Share

How to cite

Statistics