Results 251 to 260 of about 12,131,917 (294)

Book Embedding of Graphs on the Projective Plane

SIAM Journal on Discrete Mathematics, 2019
Summary: For a positive integer \(k\), a book (with \(k\) pages) is a topological space consisting of a spine, which is a line, and \(k\) pages, which are half-planes with the spine as their boundary. We say that a graph \(G\) admits a \(k\)-page book embedding or is \(k\)-page book embeddable if there exists a linear ordering of the vertices on the ...
Atsuhiro Nakamoto, Kenta Ozeki
exaly   +4 more sources

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^{
József Balogh, Gelasio Salazar
openaire   +2 more sources

Embedding the incomplete hypercube in books

Information Processing Letters, 2005
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Jywe-Fei Fang, Kuan-Chou Lai
openaire   +3 more sources

Book Embedding of Toroidal Bipartite Graphs

SIAM Journal on Discrete Mathematics, 2012
Endo proved that every toroidal graph has a book embedding with at most seven pages. In this paper, we prove that every toroidal bipartite graph has a book embedding with at most five pages. In order to do so, we prove that every bipartite torus quadrangulation Q with n vertices admits two disjoint noncontractible simple closed curves cutting the torus
Atsuhiro Nakamoto, Kenta Ozeki, Katsuhiro Ota   +2 more
exaly   +3 more sources

Advancements on SEFE and Partitioned Book Embedding problems

Theoretical Computer Science, 2015
29 pages, 10 figures, extended version of 'On Some NP-complete SEFE Problems' (Eighth International Workshop on Algorithms and Computation, 2014)
Patrizio Angelini, Giordano Da Lozzo
exaly   +6 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   +2 more sources

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, F. Giordano, LIOTTA, Giuseppe   +2 more
openaire   +2 more sources

Embedding Outerplanar Graphs in Small Books

SIAM Journal on Algebraic and 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.
Lenwood S Heath
exaly   +2 more sources