Minimum Size Representations of Graphs

Minimum Size Representations of Graphs

Topic home

Graph Drawing

 By type
 By year

Minimum Size Representations of Graphs

    Algorithms and bounds for drawing graphs in minimum volume or area.

    This topic deals with designing algorithms for drawing planar graphs on restricted two- and three-dimensional integer grids, and with proving lower bounds on the area and volume requirement of such drawings.

    Due to its strong connections with several important applications, as the layout of circuits and the display of complex relationships on a screen, the problem of drawing planar graphs in small area has always been one of the most studied problems in Graph Drawing. Even if the area requirement of a planar grid drawing of a planar graph has been shown to be worst-case quadratic, there are still interesting open problems concerning this topic. Determining the minimum size, in terms of constants, of a grid sufficient to draw every planar graph and determining the asymptotic area requirement of outerplanar graphs and trees are between such open questions.

    Recently, an increasing attention has been devoted to analogous questions in the three-dimensional space, where every graph can be drawn without intersections between edges. It has been proved a tight cubic bound on the volume requirement of an integer realization of a graph, but still some questions concerning the volume requirement of integer drawings of interesting family of graphs are open. The most posed question is whether a planar graph admits a linear volume drawing.