
doi: 10.1137/0608018
A book consists of a number of half-planes (pages) sharing a common boundary line (the spine). A book embedding of a graph embeds the vertices on the spine and each edge in some page so that each page contains a plane subgraph. The width of a page is the maximum number of edges that intersect any half-line perpendicular to the spine in the page. The pagewidth of the embedding is the maximum width of any page, and the pagewidth of the graph G is the minimum pagewidth of any book embedding of G in a book having a minimum number of pages for G. The author presents an O(n log n) time algorithm for embedding an n-vertex outerplanar graph with small pagewidth. The algorithm embeds any d-valent outerplanar graph in a two-page book with pagewidth O(d log n). This result is optimal in pagenumber for the stated pagewidth and optimal in pagewidth (to within a constant factor) for the class of outerplanar graphs. There is application to fault-tolerant arrays of VLSI processors: any outerplanar graph can be implemented in small area, in a fault- tolerant fashion.
algorithm, book embedding, pagewidth of the graph, spine, VLSI processors, Planar graphs; geometric and topological aspects of graph theory, outerplanar graph, width, book, Applications of graph theory to circuits and networks, pages, pagewidth of the embedding
algorithm, book embedding, pagewidth of the graph, spine, VLSI processors, Planar graphs; geometric and topological aspects of graph theory, outerplanar graph, width, book, Applications of graph theory to circuits and networks, pages, pagewidth of the embedding
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
