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

DOI10.1137/0608002MaRDI QIDQ4727445zbMATH OpenOpenAlexWikidataFDO

Authors Arnold L. Rosenberg, Fan Chung, F. Thomson Leighton

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

arrays of processorsbook embeddingsfault-tolerant computingoptimization problemspage numberVLSI circuits

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3914339
• scientific article; zbMATH DE number 1094182
• Optimum embedding of complete graphs in books
• Embedding Outerplanar Graphs in Small Books
• A framework for solving VLSI graph layout problems
• scientific article; zbMATH DE number 6902663
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• A survey on book-embedding of planar graphs
• A survey on book-embedding of planar graphs

Cites work

• A framework for solving VLSI graph layout problems
• A Set of Topological Invariants for Graphs
• Characterizations of outerplanar graphs
• Graphs That are Almost Binary Trees
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
• Optimal Rearrangeable Multistage Connecting Networks
• Single Row Routing
• Sorting Using Networks of Queues and Stacks
• The book thickness of a graph
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(only showing first 100 items - show all)

• Improved book-embeddings of incomplete hypercubes
• Embedding connected double-loop networks with even cardinality in books
• Embedding the incomplete hypercube in books
• Optimal book embeddings of the FFT, Benes, and barrel shifter networks
• A trade-off between page number and page width of book embeddings of graphs
• Deciding whether graph \(G\) has page number one is in NC
• On the approximation of protein threading
• Catalan, Motzkin, and Riordan numbers
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Embedding de Bruijn, Kautz and shuffle-exchange networks in books
• The pagenumber of toroidal graphs is at most seven
• Optimum embedding of complete graphs in books
• Geometric thickness in a grid
• Boolean approaches to graph embeddings related to VLSI
• Algorithms for the fixed linear crossing number problem
• The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
• 1-page and 2-page drawings with bounded number of crossings per edge
• The longest common subsequence problem for sequences with nested arc annotations.
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Structural properties of subdivided-line graphs
• 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
• A (2k + 1)-regular graph with page-number k
• 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
• The book thickness of nilpotent graphs
• A survey on book-embedding of planar graphs
• 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
• The crossing number of twisted graphs
• The outerplanar crossing number of the complete bipartite graph
• Parameterized analysis and crossing minimization problems
• Embedding planar 5-graphs in three pages
• 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
• The pagewidth of trivalent planar graphs
• On 3-pushdown graphs with large separators
• 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
• Area requirement of graph drawings with few crossings per edge
• The 2-page crossing number of \(K_{n}\)
• An annotated bibliography on 1-planarity
• Succinct representation of labeled graphs
• Book drawings of complete bipartite graphs
• Approximating the fixed linear crossing number
• Extension of a theorem of Whitney
• An analysis of some linear graph layout heuristics
• On the pagenumber of trivalent Cayley graphs
• \(k\)-spine, 1-bend planarity
• Book embedding of locally planar graphs on orientable surfaces
• Drawing partial 2-trees with few slopes
• Graph separators, with applications
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Embedding generalized Petersen graph in books
• Two-page book embeddings of 4-planar graphs
• Characterizations of deque and queue graphs
• On the page number of upward planar directed acyclic graphs
• On Posets of Page Number 2
• On Page Number of N-free Posets
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• scientific article; zbMATH DE number 3914339 (Why is no real title available?)
• scientific article; zbMATH DE number 3980512 (Why is no real title available?)
• Embedding Outerplanar Graphs in Small Books
• scientific article; zbMATH DE number 4002118 (Why is no real title available?)
• Universality considerations in VLSI circuits
• scientific article; zbMATH DE number 51713 (Why is no real title available?)
• scientific article; zbMATH DE number 1094182 (Why is no real title available?)
• Classification of book representations of K₆
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• Upward partitioned book embeddings
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• One-Page Book Embedding under Vertex-Neighborhood Constraints
• scientific article; zbMATH DE number 951476 (Why is no real title available?)
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Matching book thickness of generalized Petersen graphs
• Upward book embeddings of st-graphs
• An improved fixed-parameter algorithm for one-page crossing minimization
• A survey on book-embedding of planar graphs
• Parameterized algorithms for book embedding problems
• Book embedding of graphs on the projective plane
• Book embeddings of regular graphs
• Succinct Representation of Labeled Graphs
• On the upward book thickness problem: combinatorial and complexity results
• Ramsey numbers of ordered graphs
• On the upward book thickness problem: combinatorial and complexity results
• The pagenumber of k-trees is O(k)
• 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
• 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

This page was built for publication: Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4727445)