Orthogonal Graph Drawing with Flexibility Constraints

Bläsius, Thomas and Krug, Marcus and Rutter, Ignaz and Wagner, Dorothea (2011) Orthogonal Graph Drawing with Flexibility Constraints. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 92-104 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_9).

Full text not available from this repository.

Abstract

In this work we consider the following problem. Given a planar graph G with maximum degree 4 and a function flex E->N_o: that gives each edge a flexibility. Does G admit a planar embedding on the grid such that each edge e has at most flex(e) bends? Note that in our setting the combinatorial embedding of G is not fixed. We give a polynomial-time algorithm for this problem when the flexibility of each edge is positive. This includes as a special case the problem of deciding whether G admits a drawing with at most one bend per edge.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_9
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:1197

Repository Staff Only: item control page

References

Battista, G.D., Liotta, G., Vargiu, F.: Spirality and optimal orthogonal drawings. SIAM J. Comput. 27(6), 1764–1811 (1998)

Biedl, T., 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. Technical Report 2010-18, Faculty of Informatics, Karlsruhe Institute of Technology, KIT (2010), http://digbib.ubka.uni-karlsruhe.de/volltexte/1000019793

Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956–997 (1996)

Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 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)

Liu, Y., Marchioro, P., Petreschi, R., Simeone, B.: Theoretical results on at most 1-bend embeddability of graphs. Acta Math. Appl. Sinica (English Ser.) 8(2), 188–192 (1992)

Liu, Y., Morgana, A., Simeone, B.: A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid. Discr. Appl. Math. 81(1–3), 69–91 (1998)

Morgana, A., de Mello, C.P., Sontacchi, G.: An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid. Discr. Appl. Math. 141(1-3), 225–241 (2004)

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