{"id":13091,"date":"2021-12-05T21:01:44","date_gmt":"2021-12-06T02:01:44","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13091"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-03-08-stacks-queues-and-tracks-layouts-of-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2003\/tr-03-08-stacks-queues-and-tracks-layouts-of-graphs\/","title":{"rendered":"TR-03-08: Stacks, Queues and Tracks: Layouts of Graphs"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-03-08: Stacks, Queues and Tracks: Layouts of Graphs\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-03-08
\nOctober 2003<\/p>\n\n\n\n

Stacks, Queues and Tracks: Layouts of Graphs<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
Vida Dujmovic & David R. Wood<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

A k-stack layout (respectively, k -queue layout ) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering. A k -track layout of a graph consists of a vertex k -colouring, and a total order of each vertex colour class, such that between each pair of colour classes no two edges cross. The stack-number (respectively, queue-number , track-number ) of a graph G , denoted by sn ( G ) ( qn ( G ) , tn ( G ) ), is the minimum k such that G has a k -stack ( k -queue, k -track) layout. This paper studies stack, queue, and track layouts of graph subdivisions. It is known that every graph has a 3 -stack subdivision. The best known upper bound on the number of division vertices per edge in a 3 -stack subdivision of an n -vertex graph G is improved from O (log n ) to O (log min { sn ( G ) , qn ( G ) } ) . This result reduces the question of whether queue-number is bounded by stack-number to whether 3 -stack graphs have bounded queue number. It is proved that every graph has a 2 -queue subdivision, a 4 -track subdivision, and a mixed 1 – stack 1 -queue subdivision. All these values are optimal for every non-planar graph. In addition, we characterise those graphs with k -stack, k -queue, and k -track subdivisions, for all values of k . The number of division vertices per edge in the case of 2 -queue and 4 -track subdivisions, namely O (log qn ( G )) , is optimal to within a constant factor, for every graph G . The relationship between queue layouts and so-called 2 -track thickness of bipartite graphs is investigated, and 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.<\/p>\n\n\n\n

TR-03-08.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-03-08 October 2003 Stacks, Queues and Tracks: Layouts of Graphs Vida Dujmovic & David R. Wood Abstract A k-stack layout (respectively, k -queue layout ) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12314,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13091","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13091","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13091"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13091\/revisions"}],"predecessor-version":[{"id":13092,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13091\/revisions\/13092"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12314"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13091"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13091"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}