Optimal and Near-Optical Results on Book Embeddings

Abstract

A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its page number. The page number of a class of graphs is the minimum number of pages in which all the members of the class can be embedded, as a function of graph size. This thesis, proves certain results, all of which substantially improve previously known bounds. Keywords: Mesh, Algorithms, Very large scale integration, Theses.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1989
Accession Number
ADA208118

Entities

People

  • Seth M. Malitz

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Applied Mathematics
  • Automata
  • Automata Theory
  • Circuit Boards
  • Computations
  • Computer Science
  • Computers
  • Fabrication
  • Large Scale Integration
  • Mathematics
  • Printed Circuit Boards
  • Printed Circuits
  • Theorems
  • Theoretical Computer Science
  • Three Dimensional
  • Two Dimensional
  • Very Large Scale Integration

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Political Science/ International Relations/ European Studies