Drawing Planar 3-Trees with Given Face-Areas

Biedl, Therese and Ruiz Velázquez, Lesvia Elena (2010) Drawing Planar 3-Trees with Given Face-Areas. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 316-322 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_30).

Full text not available from this repository.

Abstract

We study straight-line drawings of planar graphs such that each interior face has a prescribed area. It was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face-areas are rational, and we can bound the resolution. We also give some negative results for other graph classes.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_30
Classifications:P Styles > P.720 Straight-line
P Styles > P.540 Planar
ID Code:1066

Repository Staff Only: item control page

References

de Berg, M., Mumford, E., Speckmann, B.: On rectilinear duals for vertex-weighted plane graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 61–72. Springer, Heidelberg (2006)

Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal rectangular layouts. In: Proceedings of the 25th Annual Symposium on Computational Geometry. SCG 2009, Aarhus, Denmark, June 08-10, pp. 267–276. ACM, New York (2009)

Fáry, I.: On straight line representation of planar graphs. Acta. Sci. Math. Szeged 11, 229–233 (1948)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)

Geelen, J., Guo, A., McKinnon, D.: Straight line embeddings of cubic planar graphs with integer edge lengths. Journal of Graph Theory 58(3), 270–274 (2008)

Kratochvil, J., Thomas, R.: Manuscript (in preparation)

Ringel, G.: Equiareal graphs. In: Contemporary methods in graph theory, in honour of Prof. Dr. K. Wagner, pp. 503–505 (1990)

Schnyder, W.: Embedding planar graphs on the grid. In: 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138–148 (1990)

Stein, S.: Convex maps. Amer. Math. Soc. 2, 464–466 (1951)

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

van Kreveld, M., Speckmann, B.: On rectangular cartograms. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 724–735. Springer, Heidelberg (2004)

Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46, 26–32 (1936)