Combinatorial Ordering and the Geometric Embedding of Graphs

Abstract

The report introduces a new graph-theoretic structure--the (2,1)- connected sequence--with direct applicability to the embedding of both planar and nonplanar graphs. It is proven that the nodes of a graph can be ordered so as to form a (2,1)-connected sequence, regardless of whether the graph is planar or nonplanar, and such a sequence yields a new and exceptionally simple technique for planarity testing and embedding. All algorithms are proven to operate within a time bound proportional to the square of the number of nodes or edges in the graph.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 05, 1971
Accession Number
AD0732882

Entities

People

  • Lee F. Mondshein

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automata
  • Bibliographies
  • Boundaries
  • Buildings And Structures
  • Circuits
  • Computational Complexity
  • Construction
  • Decomposition
  • Department Of Defense
  • Embedding
  • Graph Theory
  • Nonplanar
  • Sequences
  • Standards
  • Theses

Readers

  • Graph Algorithms and Convex Optimization.