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

optimization problemsVLSI circuitspage numberfault-tolerant computingbook embeddingsarrays of processors

Mathematics Subject Classification ID

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) Graph theory (05C99)

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

• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• A Set of Topological Invariants for Graphs
• A framework for solving VLSI graph layout problems
• Characterizations of outerplanar graphs
• Graphs That are Almost Binary Trees
• 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 Complexity of Coloring Circular Arcs and Chords
• The book thickness of a graph

Cited in

(only showing first 100 items - show all)

• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Drawing partial 2-trees with few slopes
• On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page
• Geometric thickness in a grid
• Succinct Representation of Labeled Graphs
• Untangling circular drawings: algorithms and complexity
• Embedding planar 5-graphs in three pages
• Local and union page numbers
• A \((2k + 1)\)-regular graph with page-number \(k\)
• scientific article; zbMATH DE number 51713 (Why is no real title available?)
• Matching book thickness of generalized Petersen graphs
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• The pagenumber of \(k\)-trees is \(O(k)\)
• The outerplanar crossing number of the complete bipartite graph
• On book crossing numbers of the complete graph
• On the page number of upward planar directed acyclic graphs
• On Posets of Page Number 2
• On the pagenumber of trivalent Cayley graphs
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• scientific article; zbMATH DE number 4002118 (Why is no real title available?)
• On 3-coloring circle graphs
• Book drawings of complete bipartite graphs
• Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
• Boolean approaches to graph embeddings related to VLSI
• Universality considerations in VLSI circuits
• Mixed linear layouts: complexity, heuristics, and experiments
• Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
• A survey on book-embedding of planar graphs
• On 3-pushdown graphs with large separators
• Book embeddings and crossing numbers
• Stack and queue number of 2-trees
• A trade-off between page number and page width of book embeddings of graphs
• Optimal book embeddings of the FFT, Benes, and barrel shifter networks
• Characterizations of deque and queue graphs
• Embedding generalized Petersen graph in books
• Two-page book embeddings of 4-planar graphs
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• On the upward book thickness problem: combinatorial and complexity results
• Book embeddings of regular graphs
• The book thickness of nilpotent graphs
• Catalan, Motzkin, and Riordan numbers
• The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
• Parameterized algorithms for book embedding problems
• A survey on book-embedding of planar graphs
• The pagenumber of the class of bandwidth-k graphs is k-1
• Approximating the fixed linear crossing number
• Succinct representation of labeled graphs
• Linear layouts of bipartite planar graphs
• scientific article; zbMATH DE number 3980512 (Why is no real title available?)
• Upward book embeddings of st-graphs
• Classification of book representations of \(K_6\)
• On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
• The longest common subsequence problem for sequences with nested arc annotations.
• Embedding connected double-loop networks with even cardinality in books
• Embedding the incomplete hypercube in books
• Efficient deterministic algorithms for embedding graphs on books
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
• Book embedding of graphs on the projective plane
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Stack-number is not bounded by queue-number
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• An analysis of some linear graph layout heuristics
• 1-bend upward planar slope number of SP-digraphs
• Book embedding of locally planar graphs on orientable surfaces
• On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
• Parameterized algorithms for book embedding problems
• A framework for solving VLSI graph layout problems
• Optimum embedding of complete graphs in books
• The pagenumber of toroidal graphs is at most seven
• Improved book-embeddings of incomplete hypercubes
• scientific article; zbMATH DE number 951476 (Why is no real title available?)
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• On the pagenumber of the cube-connected cycles
• An improved fixed-parameter algorithm for one-page crossing minimization
• The pagewidth of trivalent planar graphs
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Embedding de Bruijn, Kautz and shuffle-exchange networks in books
• 1-page and 2-page drawings with bounded number of crossings per edge
• Embedding Outerplanar Graphs in Small Books
• \(k\)-spine, 1-bend planarity
• On 3-coloring circle graphs
• Recognizing geometric intersection graphs stabbed by a line
• Algorithms for the fixed linear crossing number problem
• Parameterized analysis and crossing minimization problems
• Upward partitioned book embeddings
• On Page Number of N-free Posets
• Routing with critical paths
• Ordered sets, pagenumbers and planarity
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• An annotated bibliography on 1-planarity
• scientific article; zbMATH DE number 3914339 (Why is no real title available?)
• Graph separators, with applications
• The bipartite-cylindrical crossing number of the complete bipartite graph
• The least eigenvalues of integral circulant graphs
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• The matching book embeddings of pseudo-Halin graphs
• Book thickness of the non-zero component union graph of the finite dimensional vector space
• Ramsey numbers of ordered graphs

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)