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

DOI10.1137/0608002zbMATH Open0617.68062OpenAlexW1967125711WikidataQ56689198 ScholiaQ56689198MaRDI QIDQ4727445FDOQ4727445

F. Thomson Leighton, Arnold L. Rosenberg, Fan 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 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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• The outerplanar crossing number of the complete bipartite graph
• On the pagenumber of trivalent Cayley graphs
• Parameterized Algorithms for Book Embedding Problems
• SIMULTANEOUS EMBEDDING OF OUTERPLANAR GRAPHS, PATHS, AND CYCLES
• Universality considerations in VLSI circuits
• Boolean approaches to graph embeddings related to VLSI
• Mixed linear layouts: complexity, heuristics, and experiments
• Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
• On 3-pushdown graphs with large separators
• 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
• Embedding generalized Petersen graph in books
• Two-page book embeddings of 4-planar graphs
• The book thickness of nilpotent graphs
• On the Page Number of Upward Planar Directed Acyclic 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
• The pagenumber of the class of bandwidth-k graphs is \(k-1\)
• Approximating the fixed linear crossing number
• Succinct representation of labeled graphs
• Title not available (Why is that?)
• 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.
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• Embedding connected double-loop networks with even cardinality in books
• Embedding the incomplete hypercube in books
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
• Title not available (Why is that?)
• 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
• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Characterizations of Deque and Queue Graphs
• On the pagenumber of the cube-connected cycles
• On dispersable book embeddings
• Embedding Outerplanar Graphs in Small Books
• 1-page and 2-page drawings with bounded number of crossings per edge
• Embedding de Bruijn, Kautz and shuffle-exchange networks in books
• Algorithms for the fixed linear crossing number problem
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Routing with critical paths
• Ordered sets, pagenumbers and planarity
• Title not available (Why is that?)
• An annotated bibliography on 1-planarity
• Graph separators, with applications
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Ramsey numbers of ordered graphs
• Area requirement of graph drawings with few crossings per edge
• On the page number of RNA secondary structures with pseudoknots
• Deciding whether graph \(G\) has page number one is in NC
• Structural properties of subdivided-line graphs
• Extension of a theorem of Whitney
• The 2-page crossing number of \(K_{n}\)
• The crossing number of twisted graphs
• On the approximation of protein threading
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Succinct Representation of Labeled Graphs
• Geometric thickness in a grid
• Embedding planar 5-graphs in three pages
• Local and union page numbers
• A \((2k + 1)\)-regular graph with page-number \(k\)
• The pagenumber of \(k\)-trees is \(O(k)\)
• On book crossing numbers of the complete graph
• On Posets of Page Number 2
• Upward Book Embeddings of st-Graphs
• 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
• Book Embedding of Graphs on the Projective Plane
• Upward Partitioned Book Embeddings
• Book embeddings and crossing numbers
• Stack and queue number of 2-trees
• Title not available (Why is that?)
• On the upward book thickness problem: combinatorial and complexity results
• A survey on book-embedding of planar graphs
• Linear layouts of bipartite planar graphs
• Efficient deterministic algorithms for embedding graphs on books
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
• Fixed-parameter tractability for book drawing with bounded number of crossings per edge
• Stack-number is not bounded by queue-number
• 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
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• On 3-coloring circle graphs
• The pagewidth of trivalent planar graphs
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Recognizing geometric intersection graphs stabbed by a line
• \(k\)-spine, 1-bend planarity
• On Page Number of N-free Posets
• Parameterized analysis and crossing minimization problems
• The bipartite-cylindrical crossing number of the complete bipartite graph
• The least eigenvalues of integral circulant graphs
• The matching book embeddings of pseudo-Halin graphs
• Book thickness of the non-zero component union graph of the finite dimensional vector space

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Optimum embedding of complete graphs in books 👍 👎
• Embedding Outerplanar Graphs in Small Books 👍 👎
• A framework for solving VLSI graph layout problems 👍 👎
• Title not available (Why is that?) 👍 👎
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine 👍 👎
• Title not available (Why is that?) 👍 👎
• A survey on book-embedding of planar 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)