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
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
0.8433318138122559
0 references
0.8201844096183777
0 references
0.8108008503913879
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