Some Applications of Orderly Spanning Trees in Graph DrawingChen, HoLin and Liao, ChienChih and Lu, HsuehI. and Yen, HsuChun (2002) Some Applications of Orderly Spanning Trees in Graph Drawing. In: Graph Drawing 10th International Symposium, GD 2002, August 2628, 2002 , pp. 332343(Official URL: http://dx.doi.org/10.1007/3540361510_31). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540361510_31
AbstractOrderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by Fößmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with halfperimeter no more than {\left\lceil{\frac{3n}{2}}\right\rceil}+ 1 and at most one bend per edge for any nnode plane graph with maximal degree \Delta, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floorplan using only rectangles.
Actions (login required)
