Results 231 to 240 of about 197,938 (280)
Some of the next articles are maybe not open access.
Book Embeddings of Regular Graphs
SIAM Journal on Discrete Mathematics, 2015Summary: In the influential papers in which \textit{M. Malitz} [J. Algorithms 17, No. 1, 71--84 (1994; Zbl 0810.68102); ibid. No. 1, 85--109 (1994; Zbl 0810.68103)] proved that every graph with \(m\) edges can be embedded in a book with \(O({m}^{1/2})\) pages, he proved the existence of \(d\)-regular \(n\)-vertex graphs that require \(\Omega(\sqrt{d}n^{
Balogh, József, Salazar, Gelasio
openaire +2 more sources
Degree constrained book embeddings
Journal of Algorithms, 2002Summary: A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine) and an assignment of edges to half-planes with the spine as boundary (the pages) so that edges assigned to the same page can be drawn on that page without crossings.
openaire +2 more sources
Afrika Matematika
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Luke Martin +3 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Luke Martin +3 more
openaire +2 more sources
Embedding Outerplanar Graphs in Small Books
SIAM Journal on Algebraic Discrete Methods, 1987A 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.
openaire +2 more sources
Vertex Types in Book-Embeddings
SIAM Journal on Discrete Mathematics, 1989A new measure of the complexity of a book-embedding of a simple undirected graph, the number of vertex types in the embedding, is studied. The type of a vertex $v $ in a p-page book-embedding is the $p \times 2$ matrix of nonnegative integers \[ \tau (v ) = \begin{pmatrix} L_1 & & R_1 \\ L_2 & & R_2 \\ & \vdots & \\ L_P & & {R_P } \end{pmatrix ...
Jonathan F. Buss +2 more
openaire +1 more source
PACRIM. 2005 IEEE Pacific Rim Conference on Communications, Computers and signal Processing, 2005., 2005
In this paper, we study the linear layout problem of the rectangular mesh by the embedding-in-book technique. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges residing in a page do not cross. We propose a scheme to embed an h /spl times/ w rectangular mesh with two pages and book width Min(h,w ...
null Erh-Ying Yen +4 more
openaire +1 more source
In this paper, we study the linear layout problem of the rectangular mesh by the embedding-in-book technique. Embedding a graph in a book is to place nodes on the spine of a book and to draw the edges such that edges residing in a page do not cross. We propose a scheme to embed an h /spl times/ w rectangular mesh with two pages and book width Min(h,w ...
null Erh-Ying Yen +4 more
openaire +1 more source
Upward Topological Book Embeddings of DAGs [PDF]
SIAM Journal on Discrete Mathematics, 2011 Let G be a directed acyclic graph (DAG). An upward (k,h)-topological book embedding of G is an upward book embedding on k pages of a subdivision of G where every edge is replaced by a path having at most h+2 vertices. In this paper it is proved that every DAG with n vertices admits an upward (d+1, 2⌈logdn⌉-1)-topological book embedding, where d is any ...
DI GIACOMO, Emilio +2 more
openaire +1 more source
Book embeddings and crossing numbers
1995The paper introduces the book crossing number problem which can be viewed as a variant of the well-known plane and surface crossing number problem or as a generalization of the book embedding problem. The book crossing number of a graph G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k-page book ...
Farhad Shahrokhi +3 more
openaire +1 more source