Straight-line monotone grid drawings of series-parallel graphs. (English) Zbl 1331.68153
Summary: A monotone drawing of a planar graph \(G\) is a planar straight-line drawing of \(G\) where a monotone path exists between every pair of vertices of \(G\) in some direction. Recently monotone drawings of graphs have been discovered as a new standard for visualizing graphs. In this paper we study monotone drawings of series-parallel graphs in a variable embedding setting. We show that a series-parallel graph of \(n\) vertices has a straight-line planar monotone drawing on a grid of size \(O(n) \times O(n^{2})\) and such a drawing can be found in linear time.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | DOI: 10.7155/jgaa.00249 · Zbl 1234.68321 · doi:10.7155/jgaa.00249 |
| [2] | Di Battista G., Graph Drawing: Algorithms for the Visualization of Graphs (1999) · Zbl 1057.68653 |
| [3] | DOI: 10.1016/0304-3975(88)90123-5 · Zbl 0678.68059 · doi:10.1016/0304-3975(88)90123-5 |
| [4] | DOI: 10.1007/s004539900017 · Zbl 0843.68088 · doi:10.1007/s004539900017 |
| [5] | DOI: 10.1007/PL00009264 · Zbl 0921.68063 · doi:10.1007/PL00009264 |
| [6] | DOI: 10.1016/S0012-365X(03)00059-1 · Zbl 1027.05042 · doi:10.1016/S0012-365X(03)00059-1 |
| [7] | DOI: 10.1142/5648 · doi:10.1142/5648 |
| [8] | Tamassia R., Discrete Mathematics and Its Applications, in: Handbook of Graph Drawing and Visualization (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
