Geodesic
Data Structures and their Planar Graph Layouts
Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 207-237.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In a stack layout, also known as book embedding, the vertices of a graph are placed on a line and an edge is a data item that is pushed on the stack at the left vertex and removed at the right vertex. The LIFO principle of the stack is represented by a rainbow of nesting edges. We introduce linear cylindric drawings for the representation of the working principles of fundamental data structures including stack, queue, double-stack and deque. The resulting graphs are called stack (queue, double-stack, deque) graphs. We characterize the feasibility of a sequence of insertions and removals by planarity and use the graph classes to compare the relative power of these data structures. In particular, we show that the deque graphs are the linear cylindric planar graphs and are the subgraphs of the planar graphs with a Hamiltonian path. In comparison, the double-stack graphs are the graphs with a linear layout in the plane and are known as the subgraphs of the planar graphs with a Hamiltonian cycle. Hence, the power of the queue mode of a deque is expressed both by the differences between Hamiltonian path and Hamiltonian cycle and by linear layouts on the cylinder and in the plane. It is also reflected in the dual graph. Linear cylindric drawings provide an intuitive planar representation of the FIFO principle of a queue. We show that a queue graph augmented by a Hamiltonian path has a dual of the same type and that the dual has an Eulerian path. Finally, we study recognition problems. 
@article{JGAA_2018_22_2_a3,
     author = {Christopher Auer and Christian Bachmaier and Franz Brandenburg and Wolfgang Brunner and Andreas Glei{\ss}ner},
     title = {Data {Structures} and their {Planar} {Graph} {Layouts}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {207--237},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2018},
     doi = {10.7155/jgaa.00465},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00465/}
}
TY  - JOUR
AU  - Christopher Auer
AU  - Christian Bachmaier
AU  - Franz Brandenburg
AU  - Wolfgang Brunner
AU  - Andreas Gleißner
TI  - Data Structures and their Planar Graph Layouts
JO  - Journal of Graph Algorithms and Applications
PY  - 2018
SP  - 207
EP  - 237
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00465/
DO  - 10.7155/jgaa.00465
LA  - en
ID  - JGAA_2018_22_2_a3
ER  - 
%0 Journal Article
%A Christopher Auer
%A Christian Bachmaier
%A Franz Brandenburg
%A Wolfgang Brunner
%A Andreas Gleißner
%T Data Structures and their Planar Graph Layouts
%J Journal of Graph Algorithms and Applications
%D 2018
%P 207-237
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00465/
%R 10.7155/jgaa.00465
%G en
%F JGAA_2018_22_2_a3
Christopher Auer; Christian Bachmaier; Franz Brandenburg; Wolfgang Brunner; Andreas Gleißner. Data Structures and their Planar Graph Layouts. Journal of Graph Algorithms and Applications, Tome 22 (2018) no. 2, pp. 207-237. doi : 10.7155/jgaa.00465. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00465/

Cité par Sources :