# 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
Full Text:
##### References:
  Battista GD, Eades P, Tamassia R, Tollis I (1998) Graph drawing: algorithms for the visualization of graphs. Prentice Hall, New York · Zbl 1057.68653  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  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  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  Brehm E (2000) 3-orientations and Schnyder 3-tree-decompositions: construction and order structure. Diploma thesis, FB Mathemtik und Informatik, Freie Universität. Berlin,  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  He X (1993) On finding the rectangular duals of planar triangular graphs. SIAM J Comput 22:1218–1226 · Zbl 0786.05025  He X (1999) On floor-plan of plane graphs. SIAM J Comput 28:2150–2167 · Zbl 0935.05039  Koźmiński K, Kinnen E (1985) Rectangular dual of planar graphs. Networks 15:145–157 · Zbl 0585.05029  Koźmiński K, Kinnen E (1988) Rectangular dualization and rectangular dissection. IEEE Trans Circuits Syst 35:1401–1416 · Zbl 0663.05027  Kurowski M (2003) Simple and efficient floor-planning. Inf Process Lett 86:113–119 · Zbl 1173.68768  Lai YT, Leinwand SM (1990) A theory of rectangular dual graphs. Algorithmica 5:467–483 · Zbl 0712.05053  Liao CC, Lu HI, Yen HC (2003) Compact floor-planning via orderly spanning trees. J Algorithms 48:441–451 · Zbl 1073.68901  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  Schnyder W (1989) Planar graphs and poset dimension. Order 5:323–343 · Zbl 0675.06001  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  Sun Y, Sarrafzadeh M (1993) Floor-planning by graph dualization: L-shaped models. Algorithmica 10:429–456 · Zbl 0780.94019  Yeap KH, Sarrafzadeh M (1993) Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J Comput 22:500–526 · Zbl 0774.05093  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  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.