Plane Drawings of Queue and Deque Graphs
Plane Drawings of Queue and Deque Graphs
复制标题
队列和双端队列图的平面图
DOI：
10.1007/978-3-642-18469-7_7
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Gleißner
中科院分区：
文献类型：
--
作者：
C. Auer;C. Bachmaier;F. J. Brandenburg;W. Brunner;A. Gleißner
在堆栈和队列布局中，图的顶点从左到右线性排序，其中每个边对应于一个项，并且每个边的左端和右端顶点表示向所使用的数据结构添加和移除项。允许堆栈或队列布局的图分别是堆栈图或队列图。典型的堆栈和队列布局分别是彩虹和扭曲，分别体现了LIFO和FIFO原则。然而，在这样的可视化中，扭曲导致许多交叉，这使得附图难以理解。我们引入线性圆柱布局作为队列和双端队列（双端队列）图的可视化技术。它为这些基本数据结构的特征提供了新的见解，并扩展到具有堆栈和队列的混合布局的可视化。我们的主要结果是：一个图是双端图当且仅当它有一个平面线性柱面图。
In stack and queue layouts the vertices of a graph are linearly ordered from left to right, where each edge corresponds to an item and the left and right end vertex of each edge represents the addition and removal of the item to the used data structure. A graph admitting a stack or queue layout is a stack or queue graph, respectively.Typical stack and queue layouts are rainbows and twists visualizing the LIFO and FIFO principles, respectively. However, in such visualizations, twists cause many crossings, which make the drawings incomprehensible. We introduce linear cylindric layouts as a visualization technique for queue and deque (double-ended queue) graphs. It provides new insights into the characteristics of these fundamental data structures and extends to the visualization of mixed layouts with stacks and queues. Our main result states that a graph is a deque graph if and only if it has a plane linear cylindric drawing.
登录
查看更多内容
有向无环图的堆栈和队列布局：第一部分
DOI：
--
发表时间：
1999
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Lenwood S. Heath;Sriram V. Pemmaraju;Ann N. Trenk
通讯作者：
Ann N. Trenk
使用队列布局图
DOI：
--
发表时间：
1992
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
L. Heath;A. Rosenberg
通讯作者：
A. Rosenberg
关于图的线性布局
影响因子：
0.7
作者：
V. Dujmović;D. Wood
通讯作者：
D. Wood
FST TCS 2002：软件技术和理论计算机科学基础
DOI：
--
发表时间：
2002
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
Manindra Agrawal;Anil Seth
通讯作者：
Anil Seth
DOI：
--
发表时间：
2001
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
D. Wood
通讯作者：
D. Wood