A. A. Ageev, A triangle-free circle graph with chromatic number 5, Discrete Mathematics, vol.152, issue.1-3, pp.295-298, 1996.
DOI : 10.1016/0012-365X(95)00349-2

M. Alzohairi-and-i and . Rival, Series-parallel planar ordered sets have pagenumber two, Proc. 4th International Symp. on Graph Drawing (GD '96), pp.11-24, 1997.
DOI : 10.1007/3-540-62495-3_34

M. Alzohairi, I. Rival, and A. A. Kostochka, The pagenumber of spherical lattices is unbounded, Arab J. Math. Sci, vol.7, issue.1, pp.79-82, 2001.

F. R. Bernhart and P. C. Kainen, The book thickness of a graph, Journal of Combinatorial Theory, Series B, vol.27, issue.3, pp.320-331, 1979.
DOI : 10.1016/0095-8956(79)90021-2

S. N. Bhatt, F. R. Chung, F. T. Leighton, and A. A. Rosenberg, Scheduling Tree-Dags Using FIFO Queues: A Control???Memory Trade-Off, Journal of Parallel and Distributed Computing, vol.33, issue.1, pp.55-68, 1996.
DOI : 10.1006/jpdc.1996.0024

T. C. Biedl, T. Shermer, S. Whitesides, and A. S. Wismath, Bounds For Orthogonal 3-D Graph Drawing, Journal of Graph Algorithms and Applications, vol.3, issue.4, pp.63-79, 1999.
DOI : 10.7155/jgaa.00018

T. Bilski, Embedding graphs in books with prespecified order of vertices, Studia Automat, vol.18, pp.5-12, 1993.

T. Bilski, Optimum embedding of complete graphs in books, Discrete Mathematics, vol.182, issue.1-3, pp.21-28, 1998.
DOI : 10.1016/S0012-365X(97)00131-3

R. Blankenship-and-b and . Oporowski, Drawing subdivisions of complete and complete bipartite graphs on books, 1999.

R. Blankenship-and-b and . Oporowski, Book embeddings of graphs and minor-closed classes, Proc. 32nd Southeastern International Conf. on Combinatorics, Graph Theory and Computing, 2001.

P. Bose, J. Czyzowicz, P. Morin, and A. D. Wood, The maximum number of edges in a three-dimensional grid-drawing, Proc. 19th European Workshop on Computational Geometry, pp.101-103, 2003.

J. Buss and P. Shor, On the pagenumber of planar graphs, Proceedings of the sixteenth annual ACM symposium on Theory of computing , STOC '84, pp.98-100, 1984.
DOI : 10.1145/800057.808670

J. F. Buss, A. L. Rosenberg, and A. J. Knott, Vertex Types in Book-Embeddings, SIAM Journal on Discrete Mathematics, vol.2, issue.2, pp.156-175, 1989.
DOI : 10.1137/0402015

Y. Chen, H. Fu, and A. Sun, A study of typenumber in book-embedding, Ars Combin, vol.62, pp.97-103, 2002.

F. R. Chung, F. T. Leighton, and A. A. Rosenberg, Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design, SIAM Journal on Algebraic Discrete Methods, vol.8, issue.1, pp.33-58, 1987.
DOI : 10.1137/0608002

G. A. Cottafava and O. D. Antona, Book-thickness and book-coarseness of graphs, Proc. 5th International Symp. on Network Theory, pp.337-340, 1984.

D. P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Mathematics, vol.30, issue.3, pp.289-293, 1980.
DOI : 10.1016/0012-365X(80)90236-8

E. Damiani, O. D. Antona, and A. P. Salemi, An upper bound to the crossing number of the complete graph drawn on the pages of a book, J. Combin. Inform. System Sci, vol.19, issue.12, pp.75-84, 1994.

H. De-fraysseix, P. Ossona, A. J. Mendez, and . Pach, A left-first search algorithm for planar graphs, Discrete & Computational Geometry, vol.55, issue.3-4, pp.3-4459, 1995.
DOI : 10.1007/BF02574056
URL : https://hal.archives-ouvertes.fr/hal-00005623

A. M. Dean and J. P. Hutchinson, Relations among embedding parameters for graphs, Graph theory, combinatorics, and applications, pp.287-296, 1991.

E. Di-giacomo, W. Didimo, G. Liotta, and A. S. Wismath, Book Embeddings and Point-Set Embeddings of Series-Parallel Digraphs, Proc. 10th International Symp. on Graph Drawing (GD '02), pp.162-173, 2002.
DOI : 10.1007/3-540-36151-0_16

E. Di-giacomo, W. Didimo, G. Liotta, and A. S. Wismath, Drawing Planar Graphs on a Curve, pp.192-204
DOI : 10.1007/978-3-540-39890-5_17

E. , D. Giacomo, and A. H. Meijer, Track drawings of graphs with constant queue number, Proc. 11th International Symp. on Graph Drawing (GD '03), pp.214-225, 2004.

R. P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, The Annals of Mathematics, vol.51, issue.1, pp.161-166, 1950.
DOI : 10.2307/1969503

V. Dujmovi´cdujmovi´-dujmovi´c, P. Morin, and A. D. Wood, Layout of graphs with bounded tree-width, 2002.

V. Dujmovi´cdujmovi´-dujmovi´c and A. D. Wood, Tree-partitions of k-trees with applications in graph layout, 2002.

V. Dujmovi´cdujmovi´-dujmovi´c and A. D. Wood, Stacks, queues and tracks: Layouts of graph subdivisions, 2003, submitted. See Tech, 2003.

V. Dujmovi´cdujmovi´-dujmovi´c and A. D. Wood, Track layouts of graphs, 2003, submitted. See Tech, 2003.

V. Dujmovi´cdujmovi´-dujmovi´c and A. D. Wood, Tree-partitions of k-trees with applications in graph layout, pp.205-217

B. Dushnik and E. W. Miller, Partially Ordered Sets, American Journal of Mathematics, vol.63, issue.3, pp.600-610, 1941.
DOI : 10.2307/2371374

T. Endo, The pagenumber of toroidal graphs is at most seven, Discrete Mathematics, vol.175, issue.1-3, pp.87-96, 1997.
DOI : 10.1016/S0012-365X(96)00144-6

H. Enomoto, T. Nakamigawa, and A. K. Ota, On the Pagenumber of Complete Bipartite Graphs, Journal of Combinatorial Theory, Series B, vol.71, issue.1, pp.111-120, 1997.
DOI : 10.1006/jctb.1997.1773

D. Eppstein, Separating geometric thickness from book thickness. arXiv.org:math, 2001.
DOI : 10.1007/3-540-36151-0_15
URL : http://arxiv.org/abs/math/0204252

S. A. Even and . Itai, QUEUES, STACKS AND GRAPHS, Proc. International Symp. on Theory of Machines and Computations, pp.71-86, 1971.
DOI : 10.1016/B978-0-12-417750-5.50011-7

H. Fu-and-i.-f and . Sun, The typenumber of trees, Discrete Math, vol.253, issue.1-3, pp.3-10, 2002.

Z. Galil, R. Kannan, and A. E. Szemerédiszemer´szemerédi, On 3-pushdown graphs with large separators, Combinatorica, vol.13, issue.No. 2, pp.9-19, 1989.
DOI : 10.1007/BF02122679

Z. Galil, R. Kannan, and A. E. Szemerédiszemer´szemerédi, On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape turing machines, Journal of Computer and System Sciences, vol.38, issue.1, pp.134-149, 1989.
DOI : 10.1016/0022-0000(89)90036-6

R. A. Games, Optimal book embeddings of the FFT, benes, and barrel shifter networks, Algorithmica, vol.20, issue.1-4, pp.233-250, 1986.
DOI : 10.1007/BF01840445

J. L. Ganley, Stack and queue layouts of Halin graphs, 1995.

J. L. Ganley and L. S. Heath, The pagenumber of k-trees is O(k), Discrete Applied Mathematics, vol.109, issue.3, pp.215-221, 2001.
DOI : 10.1016/S0166-218X(00)00178-5

M. R. Garey, D. S. Johnson, G. L. Miller, and A. C. Papadimitriou, The Complexity of Coloring Circular Arcs and Chords, SIAM Journal on Algebraic Discrete Methods, vol.1, issue.2, pp.216-227, 1980.
DOI : 10.1137/0601025

M. R. Garey, D. S. Johnson, and A. L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science, vol.1, issue.3, pp.237-267, 1976.
DOI : 10.1016/0304-3975(76)90059-1
URL : http://doi.org/10.1016/0304-3975(76)90059-1

C. Gavoille, N. J. Hanusse, P. Wie-dermann, . Van-emde, A. M. Boas et al., Compact Routing Tables for Graphs of Bounded Genus (Extended Abstract), Proc. 26th International Colloquium on Automata, Languages and Programming (ICALP '99), pp.351-360, 1999.
DOI : 10.1007/3-540-48523-6_32

A. Gy´arf´asgy´ and . Gy´arf´as, On the chromatic number of multiple interval graphs and overlap graphs, Discrete Mathematics, vol.55, issue.2, pp.161-166, 1985.
DOI : 10.1016/0012-365X(85)90044-5

A. Gy´arf´asgy´ and C. Gy´arf´as, Corrigendum, Discrete Mathematics, vol.62, issue.3, p.333, 1986.
DOI : 10.1016/0012-365X(86)90224-4

A. Gy´arf´asgy´, . J. Gy´arf´as, and . Lehel, Covering and coloring problems for relatives of intervals, Discrete Mathematics, vol.55, issue.2, pp.167-180, 1985.
DOI : 10.1016/0012-365X(85)90045-7

T. Harju-and-l and . Ilie, Forbidden subsequences and permutations sortable on two parallel stacks, Where mathematics, computer science, linguistics and biology meet, pp.267-275, 2001.

T. Hasunuma, Embedding iterated line digraphs in books, Networks, vol.38, issue.2, pp.51-62, 2002.
DOI : 10.1002/net.10032

T. Y. Hasunuma, . Shibata, and . Embedding-de-bruijn, Embedding de Bruijn, Kautz and shuffle-exchange networks in books, Discrete Applied Mathematics, vol.78, issue.1-3, pp.103-116, 1997.
DOI : 10.1016/S0166-218X(97)00009-7

L. S. Heath, Embedding Planar Graphs In Seven Pages, 25th Annual Symposium onFoundations of Computer Science, 1984., pp.74-83, 1984.
DOI : 10.1109/SFCS.1984.715903

L. S. Heath, Embedding Outerplanar Graphs in Small Books, SIAM Journal on Algebraic Discrete Methods, vol.8, issue.2, pp.198-218, 1987.
DOI : 10.1137/0608018

L. S. Heath-and-s and . Istrail, The pagenumber of genus g graphs is O(g), Journal of the ACM, vol.39, issue.3, pp.479-501, 1992.
DOI : 10.1145/146637.146643

L. S. Heath, F. T. Leighton, and A. A. Rosenberg, Comparing Queues and Stacks As Machines for Laying Out Graphs, SIAM Journal on Discrete Mathematics, vol.5, issue.3, pp.398-412, 1992.
DOI : 10.1137/0405031

L. S. Heath and S. V. Pemmaraju, Stack and Queue Layouts of Posets, SIAM Journal on Discrete Mathematics, vol.10, issue.4, pp.599-625, 1997.
DOI : 10.1137/S0895480193252380

L. S. Heath and S. V. Pemmaraju, Stack and Queue Layouts of Directed Acyclic Graphs: Part I, SIAM Journal on Computing, vol.28, issue.4, pp.1588-1626, 1999.
DOI : 10.1137/S0097539795280287

L. S. Heath, S. V. Pemmaraju, and A. A. Trenk, Stack and Queue Layouts of Directed Acyclic Graphs: Part I, SIAM Journal on Computing, vol.28, issue.4, pp.1510-1539, 1999.
DOI : 10.1137/S0097539795280287

L. S. Heath and A. L. Rosenberg, Laying Out Graphs Using Queues, SIAM Journal on Computing, vol.21, issue.5, pp.927-958, 1992.
DOI : 10.1137/0221055

R. A. Hochberg and M. F. Stallmann, Optimal one-page tree embeddings in linear time, Information Processing Letters, vol.87, issue.2, pp.59-66, 2003.
DOI : 10.1016/S0020-0190(03)00261-8

A. A. Imamiya and . Nozaki, Generating and sorting permutations using restricted-deques, Information Processing in Japan, vol.17, pp.80-86, 1977.

M. Ishiwata, Book presentation of the complete n-partite graphs, Kobe J. Math, vol.13, issue.1, pp.27-48, 1996.

G. Jacobson, Space-efficient static trees and graphs, 30th Annual Symposium on Foundations of Computer Science, pp.549-554, 1989.
DOI : 10.1109/SFCS.1989.63533

P. C. Kainen, The book thickness of a graph. II, Proc. 20th Southeastern Conference on Combinatorics , Graph Theory, and Computing, pp.127-132, 1990.

P. C. Kainen-and-s and . Overbay, Book embeddings of graphs and a theorem of Whitney

R. Kannan, Unraveling k-page graphs, Information and Control, vol.66, issue.1-2, pp.1-5, 1985.
DOI : 10.1016/S0019-9958(85)80008-5
URL : http://doi.org/10.1016/s0019-9958(85)80008-5

N. Kapoor, M. Russell, I. Stojmenovic, and A. A. Zomaya, A Genetic Algorithm for Finding the Pagenumber of Interconnection Networks, Journal of Parallel and Distributed Computing, vol.62, issue.2, pp.267-283, 2002.
DOI : 10.1006/jpdc.2001.1789

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Communications, pp.85-103, 1972.
DOI : 10.1007/978-3-540-68279-0_8

C. D. Keys, Graphs critical for maximal bookthickness, Pi Mu Epsilon J, vol.6, pp.79-84, 1975.

K. Kobayashi, Book presentation and local unknottedness of spatial graphs, Kobe J. Math, vol.10, issue.2, pp.161-171, 1993.

A. J. Kostochka and . Kratochv´ilkratochv´il, Covering and coloring polygon-circle graphs, Discrete Mathematics, vol.163, issue.1-3, pp.299-305, 1997.
DOI : 10.1016/S0012-365X(96)00344-5

A. V. Kostochka, Upper bounds on the chromatic number of graphs, Trudy Inst. Mat, vol.10, pp.204-226, 1988.

Q. H. Le and . Tu, A planar poset which requires four pages, Ars Combin, vol.35, pp.291-302, 1993.

Y. Lin, Cutwidth and related parameters of graphs, J. Zhengzhou Univ. Nat. Sci. Ed, vol.34, issue.1, pp.1-5, 2002.

S. M. Malitz, Genus g Graphs Have Pagenumber O(???g), Journal of Algorithms, vol.17, issue.1, pp.85-109, 1994.
DOI : 10.1006/jagm.1994.1028

S. M. Malitz, Graphs with E Edges Have Pagenumber O(???E), Journal of Algorithms, vol.17, issue.1, pp.71-84, 1994.
DOI : 10.1006/jagm.1994.1027

S. Masuyama-and-s and . Naito, Deciding whether graph G has page number one is in NC, Information Processing Letters, vol.44, issue.1, pp.7-10, 1992.
DOI : 10.1016/0020-0190(92)90247-S

S. L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Information Processing Letters, vol.9, issue.5, pp.229-232, 1979.
DOI : 10.1016/0020-0190(79)90075-9

S. Moran and Y. Wolfstahl, One-Page Book Embedding under Vertex-Neighborhood Constraints, SIAM Journal on Discrete Mathematics, vol.3, issue.3, pp.376-390, 1990.
DOI : 10.1137/0403034

S. Moran and Y. Wolfsthal, Two-page book embedding of trees under vertex-neighborhood constraints, Discrete Applied Mathematics, vol.43, issue.3, pp.233-241, 1993.
DOI : 10.1016/0166-218X(93)90114-4

D. J. Muder, M. L. Weaver, and A. D. West, Pagenumber of complete bipartite graphs, Journal of Graph Theory, vol.1, issue.4, pp.469-489, 1988.
DOI : 10.1002/jgt.3190120403

J. I. Munro and V. Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, vol.31, issue.3, pp.762-776, 2001.
DOI : 10.1137/S0097539799364092

R. A. Nowakowski and . Parker, Ordered sets, pagenumbers and planarity. Order, pp.209-218, 1989.
DOI : 10.1007/bf00563521

B. Obreni´cobreni´ and . Obreni´c, Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages, SIAM Journal on Discrete Mathematics, vol.6, issue.4, pp.642-654, 1993.
DOI : 10.1137/0406049

L. T. Ollmann, On the book thicknesses of various graphs, Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, p.459, 1973.

E. T. Ordman and . Schmitt, Permutations using stacks and queues, Proc. of 24th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, pp.57-64, 1993.

S. V. Pemmaraju, Exploring the Powers of Stacks and Queues via Graph Layouts, 1992.

V. R. Pratt, Computing permutations with double-ended queues, parallel stacks and parallel queues, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.268-277, 1973.
DOI : 10.1145/800125.804058

H. J. Pr¨omelpr¨-pr¨omel, T. Schickinger, and A. A. Steger, A note on triangle-free and bipartite graphs, Discrete Mathematics, vol.257, issue.2-3, pp.531-540, 2002.
DOI : 10.1016/S0012-365X(02)00511-3

S. Rengarajan, C. E. Veni, and . Madhavan, Stack and queue number of 2-trees, Proc. 1st Annual International Conf. on Computing and Combinatorics (COCOON '95), pp.203-212, 1995.
DOI : 10.1007/BFb0030834

A. L. Rosenberg, The Diogenes Approach to Testable Fault-Tolerant Arrays of Processors, IEEE Transactions on Computers, vol.32, issue.10, pp.902-910, 1983.
DOI : 10.1109/TC.1983.1676134

A. L. Rosenberg, Book embeddings and wafer-scale integration, Proc. 17th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, pp.217-224, 1986.

A. L. Rosenberg and . Diogenes, Diogenes, circa 1986 ?????????? ?????? ?????? ????????o ????????o??o, Proc. VLSI Algorithms and Architectures, pp.96-107, 1986.
DOI : 10.1007/3-540-16766-8_9

F. W. Shahrokhi and . Shi, On Crossing Sets, Disjoint Sets, and Pagenumber, Journal of Algorithms, vol.34, issue.1, pp.40-53, 2000.
DOI : 10.1006/jagm.1999.1049
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.7483

F. Shahrokhi, L. A. Székelysz´székely, O. S. Ykora, A. I. V?, and . To, The book crossing number of a graph, Journal of Graph Theory, vol.21, issue.4, pp.413-424, 1996.
DOI : 10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5

E. St¨ohrst¨ and . St¨ohr, A trade-off between page number and page width of book embeddings of graphs, Information and Computation, vol.79, issue.2, pp.155-162, 1988.
DOI : 10.1016/0890-5401(88)90036-3

E. St¨ohrst¨ and . St¨ohr, Optimal book embeddings in depth-k K n -cylinders, J. Information Processing and Cybernetics EIK, p.26, 1990.

E. St¨ohrst¨ and . St¨ohr, The pagewidth of trivalent planar graphs, Discrete Mathematics, vol.89, issue.1, pp.43-49, 1991.
DOI : 10.1016/0012-365X(91)90398-L

R. P. Swaminathan, D. Giriraj, and A. D. Bhatia, The pagenumber of the class of bandwidth-k graphs is k ??? 1, Information Processing Letters, vol.55, issue.2, pp.71-74, 1995.
DOI : 10.1016/0020-0190(95)00079-R

M. M. Sys?o, Bounds to the page number of partially ordered sets, Proc. 15th International Workshop in Graph-Theoretic Concepts in Computer Science (WG '89), pp.181-195, 1990.
DOI : 10.1007/3-540-52292-1_13

R. Tarjan, Sorting Using Networks of Queues and Stacks, Journal of the ACM, vol.19, issue.2, pp.341-346, 1972.
DOI : 10.1145/321694.321704

M. Togasaki and K. Yamazaki, Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs, Discrete Mathematics, vol.259, issue.1-3, pp.361-368, 2002.
DOI : 10.1016/S0012-365X(02)00542-3

W. Unger, On the k-colouring of circle-graphs, Proc. 5th International Symp. on Theoretical Aspects of Computer Science (STACS '88), pp.61-72, 1988.
DOI : 10.1007/BFb0035832

W. Unger, The complexity of colouring circle graphs, Proc. 9th International Symp. on Theoretical Aspects of Computer Science (STACS '92), pp.389-400, 1992.
DOI : 10.1007/3-540-55210-3_199

M. J. Wang, Some results on embedding grid graphs in books, J. Zhengzhou Univ. Nat. Sci. Ed, vol.29, issue.2, pp.31-34, 1997.

A. Wigderson, The complexity of the Hamiltonian circuit problem for maximal planar graphs, 1982.

D. R. Wood, Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing, Proc. 9th International Symp. on Graph Drawing (GD '01), pp.312-327, 2002.
DOI : 10.1007/3-540-45848-4_25
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.525.2642

D. R. Wood, Degree constrained book embeddings, Journal of Algorithms, vol.45, issue.2, pp.144-154, 2002.
DOI : 10.1016/S0196-6774(02)00249-3
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.3006

D. R. Wood, Queue Layouts, Tree-Width, and Three-Dimensional Graph Drawing, Proc. 22nd Foundations of Software Technology and Theoretical Computer Science (FST TCS '02), pp.348-359, 2002.
DOI : 10.1007/3-540-36206-1_31
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4989

M. Yannakakis, Embedding planar graphs in four pages, Journal of Computer and System Sciences, vol.38, issue.1, pp.36-67, 1986.
DOI : 10.1016/0022-0000(89)90032-9