Optimality and Complexity for Drawing Problems of Tree-Structured Diagrams
Kensei Tsuchida, Tadaaki Kirishima, Yasunori Shiono, Chieko Kato, Futoshi Sugimoto, Takeo Yaku · 2013
We investigated sets of conditions with respect to narrower drawing of tree-structured diagrams on an integral lattice. We found that under certain sets of conditions there are practical procedural algorithms for narrower drawing of tree-structured diagrams, while under other sets of conditions there are none. Based on our findings, we presented efficient algorithms that provide narrower placement satisfying given amorphous conditions. In this paper we review our these previous results regarding with sets of constraints for tidily drawing TSDs, efficient algorithms which produce minimum width drawings of TSDs while satisfying certain constraints and NP-completeness of drawing problems of TSDs. Then we discuss the relation among constraints and the optimality with respect to the widths of drawing TSDs. Finally we indicate a key constraint which is not only for obtaining the optimality but also for the practical uses.