Planar graphs and face areas: Area-Universality
Linda Kleist · 2019
In this work, we study planar graphs with prescribed face areas. This field is inspired by cartograms. A 'cartogram' is a distorted map where the size of the regions are proportional to some statistical parameter such as the population, the total birth, the gross national product, or some other special property. As a mathematical abstraction we are interested in straight-line drawings of plane graphs realizing the prescribed faces areas. We say a plane graph is 'area-universal' if every area assignment to the inner faces has a realizing straight-line drawing. In the beginning of this thesis, not much was known. Specifically, there were three interesting facts: On the positive side, stacked triangulations and plane cubic graphs are area-universal. On the negative side, it is known that the octahedron is not area-universal. The aim of this thesis is to shed some more light into the world of area-universal graphs. The work is structured as follows: *Chapter 1: Introduction.* The concept of area-universality is introduced and the state of the art is presented. *Chapter 2: The Toolbox.* We introduce the basic notions and discuss properties of area-universal graphs. In particular, we introduce area-universality preserving operations and several characterizations of area-universality. These tools are used repeatedly throughout this thesis. *Chapter 3: Triangulations.* We study area-universality of maximal plane graphs, i.e., triangulations, and develop methods to prove and disprove area-universality. For the octahedron graph, we present a new proof technique to disprove its area-universality. Our proof relies on a simple counting argument that can also be used to show that no 'Eulerian triangulation' is area-universal. The result has several interesting consequences. Among them, there is no hope for constant factor approximations of realizing drawings even in the set of 4-connected triangulations. Adding some geometric arguments, a similar reasoning can be used for disproving the area-universality of other graphs. Moreover, we develop a sufficient criterion to guarantee the area-universality of triangulations with a special vertex order. The criterion relies on the investigation of area assignment. Combining these two techniques, we can characterize the area-universality of an interesting 4-connected family of triangulations. *Chapter 4: Quadrangulations.* We study the conjecture that all quadrangulations are area-universal. Even though we do not provide a full answer, we establish the area-universality of large classes of quadrangulations via reductions to related area-universal graphs. From our results it follows that a minimal counter example to the conjecture has at least 14 vertices. *Chapter 5: Drawings with Bends.* Given that not all plane graphs are area-universal, we investigate how much the straight-line property must be relaxed to realize each area assignment of every plane graph. We show that the 1-subdivision of every planar graph is area-universal, i.e., one bend per edge is sufficient. *Chapter 6: Related Concepts.* In this chapter, we study related concepts, in particular convex realizing drawings, equiareal drawings and realizing drawings for area assignments with negative values; in the latter case the drawings are not necessarily crossing-free. *Chapter 7: Computational Complexity.* We investigate the computational complexity of area-universality and present several interesting connections to the complexity class 'universal existential theory of the reals'. In particular, we show hardness of several variants of area-universality. *Chapter 8: Future Direction -- Air Pressure.* We transfer the idea of the air pressure method, which has previously been used in the context of area-universal rectangular layouts and seems promising to show area-universality of cubic graphs or other graph classes. *Chapter 9: Open Problems and Conjectures.* We conclude with our favorite set of open questions and ideas for further projects related to the study of plane graphs and faces areas.