Planar Octilinear Drawings with One Bend Per Edge

Bekos, Michael A. and Gronemann, Martin and Kaufmann, Michael and Krug, Robert (2014) Planar Octilinear Drawings with One Bend Per Edge. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 331-342 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_28).

Full text not available from this repository.

Abstract

In octilinear drawings of planar graphs, every edge is drawn as an alternating sequence of horizontal, vertical and diagonal line-segments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A k-planar graph is a planar graph in which each vertex has degree less or equal to k. In particular, we prove that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size O(n 2) ×O(n). For 5-planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in super-polynomial area. However, for 6-planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_28
Classifications:G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.280 Canonical Ordering
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.540 Planar
P Styles > P.600 Poly-line
P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
ID Code:1444

Repository Staff Only: item control page

References

Bekos, M.A., Gronemann, M., Kaufmann, M., Krug, R.: Planar octilinear drawings with one bend per edge. Arxiv report arxiv.org/abs/1408.5920 (2014)

Biedl, T.C., Kant, G.: A better heuristic for orthogonal graph drawings. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 24–35. Springer, Heidelberg (1994)

Bläsius, T., Krug, M., Rutter, I., Wagner, D.: Orthogonal graph drawing with flexibility constraints. Algorithmica 68(4), 859–885 (2014)

Bodlaender, H.L., Tel, G.: A note on rectilinearity and angular resolution. Journal of Graph Algorithms and Applications 8(1), 89–94 (2004)

Di Battista, G., Tamassia, R.: On-line graph algorithms with SPQR-trees. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 598–611. Springer, Heidelberg (1990)

Di Giacomo, E., Liotta, G., Montecchiani, F.: The planar slope number of subcubic graphs. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 132–143. Springer, Heidelberg (2014)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing 31(2), 601–625 (2001)

Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Hong, S.H., Merrick, D., do Nascimento, H.A.D.: Automatic visualisation of metro maps. Journal of Visual Languages and Computing 17(3), 203–224 (2006)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesar, M., Vyskocil, T.: The planar slope number of planar partial 3-trees of bounded degree. Graphs and Combinatorics 29(4), 981–1005 (2013)

Kant, G.: Drawing planar graphs using the lmc-ordering. In: 33rd Annual Symposium on Foundations of Computer Science (FOCS 1992), pp. 101–110. IEEE (1992)

Kant, G.: Hexagonal grid drawings. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 263–276. Springer, Heidelberg (1993)

Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing planar graphs of bounded degree with few slopes. SIAM Journal of Discrete Mathematics 27(2), 1171–1183 (2013)

Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Drawing cubic graphs with at most five slopes. Computational Geometry 40(2), 138–147 (2008)

Lenhart, W., Liotta, G., Mondal, D., Nishat, R.I.: Planar and plane slope number of partial 2-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 412–423. Springer, Heidelberg (2013)

Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 254–265. Springer, Heidelberg (2011)

Nöllenburg, M.: Automated drawings of metro maps. Tech. Rep. 2005-25, Fakultät für Informatik, Universität Karlsruhe (2005)

Nöllenburg, M., Wolff, A.: Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Visualization and Computer Graphics 17(5), 626–641 (2011)

Stott, J.M., Rodgers, P., Martinez-Ovando, J.C., Walker, S.G.: Automatic metro map layout using multicriteria optimization. IEEE Transactions on Visualization and Computer Graphics 17(1), 101–114 (2011)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal of Computing 16(3), 421–444 (1987)

Wolff, A.: Graph drawing and cartography. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, ch. 23, pp. 697–736. CRC Press (2013)