Accession Number : ADA195180

Title :   A Graph with E Edges Has Pagenumber o (the Square root of E log E),

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE MICROSYSTEMS RESEARCH CENTER

Personal Author(s) : Malitz, Seth M

PDF Url : ADA195180

Report Date : Nov 1987

Pagination or Media Count : 10

Abstract : A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an embedding of its edges on the pages so that no two edges on a given page intersect. The minimum number of pages in which a graph can be embedded is its pagenumber. This paper presents the results. Keywords: Upper bounds; Lower bounds; Probability.

Descriptors :   *GRAPHS, *PROBABILITY, BOOKS, EDGES, EMBEDDING, SQUARE ROOTS, BOUNDARIES

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE