Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

DOI10.1137/0608002zbMath0617.68062OpenAlexW1967125711WikidataQ56689198 ScholiaQ56689198MaRDI QIDQ4727445

Arnold L. Rosenberg, Frank Thompson Leighton, Fan R. K. Chung

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608002

zbMATH Keywords

optimization problems VLSI circuits page number fault-tolerant computing book embeddings arrays of processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15)

Related Items

The longest common subsequence problem for sequences with nested arc annotations., Algorithms for the fixed linear crossing number problem, SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES, Embedding generalized Petersen graph in books, The book thickness of nilpotent graphs, Two-page book embeddings of 4-planar graphs, Book embedding of locally planar graphs on orientable surfaces, A survey on book-embedding of planar graphs, The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph, Optimal book embeddings of the FFT, Benes, and barrel shifter networks, Embedding complete multi-partite graphs into Cartesian product of paths and cycles, Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number, Stack-number is not bounded by queue-number, Fixed-parameter tractability for book drawing with bounded number of crossings per edge, Area requirement of graph drawings with few crossings per edge, The 2-page crossing number of \(K_{n}\), Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, The crossing number of twisted graphs, Matching book thickness of generalized Petersen graphs, A trade-off between page number and page width of book embeddings of graphs, The outerplanar crossing number of the complete bipartite graph, Embedding Outerplanar Graphs in Small Books, Embedding de Bruijn, Kautz and shuffle-exchange networks in books, The pagenumber of toroidal graphs is at most seven, Parameterized analysis and crossing minimization problems, Optimum embedding of complete graphs in books, An annotated bibliography on 1-planarity, 1-page and 2-page drawings with bounded number of crossings per edge, RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties, Embedding planar 5-graphs in three pages, On the Page Number of Upward Planar Directed Acyclic Graphs, Upward book embeddability of \(st\)-graphs: complexity and algorithms, Book embeddings of \(k\)-framed graphs and \(k\)-map graphs, Stack and queue number of 2-trees, Book thickness of the non-zero component union graph of the finite dimensional vector space, Untangling circular drawings: algorithms and complexity, On the dispersability of odd toroidal grids, The matching book embeddings of pseudo-Halin graphs, Classification of book representations of K6, On the pagenumber of the cube-connected cycles, Succinct representation of labeled graphs, Linear layouts of bipartite planar graphs, Book embeddings and crossing numbers, Efficient deterministic algorithms for embedding graphs on books, Recognizing geometric intersection graphs stabbed by a line, Routing with critical paths, 1-bend upward planar slope number of SP-digraphs, Parameterized algorithms for book embedding problems, Local and union page numbers, Mixed linear layouts: complexity, heuristics, and experiments, Ordered sets, pagenumbers and planarity, Geometric thickness in a grid, Drawing partial 2-trees with few slopes, Book drawings of complete bipartite graphs, Orthogonal drawings of graphs for the automation of VLSI circuit design, Upward Partitioned Book Embeddings, Succinct Representation of Labeled Graphs, Parameterized Algorithms for Book Embedding Problems, Approximating the fixed linear crossing number, The pagenumber of the class of bandwidth-k graphs is \(k-1\), Extension of a theorem of Whitney, Ramsey numbers of ordered graphs, Deciding whether graph \(G\) has page number one is in NC, On the page number of RNA secondary structures with pseudoknots, The pagenumber of \(k\)-trees is \(O(k)\), An analysis of some linear graph layout heuristics, On the pagenumber of trivalent Cayley graphs, Structural properties of subdivided-line graphs, On dispersable book embeddings, The pagewidth of trivalent planar graphs, On 3-pushdown graphs with large separators, \(k\)-spine, 1-bend planarity, On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering, On fixed-order book thickness parameterized by the pathwidth of the vertex ordering, Unnamed Item, On the upward book thickness problem: combinatorial and complexity results, On the upward book thickness problem: combinatorial and complexity results, The bipartite-cylindrical crossing number of the complete bipartite graph, On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page, Upward Book Embeddings of st-Graphs, The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube, On the approximation of protein threading, Improved book-embeddings of incomplete hypercubes, Embedding connected double-loop networks with even cardinality in books, Characterizations of Deque and Queue Graphs, Book Embedding of Graphs on the Projective Plane, Embedding the incomplete hypercube in books, Catalan, Motzkin, and Riordan numbers, A \((2k + 1)\)-regular graph with page-number \(k\), Book Embeddings of Regular Graphs, Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph, On Posets of Page Number 2, On Page Number of N-free Posets, Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis, Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)

Cites Work