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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1987
Accession Number
ADA195180

Entities

People

  • Seth M. Malitz

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Coefficients
  • Contracts
  • Embedding
  • Governments
  • Indicators
  • Massachusetts
  • Observation
  • Probability
  • Random Variables
  • Sequences
  • Standards

Readers

  • Business Analytics
  • Graph Algorithms and Convex Optimization.