More Compact Orthogonal Drawings by Allowing Additional Bends †

Information

Petra Mutzel¹  Christiane Spisla¹  Michael Jünger² 

[1] Department of Computer Science, TU Dortmund University, 44221 Dortmund, Germany;Department of Mathematics and Computer Science, University of Cologne, 50923 Cologne, Germany;

关键词: orthogonal compaction;    graph drawing;    total edge length;    Bends;    flow-based compaction;   

DOI  :  10.3390/info9070153

来源: DOAJ

【 摘 要 】

Compacting orthogonal drawings is a challenging task. Usually, algorithms try to compute drawings with small area or total edge length while preserving the underlying orthogonal shape. We suggest a moderate relaxation of the orthogonal compaction problem, namely the one-dimensional monotone flexible edge compaction problem with fixed vertex star geometry. We further show that this problem can be solved in polynomial time using a network flow model. An experimental evaluation shows that by allowing additional bends could reduce the total edge length and the drawing area.

【 授权许可】

Unknown