Two Linear-Time Algorithms for Five-Coloring a Planar Graph,

Abstract

A sequential processing algorithm using bicolor interchange that five-colors an n vertex planar graph in O(n-squared) time was given by Matula, Marble, and Isaacson. Lipton and Miller used a batch processing algorithm with bicolor interchange for the same problem and achieved an improved O(n log n) time bound. In this paper we use graph contraction arguments instead of bicolor interchange and improve both the sequential processing and batch processing methods to obtain five-coloring algorithms that operate in O(n) time. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1980
Accession Number
ADA098835

Entities

People

  • David W. Matula
  • Robert Tarjan
  • Yossi Shiloach

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Batch Processing
  • Boundaries
  • Computer Programming
  • Computer Science
  • Computers
  • Contracts
  • Embedding
  • Graph Theory
  • Information Processing
  • Lists (Data Structures)
  • Military Research
  • New York
  • United States
  • Universities

Readers

  • Distributed Systems and Data Platform Development
  • Graph Algorithms and Convex Optimization.