Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013
Exploiting Air-Pressure to Map Floorplans on Point Sets
Vol. 18, no. 2, pp. 233-252, 2014. Regular paper.
Abstract We prove a conjecture of Ackerman, Barequet and Pinter. Every floorplan with n internal 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 non-uniform density function. We, therefore, have to generalize the theory of area universal floorplans to this situation. For the proof we use the air-pressure approach of Izumi, Takahashi and Kajitani. The method is then used to prove a result about accommodating points in floorplans that is slightly more general than the original conjecture. We close with some remarks on the counting problem that motivated the conjecture of Ackerman et al.
Submitted: December 2013.
Reviewed: February 2014.
Revised: March 2014.
Accepted: April 2014.
Final: April 2014.
Published: May 2014.