Optimal Orthogonal Graph Drawing with Convex Bend Costs

Details Optimal Orthogonal Graph Drawing with Convex Bend Costs Optimal Orthogonal Graph Drawing with Convex Bend Costs

2012-04-23

arxiv.org/abs/1204.4997v1

Computer Science

Data Structures and Algorithms

31 pages, 14 figures

Scientific paper

Traditionally, the quality of orthogonal planar drawings is quantified by either the total number of bends, or the maximum number of bends per edge. However, this neglects that in typical applications, edges have varying importance. Moreover, as bend minimization over all planar embeddings is NP-hard, most approaches focus on a fixed planar embedding. We consider the problem OptimalFlexDraw that is defined as follows. Given a planar graph G on n vertices with maximum degree 4 and for each edge e a cost function cost_e : N_0 --> R defining costs depending on the number of bends on e, compute an orthogonal drawing of G of minimum cost. Note that this optimizes over all planar embeddings of the input graphs, and the cost functions allow fine-grained control on the bends of edges. In this generality OptimalFlexDraw is NP-hard. We show that it can be solved efficiently if 1) the cost function of each edge is convex and 2) the first bend on each edge does not cause any cost (which is a condition similar to the positive flexibility for the decision problem FlexDraw). Moreover, we show the existence of an optimal solution with at most three bends per edge except for a single edge per block (maximal biconnected component) with up to four bends. For biconnected graphs we obtain a running time of O(n T_flow(n)), where T_flow(n) denotes the time necessary to compute a minimum-cost flow in a planar flow network with multiple sources and sinks. For connected graphs that are not biconnected we need an additional factor of O(n).

Affiliated with

Also associated with

No associations

Rating

Optimal Orthogonal Graph Drawing with Convex Bend Costs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Orthogonal Graph Drawing with Convex Bend Costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Orthogonal Graph Drawing with Convex Bend Costs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-443651