orderly spanning trees with applications to graph encoding and graph drawing
The canonical ordering for triconnected planar graphs is a powerful method for designing graph algorithms. This paper introduces the orderly pair of connected planar graphs, which extends the concept of canonical ordering to planar graphs not required to be triconnected. Let G be a connected planar graph. We give a linear-time algorithm that obtains an orderly pair ( H , T ) of G , where H is a planar embedding of G , and T is an orderly spanning tree of H . As applications, we show that the technique of orderly spanning trees yields (i) the best known encoding of G with query support, and (ii) the first area-optimal 2-visibility drawing of G .
order spanning tree applications graph encode graph drawing drawing planar graph method graph algorithms algorithm paper concept embedding query support optimality timing visibility