Plane Cubic Graphs and the Air-Pressure Method

Felsner, Stefan and Kleist, Linda (2013) Plane Cubic Graphs and the Air-Pressure Method. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 536-537 .

Full text not available from this repository.


Thomassen[1] proved that plane cubic graphs are area-universal, i.e., for a plane cubic graph G with prescribed face areas there exists a stright-line (re-)drawing G’ that realizes these areas. Thomassen uses induction and proves the existence of a degenerate drawing where distinct vertices may be placed at the same position. We show that the plane cubic graphs are area-universal using the air-pressure method. In [2,3], a similar method has been applied in the context of area-universality of rectangular layouts. With the poster, we give the idea of how the method can be adapted for other classes of plane graphs, in particular for plane cubic graphs.

Item Type:Conference Poster
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:1415

Repository Staff Only: item control page


Thomassen, C.: Plane cubic graphs with prescribed face areas. Combinatorics, Probability & Computing 1(371-381), 2-10 (1992)

Felsner, S.: Exploiting air-pressure to map floorplans on point sets. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 196-207. Springer, Heidelberg (2013)

Izumi, T., Takahashi, A., Kajitani, Y.: Air-pressure model and fast algoritms for zero-wasted-area layout of general floorplan. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science 81(5), 857-865 (1998)