Drawing Planar 3-Trees with Given Face-Areas

摘要

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.