Exploiting Air-Pressure to Map Floorplans on Point Sets

Felsner, Stefan (2013) Exploiting Air-Pressure to Map Floorplans on Point Sets. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 196-207 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_18).

Full text not available from this repository.


We prove a conjecture of Ackerman, Barequet and Pinter. Every floorplan with n segments can be embedded on every set of n points in generic position. The construction makes use of area universal floorplans also known as area universal rectangular layouts. The notion of area used in our context depends on a nonuniform density function. We, therefore, have to generalize the theory of area universal floorplans to this situation. The method is then used to prove a result about accommodating points in floorplans that is slightly more general than the conjecture of Ackerman et al.

Item Type:Conference Paper
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.999 Others
Z Theory > Z.500 Representations
ID Code:1375

Repository Staff Only: item control page


Ackerman, E., Barequet, G., Pinter, R.Y.: On the number of rectangulations of a planar point set. J. Combin. Theory Ser. A 113, 1072–1091 (2006)

Asinowski, A., Barequet, G., Bousquet-Mélou, M., Mansour, T., Pinter, R.: Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations (2010) (submitted), arXiv:1011.1889

Buchsbaum, A.L., Gansner, E.R., Procopiuc, C.M., Venkatasubramanian, S.: Rectangular layouts and contact graphs. ACM Trans. Alg. 4, 28 pages (2008)

de Fraysseix, H., Ossona de Mendez, P.: On topological aspects of orientation. Discr. Math. 229, 57–72 (2001)

Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal and constrained rectangular layouts. SIAM J. Computing 41, 537–564 (2012)

Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213–248. Springer, New-York (2012)

Felsner, S., Fusy, É., Noy, M., Orden, D.: Bijections for Baxter families and related objects. Journal of Comb. Theory A 18, 993–1020 (2011)

Felsner, S., Huemer, C., Kappes, S., Orden, D.: Binary labelings for plane quadrangulations and their relatives. Discr. Math. & Theor. Comp. Sci. 12, 115–138 (2010)

Fusy, É.: Combinatoire des cartes planaires et applications algorithmiques. PhD thesis, LIX Ecole Polytechnique (2007), http://www.lix.polytechnique.fr/~fusy/Articles/these_eric_fusy.pdf

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

Izumi, T., Takahashi, A., Kajitani, Y.: Air-pressure model and fast algorithms for zero-wasted-area layout of general floorplan. IEICE Trans. Fundam. Electron., Commun. and Comp. Sci. E81-A, 857–865 (1998)

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

Schrenzenmaier, H.: Ein Luftdruckparadigma zur Optimierung von Zerlegungen. Bachelor’s Thesis, TU Berlin (2013)

Wimer, S., Koren, I., Cederbaum, I.: Floorplans, planar graphs, and layouts. IEEE Transactions on Circuits and Systems 35, 267–278 (1988)