Results 1 to 10 of about 9,877,117 (330)
Three-Dimensional Graph Products with Unbounded Stack-Number [PDF]
Discrete & Computational Geometry, 2023 We prove that the stack-number of the strong product of three $n$-vertex paths is $Θ(n^{1/3})$. The best previously known upper bound was $O(n)$. No non-trivial lower bound was known. This is the first explicit example of a graph family with bounded maximum degree and unbounded stack-number.
David Eppstein +5 more
semanticscholar +9 more sources
Stack-Number is Not Bounded by Queue-Number [PDF]
Combinatorica, 2021 We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
David R. Wood +4 more
semanticscholar +6 more sources
On Families of Planar DAGs with Constant Stack Number
International Symposium Graph Drawing and Network Visualization, 2023 A $k$-stack layout (or $k$-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into $k$ sets of non-crossing edges with respect to the vertex order. The stack number of a graph is the minimum $k$ such that it admits a $k$-stack layout. In this paper we study a long-standing problem regarding the stack
Martin Nöllenburg, Sergey Pupyrev
semanticscholar +6 more sources
Directed Acyclic Outerplanar Graphs Have Constant Stack Number [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2022 The stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering.
Jungeblut, Paul +2 more
semanticscholar +6 more sources
STACK NUMBER INFLUENCE ON THE ACCURACY OF ASTER GDEM (V2) [PDF]
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2017 In this research, the influence of stack number (STKN) on the accuracy of Advanced Spaceborne Thermal Emission and Reflection Radiometer (ASTER) Global DEM (GDEM) has been investigated. For this purpose, two data sets of ASTER and Reference DEMs from two
S. M. J. Mirzadeh +2 more
doaj +5 more sources
Stack number and queue number of graphs [PDF]
arXiv.org, 2023 In this paper we give an overview of the graph invariants queue number and stack number (the latter also called the page number or book thickness). Due to their similarity, it has been studied for a long time, whether one of them is bounded in terms of the other. It is now known that the stack number is not bounded by the queue number.
Adam Straka
openaire +3 more sources
Discrete Mathematics & Theoretical Computer Science, 2004 A \emph(k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross.
Vida Dujmović +2 more
doaj +8 more sources
Stacks, Queues and Tracks: Layouts of Graph Subdivisions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A \emphk-stack layout (respectively, \emphk-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 +3 more sources
Pop-stack-sorting for Coxeter groups [PDF]
Combinatorial Theory, 2021 Let $W$ be an irreducible Coxeter group. We define the Coxeter pop-stack-sorting operator $\mathsf{Pop}:W\to W$ to be the map that fixes the identity element and sends each nonidentity element $w$ to the meet of the elements covered by $w$ in the right ...
Colin Defant
semanticscholar +1 more source
On Linear Layouts of Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2004 In a total order of the vertices of a graph, two edges with no endpoint in common can be \emphcrossing, \emphnested, or \emphdisjoint. A \emphk-stack (respectively, \emphk-queue, \emphk-arch) \emphlayout of a graph consists of a total order of the ...
Vida Dujmović, David R. Wood
doaj +1 more source