Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph

Abstract

We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion and deletion of edges and vertices. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithms run in O(log n) time per operation and O(n) space. The algorithms can be used to maintain the connected components of a dynamic planar graph in O(log n) time per operation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 18, 1990
Accession Number
ADA221425

Entities

People

  • David Eppstein
  • Giuseppe F. Italiano
  • Jeffery Westbrook
  • Robert Tarjan
  • Roberto Tamassia

Organizations

  • Princeton University

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Communication Networks
  • Computer Science
  • Computers
  • Embedding
  • Lists (Data Structures)
  • Maintenance
  • New York
  • Notation
  • Numbers
  • Real Numbers
  • Sequences
  • Topology
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Robotics and Automation.

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers