Layouts of Graph SubdivisionsDujmović, Vida and Wood, David R. (2004) Layouts of Graph Subdivisions. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 133143(Official URL: http://dx.doi.org/10.1007/9783540318439_15). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_15
AbstractA kstack layout (respectively, kqueue layout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of noncrossing (nonnested) edges with respect to the vertex ordering. A ktrack layout of a graph consists of a vertex kcolouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The stacknumber (respectively, queuenumber, tracknumber) of a graph G, denoted by sn (G) (qn(G), tn(G) is the minimum k such that G has a kstack (kqueue, ktrack) layout. This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3stack subdivision. The best known upper bound on the number of division vertices per edge in a 3stack subdivision of an nvertex graph G is improved from O(log n) to O(log min{sn(G), qn(G)}). This result reduces the question of whether queuenumber is bounded by stacknumber to whether 3stack graphs have bounded queue number. It is proved that every graph has a 2queue subdivision, a 4track subdivision, and a mixed 1stack 1queue subdivision. All these values are optimal for every nonplanar graph. In addition, we characterise those graphs with kstack, kqueue, and ktrack subdivisions, for all values of k. The number of division vertices per edge in the case of 2queue and 4track subdivisions, namely 0(log qn(G)), is optimal to within a constant factor, for every graph G. Applications to 3D polyline grid drawings are presented. For example, it is proved that every graph G has a 3D polyline grid drawing with the vertices on a rectangular prism, and with O(log qn(G)) bends per edge. Research supported by NSERC and COMBSTRU.
Actions (login required)
