Abstract
Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈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′.
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 Liao et al. (J. Algorithms 48:441–451, 2003).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Battista GD, Eades P, Tamassia R, Tollis I (1998) Graph drawing: algorithms for the visualization of graphs. Prentice Hall, New York
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
Bhasker J, Sahni S (1988) A linear algorithm to find for a rectangular dual of planar triangulated graph. Algorithmica 3:247–278
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
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
He X (1993) On finding the rectangular duals of planar triangular graphs. SIAM J Comput 22:1218–1226
He X (1999) On floor-plan of plane graphs. SIAM J Comput 28:2150–2167
Koźmiński K, Kinnen E (1985) Rectangular dual of planar graphs. Networks 15:145–157
Koźmiński K, Kinnen E (1988) Rectangular dualization and rectangular dissection. IEEE Trans Circuits Syst 35:1401–1416
Kurowski M (2003) Simple and efficient floor-planning. Inf Process Lett 86:113–119
Lai YT, Leinwand SM (1990) A theory of rectangular dual graphs. Algorithmica 5:467–483
Liao CC, Lu HI, Yen HC (2003) Compact floor-planning via orderly spanning trees. J Algorithms 48:441–451
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
Schnyder W (1990) Embedding planar graphs on the grid. In: Proceedings of the first annual ACM-SIAM symposium on discrete algorithms, pp 138–148
Sun Y, Sarrafzadeh M (1993) Floor-planning by graph dualization: L-shaped models. Algorithmica 10:429–456
Yeap KH, Sarrafzadeh M (1993) Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J Comput 22:500–526
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
Zhang H (2010) Planar polyline drawings via graph transformations. Algorithmica 57:381–397
Author information
Authors and Affiliations
Corresponding author
Additional information
H. Zhang’s research is supported in part by NSF grant CCF-0728830.
Rights and permissions
About this article
Cite this article
Zhang, H., Sadasivam, S. Improved floor-planning of graphs via adjacency-preserving transformations. J Comb Optim 22, 726–746 (2011). https://doi.org/10.1007/s10878-010-9324-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9324-8