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 , pp. 92-104(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_9).

Full text not available from this repository.


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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1197

Actions (login required)

View Item View Item