Results 251 to 260 of about 7,209 (302)

Book Embeddings of Regular Graphs

SIAM Journal on Discrete Mathematics, 2015
Summary: 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, 2002
Summary: 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

Klein book embeddings

Afrika Matematika
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Luke Martin, Thomas McKenzie, Shannon Overbay, Lin Ai Tan   +3 more
openaire   +2 more sources

Embedding Outerplanar Graphs in Small Books

SIAM Journal on Algebraic Discrete Methods, 1987
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.
openaire   +2 more sources

Vertex Types in Book-Embeddings

SIAM Journal on Discrete Mathematics, 1989
A 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, Arnold L. Rosenberg, Judson D. Knott   +2 more
openaire   +1 more source