Drawing planar graphs with prescribed face areas

Linda Kleist

Abstract


We study drawings of planar graphs where every inner face has a prescribed area. A plane graph is 'area-universal' if for every area assignment on the inner faces, there exists a straight-line drawing realizing the assigned areas. The only non-area-universal graph known so far is the octahedron graph.

We give a simple counting argument that allows to prove non-area-universality for a large class of triangulations, namely Eulerian triangulations. Adding some geometric arguments, the concept  allows to prove non-area universality for other graphs including the icosahedron.

Relaxing the straight-line property by allowing the edges to bend, we show that  one bend per edge is sufficient to realize any face area assignment of every plane graph. For plane bipartite graphs, it even suffices that half of the edges have a bend.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v9i1a9

ISSN: 1920-180X