Claw-Free Maximal Planar Graphs

Abstract

A graph G is claw-free if it contains no induced subgraph isomorphic to the complete bipartite graph K. Such graphs have been widely studied with respect to such other graph properties as matching, perfection, vertex-packing, Hamiltonian cycles and related questions on traversability, and reconstruction. A planar graph is said to be maximal planar (or a triangulation) if, given any imbedding of G in the plane, every face boundary is a triangle. The abbreviations MAXP and CFMAXP are used for the properties maximal planar and claw-free maximal planar respectively. (Recall that every maximal planar graph with at least three points is either the complete graph K3 or else is 3- connected and thus it follows that such a graph has a unique imbedding in the plane).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA210179

Entities

People

  • Michael D. Plummer

Organizations

  • Vanderbilt University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Availability
  • Boundaries
  • Congress
  • Contracts
  • Decomposition
  • Graph Theory
  • Mathematics
  • New York
  • Observation
  • Orientation (Direction)
  • Symmetry
  • Tennessee
  • Triangles
  • Triangulation
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.