Drawing planar graphs with prescribed face areas

graph drawing;planar;prescribed face area;Computer Science

Ruiz Velázquez, Lesvia Elena

University of Waterloo

关键词: graph drawing;    planar;    prescribed face area;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/5481/1/RuizVelazquezLesviaElena.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis deals with planar drawings of planar graphs such that each interior face hasa prescribed area.Our work is divided into two main sections. Therst one deals with straight-line drawingsand the second one with orthogonal drawings.For straight-line drawings, it was known that such drawings exist for all planar graphswith 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 inone triangle and connecting it to all vertices of the triangle. Moreover, vertices have rationalcoordinates if the face areas are rational, and we can bound the resolution.For orthogonal drawings, we give an algorithm to draw triconnected planar graphs withmaximum degree 3. This algorithm produces a drawing with at most 8 bends per face and4 bends per edge, which improves the previous known result of 34 bends per face. Bothvertices and bends have rational coordinates if the face areas are rational.