×

zbMATH — the first resource for mathematics

Improved floor-planning of graphs via adjacency-preserving transformations. (English) Zbl 1239.05183
Summary: Let \(G=(V,E)\) and \(G^{\prime}=(V^{\prime},E^{\prime})\) be two graphs, an adjacency-preserving transformation from \(G\) to \(G^{\prime}\) is a one-to-many and onto mapping from \(V\) to \(V^{\prime}\) satisfying the following: (1) Each vertex \(v\in V\) in \(G\) is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in \(G^{\prime}\). The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of \(G^{\prime}\); (2) if \(u\neq v\in V\), then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices \(u\) and \(v\) are adjacent to each other in \(G\) if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in \(G^{\prime}\).
In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.
We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in C. C. Liao, H. I. Lu and H. C. Yen [J. Algorithms 48, No. 2, 441–451 (2003; Zbl 1073.68901)].

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05B45 Combinatorial aspects of tessellation and tiling problems
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Battista GD, Eades P, Tamassia R, Tollis I (1998) Graph drawing: algorithms for the visualization of graphs. Prentice Hall, New York · Zbl 1057.68653
[2] 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:307–317 · Zbl 0672.05025
[3] Bhasker J, Sahni S (1988) A linear algorithm to find for a rectangular dual of planar triangulated graph. Algorithmica 3:247–278 · Zbl 0635.68074
[4] Bonichon N, Saëc BL, Mosbah M (2002) Wagner’s theorem on realizers. In: Proceedings 29th international colloquium on automata, languages and programming. Lecture notes in computer science, vol 2380. Springer, Berlin, pp 1043–1053 · Zbl 1058.05057
[5] Brehm E (2000) 3-orientations and Schnyder 3-tree-decompositions: construction and order structure. Diploma thesis, FB Mathemtik und Informatik, Freie Universität. Berlin,
[6] Fusy É (2005) Transversal structures on triangulations, with application to straight-line drawing. In: Proceedings of 13th international symposium on graph drawing. Lecture notes in computer science, vol 3843. Springer, Berlin, pp 177–188 · Zbl 1171.68613
[7] He X (1993) On finding the rectangular duals of planar triangular graphs. SIAM J Comput 22:1218–1226 · Zbl 0786.05025
[8] He X (1999) On floor-plan of plane graphs. SIAM J Comput 28:2150–2167 · Zbl 0935.05039
[9] Koźmiński K, Kinnen E (1985) Rectangular dual of planar graphs. Networks 15:145–157 · Zbl 0585.05029
[10] Koźmiński K, Kinnen E (1988) Rectangular dualization and rectangular dissection. IEEE Trans Circuits Syst 35:1401–1416 · Zbl 0663.05027
[11] Kurowski M (2003) Simple and efficient floor-planning. Inf Process Lett 86:113–119 · Zbl 1173.68768
[12] Lai YT, Leinwand SM (1990) A theory of rectangular dual graphs. Algorithmica 5:467–483 · Zbl 0712.05053
[13] Liao CC, Lu HI, Yen HC (2003) Compact floor-planning via orderly spanning trees. J Algorithms 48:441–451 · Zbl 1073.68901
[14] Mailing K, Mueller SH, Heller WR (1982) On finding most optimal rectangular package planes. In: Proceedings of the 19th annual IEEE design automation conference, pp 263–270
[15] Schnyder W (1989) Planar graphs and poset dimension. Order 5:323–343 · Zbl 0675.06001
[16] Schnyder W (1990) Embedding planar graphs on the grid. In: Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, pp 138–148 · Zbl 0786.05029
[17] Sun Y, Sarrafzadeh M (1993) Floor-planning by graph dualization: L-shaped models. Algorithmica 10:429–456 · Zbl 0780.94019
[18] Yeap KH, Sarrafzadeh M (1993) Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J Comput 22:500–526 · Zbl 0774.05093
[19] Zhang H, Sadasivam S (2007) On planar polyline drawings. In: Proceedings of 15th international symposium on graph drawing. Lecture notes in computer science, vol 4875. Springer, Berlin, pp 213–218 · Zbl 1137.68507
[20] Zhang H (2010) Planar polyline drawings via graph transformations. Algorithmica 57:381–397 · Zbl 1191.68475
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.