Optimizing Regular Edge Labelings

Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander (2011) Optimizing Regular Edge Labelings. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 117-128 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_11).

Full text not available from this repository.

Abstract

A regular edge labeling (REL) of an irreducible triangulation G uniquely defines a rectangular dual of G. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this paper we consider optimization problems on RELs and show how to find optimal or near-optimal RELs for various quality criteria. Furthermore, we give upper and lower bounds on the number of RELs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_11
Classifications:G Algorithms and Complexity > G.999 Others
ID Code:1199

Repository Staff Only: item control page

References

Aarts, E., Korst, J., Michiels, W.: Simulated annealing. In: Search Methodologies, pp. 187–210. Springer, Heidelberg (2005)

Ackerman, E., Barequet, G., Pinter, R.Y.: A bijection between permutations and floorplans, and its applications. Disc. Appl. Math. 154(12), 1674–1684 (2006)

Aichholzer, O., Hackl, T., Vogtenhuber, B., Huemer, C., Hurtado, F., Krasser, H.: On the number of plane graphs. In: Proc. 17th SODA, pp. 504–513 (2006)

Amano, K., Nakano, S., Yamanaka, K.: On the number of rectangular drawings: Exact counting and lower and upper bounds. TR 2007-AL-115, IPSJ SIG (2007)

Avis, D., Fukuda, K.: Reverse search for enumeration. Disc. Appl. Math. 65(1), 21–46 (1996)

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

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 198–209. Springer, Heidelberg (2006)

Buchin, K., Knauer, C., Kriegel, K., Schulz, A., Seidel, R.: On the number of cycles in planar graphs. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 97–107. Springer, Heidelberg (2007)

Buchin, K., Schulz, A.: On the number of spanning trees a planar graph can have. In: Proc. 18th ESA (to appear, 2010), arXiv/0912.0712

Chung, F.R.K., Graham, R.L., Frankl, P., Shearer, J.B.: Some intersection theorems for ordered sets and graphs. J. Comb. Theory, Ser. A 43(1), 23–37 (1986)

Eppstein, D., Mumford, E.: Orientation-constrained rectangular layouts. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 49–60. Springer, Heidelberg (2009)

Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal rectangular layouts. In: Proc. 25th ACM Symp. Comp. Geom., pp. 267–276 (2009)

Felsner, S., Zickfeld, F.: On the number of planar orientations with prescribed degrees. Electron. J. Comb. 15(1), Research paper R77, 41 (2008)

Fujimaki, R., Inoue, Y., Takahashi, T.: An asymptotic estimate of the numbers of rectangular drawings or floorplans. In: Proc. ISCAS, pp. 856–859 (2009)

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

Horn, R., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)

Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. TCS 172(1-2), 175-193 (1997)

Kirkpatrick, S.: Optimization by simulated annealing: Quantitative studies. J. Statistical Physics 34(5), 975–986 (1984)

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

20. Minc, H.: Nonnegative Matrices. Wiley-Interscience, Hoboken (1988)

Peuquet, D., Ci-Xiang, Z.: An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane. Pattern Rec. 20(1), 65–74 (1987)

Speckmann, B., van Kreveld, M., Florisson, S.: A linear programming approach to rectangular cartograms. In: Progress in Spatial Data Handling: Proc. 12th International Symposium on Spatial Data Handling, pp. 529–546 (2006)

van Kreveld, M., Speckmann, B.: On rectangular cartograms. Computational Geometry: Theory and Applications 37(3), 175–187 (2007)

Yeap, G.K.H., Sarrafzadeh, M.: Sliceable floorplanning by graph dualization. SIAM J. Discrete Mathematics 8(2), 258–280 (1995)