Results 1 to 10 of about 1,396 (174)
Stacks, Queues and Tracks: Layouts of Graph Subdivisions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A k-stack layout (respectively, k-queuelayout) 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.
Vida Dujmović, David R. Wood
doaj +8 more sources
Queue Layouts of Graph Products and Powers [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A \emphk-queue layout of a graph G consists of a linear order σ of V(G), and a partition of E(G) into k sets, each of which contains no two edges that are nested in σ .
David R. Wood
doaj +8 more sources
Parameterized Algorithms for Queue Layouts [PDF]
Journal of Graph Algorithms and Applications, 2022 An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ sets, called queues, such that no two independent edges of the same queue nest. The minimum $h$ such that $G$ admits an $h$-queue layout is the queue number of $G$.
Sujoy Bhore +3 more
openalex +5 more sources
Lazy Queue Layouts of Posets [PDF]
Algorithmica, 2022 AbstractWe investigate the queue number of posets in terms of their width, that is, the maximum number of pairwise incomparable elements. A long-standing conjecture of Heath and Pemmaraju asserts that every poset of width w has queue number at most w. The conjecture has been confirmed for posets of width $$w=2$$ w
Jawaherul Md. Alam +4 more
openalex +5 more sources
Queue Layouts of Planar 3-Trees [PDF]
Algorithmica, 2020 AbstractA queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are nested. The queue number of graph G is defined as the minimum number of queues required by any queue layout of G.
Jawaherul Md. Alam +4 more
openalex +5 more sources
Stack and Queue Layouts via Layered Separators [PDF]
Journal of Graph Algorithms and Applications, 2017 It is known that every proper minor-closed class of graphs has bounded stack-number (a.k.a. book thickness and page number). While this includes notable graph families such as planar graphs and graphs of bounded genus, many other graph families are not closed under taking minors.
Vida Dujmović, Fabrizio Frati
openalex +6 more sources
Stack and Queue Layouts of Posets [PDF]
SIAM Journal on Discrete Mathematics, 1997 Summary: The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph.
Lenwood S. Heath, Sriram V. Pemmaraju
openalex +4 more sources
Queue Layouts of Two-Dimensional Posets
, 2022 Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)
Sergey Pupyrev
openalex +4 more sources
Queue layouts and nonrepetitive colouring of planar graphs and powers of trees
, 2021 There are some mistakes in the proof of Theorem 2.2, this leads to the fact that some major results are ...
Jiaqi Wang, Daqing Yang
openalex +4 more sources
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs [PDF]
Some of the most important open problems for linear layouts of graphs ask for the relation between a graph's queue number and its stack number or mixed number. In such, we seek a vertex order and edge partition of $G$ into parts with pairwise non-crossing edges (a stack) or with pairwise non-nesting edges (a queue).
Julia Katheder +3 more
+9 more sources