آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,881 |
| تعداد دریافت فایل اصل مقاله | 1,060,653 |
Uniqueness of rectangularly dualizable graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 2، دوره 9، شماره 1، خرداد 2024، صفحه 13-25 اصل مقاله (409.26 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2022.27774.1350 | ||
| نویسندگان | ||
| Vinod Kumar* ؛ Krishnendra Shekhawat | ||
| Department of Mathematics, Birla Institute of Technology & Science, Pilani, Pilani Campus, Rajasthan−333031, India | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| plane graphs؛ rectangularly dualizable graphs؛ rectangular duals؛ rectangular partitions | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 493 تعداد دریافت فایل اصل مقاله: 1,437 |
||