Vertex Types in Book-Embeddings (Q4734772)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4121460
Language Label Description Also known as
default for all languages
No label defined
    English
    Vertex Types in Book-Embeddings
    scientific article; zbMATH DE number 4121460

      Statements

      Vertex Types in Book-Embeddings (English)
      0 references
      0 references
      0 references
      0 references
      1989
      0 references
      design of fault-tolerant processor arrays
      0 references
      VLSI design
      0 references
      outerplanar graphs
      0 references
      NP-completeness
      0 references
      Book embeddings of graphs
      0 references
      Book embeddings of graphs were studied with respect to their page number and page width. Here a new measure of the complexity of a book-embedding is studied, namely the number of vertex types in the embedding. For a somewhat more detailed description of the results recall that ``... a book is a set of half-planes (the pages of the book) that share a common boundary line (the spine of the book). An embedding of a simple undirected graph G in a book consists of an ordering of the vertices of G along the spine of the book together with an assignment of each edge of G to a page of the book, in which edges assigned to the same page do not cross....'' The number of vertex types in a p-page book-embedding of a graph G is defined as follows: ``... each vertex v of G has an associated \(p\times 2\) matrix of nonnegative integers, called its type, \[ \tau(v) = \begin{pmatrix} L_1 & R_1 \\ L_2 & R_2 \\ \vdots & \vdots \\ L_ p & R_ p \end{pmatrix} \] \(L_ i\) (respectively, \(R_ i)\) is the number of edges incident to v that connect on page i to vertices lying to the left (respectively, to the right) of v....'' ``The number of types in a book-embedding relates to the amount of logic necessary to realize fault-tolerant arrays of processors using one specific design methodology.... the base-two logarithm of the number of vertex types is the number of control bits per processing element needed to configure the array to its fault-free format....'' ``... We study techniques for bounding the typenumbers of graphs by studying a variety of specific graphs ({\S} 3); we then investigate the relationships between typenumber and a number of other structural properties of graphs ({\S} 4); we finally consider the problem of minimizing the typenumber of a graph. We show that the problem of finding a typenumber-minimal one-pag embedding of an outerplanar graph is NP-complete. We then fall back to the problem of minimizing the type number of a given book-embedding, by means of a (cyclic) rotation....''
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references