Area requirement of graph drawings with few crossings per edge

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Graph theory (including graph drawing) in computer science (68R10)

Review text

In the paper the authors study the compact straight-line drawings of planar graphs with few crossings per edge. At the beginning the authors give definitions from the graph theory used in the paper. Next, they introduce the general drawing strategy. In the proposed strategy important role plays: leveling, proper level drawing and folding. Leveling is a labeling of all vertices of the graph with non-negative integer numbers \(0, 1, \ldots, r\) called levels. The proper level drawing of a graph with respect to some leveling has three properties: all vertices from the same level have the same \(y\)-coordinate, for each edge the \(y\)-coordinates of its ends differs by at most \(1\), for any two levels \(j < l\) all vertices of level \(l\) are to the right of all vertices of level \(j\). When we have the leveling and proper level drawing of some graph, then level \(l\) is folded in the drawing if the \(y\)-coordinates of vertices from levels \(l-1\) and \(l+1\) are equal. The proposed strategy is divided into two stages. In the first stage we find leveling and a proper level drawing without folded levels. In the second stage we construct new proper level drawing using the drawing from stage one and folding. Next, the authors prove that for a graph with \(n\) vertices and given leveling, proper level drawing and integer \(d \geq 0\) we can compute a drawing such that it has \(O(k(n))\) crossings per edge (\(k(n) : N \rightarrow N\) is a function such that \(k(n)\in O(n)\) and \(k(n) > d\) for every \(n \geq n_0\), for some \(n_0 \geq 0\)), and has area \(O(n^2 / k(n))\) in \(O(n)\) time. In the proof they give the so-called folding condition which is used to determine when we should use the folding in the second stage of the proposed strategy. After introducing the general strategy the authors study the outerplanar graphs and flat series-parallel graphs. For the former one they use the result of \textit{S. Felsner, G. Liotta} and \textit{S. K. Wismath} [J. Graph Algorithms Appl. 7, No. 4, 363--398 (2003; Zbl 1068.68103)] for leveling and the proposed folding. Moreover, they give a corollary in which they give the bounds on crossings per edge and the area of drawing of an outerplanar graph with \(n\) vertices for \(k(n) = \theta(n / \log n)\) and \(k(n) = \theta(n^{1-\varepsilon})\). For the latter one the authors use in the leveling stage the technique described in the authors [Lect. Notes Comput. Sci. 7551, 91--102 (2012; Zbl 1341.05173)]. The authors give similar corollary as in the case of outerplanar graphs for a flat series-parallel graphs with \(n\) vertices and vertex degree at most \(d\) for \(k(n) = \theta(n / \log n)\) and \(k(n) = \theta(n^{1 - \varepsilon})\).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Area requirement of graph drawings with few crossings per edge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391538)