ABSTRACT
A layered drawing of a graph is a drawing such that the vertices are constrained to lie on geometric layers that can be lines, circles, or other kinds of curves. Partitioning the vertices into distinct layers can be an effective way to emphasize some structural properties of the graph; in many cases this is required in some real-world applications to convey the so-called semantic constraints [Sug02]. In this chapter, we concentrate on layered drawings of undirected graphs, where the
edges are not constrained to be monotone in a given direction. Conversely, this is typically a basic requirement in the layered drawings of directed graphs or hierarchies, where all edges must flow in a common direction (usually the vertical one), according to their orientation. Layered drawings algorithms for directed graphs are extensively investigated in Chapter 13. Although it is theoretically interesting to study layered drawings where the layers can be
curves of any type, it is rather difficult to extract properties and design algorithms if the layers do not have a quite “regular” shape. Indeed, most of the literature assumes that the layers are either parallel straight lines or concentric circles, which is also the most common requirement in real-world application domains. Therefore, we only give an overview of the results on layered drawings where layers are straight lines or circles. We call the first family of drawings spine drawings and the second family radial drawings . The remainder of this chapter is structured as follows. We first give formal definitions
that are needed in the chapter and describe a unified investigation framework for spine and radial drawings (Section 8.2). Then, we investigate the results on spine and radial drawings in a general scenario (Section 8.3); this scenario has the only requirement that the vertices are placed on layers. Results on scenarios that consider additional constraints are
investigated in Section 8.4. Finally, we mention some topological and geometric problems related to the spine and radial drawability of a graph (Section 8.5) and we give conclusions (Section 8.6).
