Towards Characterizing Graphs with a Sliceable Rectangular Dual

Kusters, Vincent and Speckmann, Bettina (2015) Towards Characterizing Graphs with a Sliceable Rectangular Dual. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 460-471 (Official URL:

Full text not available from this repository.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
Z Theory > Z.750 Topology
ID Code:1512

Repository Staff Only: item control page


Ackerman, E., Barequet, G., Pinter, R.Y., Romik, D.: The number of guillotine partitions in d dimensions. Inf. Proces. Letters 98(4), 162–167 (2006)

Alam, M.J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. In: SOCG 2012, pp. 21–30 (2012)

de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. Disc. Math. 309(7), 1794–1812 (2009)

Bhasker, J., Sahni, S.: A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph. Networks 17(3), 307–317 (1987)

Bhattacharya, B., Sur-Kolay, S.: On the family of inherently nonslicible floorplans in VLSI layout design. In: ISCAS 1991, pp. 2850–2853. IEEE (1991)

Buchin, K., Speckmann, B., Verdonschot, S.: Optimizing regular edge labelings. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 117–128. Springer, Heidelberg (2011)

Dasgupta, P., Sur-Kolay, S.: Slicible rectangular graphs and their optimal floorplans. ACM Trans. Design Automation of Electronic Systems 6(4), 447–470 (2001)

Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal rectangular layouts. In: SOCG 2009, pp. 267–276 (2009)

Fusy, É.: Transversal structures on triangulations: A combinatorial study and straight-line drawings. Disc. Math. 309(7), 1870–1894 (2009)

He, X.: On floor-plan of plane graphs. SIAM J. Comp. 28(6), 2150–2167 (1999)

Kant, G., He, X.: Two algorithms for finding rectangular duals of planar graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 396–410. Springer, Heidelberg (1994)

Koźmiński, K., Kinnen, E.: Rectangular duals of planar graphs. Networks 15(2), 145–157 (1985)

van Kreveld, M., Speckmann, B.: On rectangular cartograms. Comp. Geom. 37(3), 175–187 (2007)

Liao, C.C., Lu, H.I., Yen, H.C.: Compact floor-planning via orderly spanning trees. J. Algorithms 48(2), 441–451 (2003)

Mumford, E.: Drawing Graphs for Cartographic Applications. Ph.D. thesis, TU Eindhoven (2008). http://​repository.​tue.​nl/​636963

Otten, R.: Efficient floorplan optimization. In: ICCAD’83. vol. 83, pp. 499–502 (1983)

Stockmeyer, L.: Optimal orientations of cells in slicing floorplan designs. Inf. Control 57(2), 91–101 (1983)

Sur-Kolay, S., Bhattacharya, B.: Inherent nonslicibility of rectangular duals in VLSI floorplanning. In: Kumar, S., Nori, K.V. (eds.) FSTTCS 1988. LNCS, vol. 338, pp. 88–107. Springer, Heidelberg (1988)

Szepieniec, A.A., Otten, R.H.: The genealogical approach to the layout problem. In: Proceedings of the 17th Conference on Design Automation, pp. 535–542. IEEE (1980)

Ungar, P.: On diagrams representing maps. J. L. Math. Soc. 1(3), 336–342 (1953)

Yao, B., Chen, H., Cheng, C.K., Graham, R.: Floorplan representations: Complexity and connections. ACM Trans. Design Auto. of Elec. Sys. 8(1), 55–80 (2003)

Yeap, G., Sarrafzadeh, M.: Sliceable floorplanning by graph dualization. SIAM J. Disc. Math. 8(2), 258–280 (1995)

Yeap, K.H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comp. 22(3), 500–526 (1993)