Minimal Elimination Orderings for Planar Graphs

Dahlhaus, Elias (1998) Minimal Elimination Orderings for Planar Graphs.
Published In: Algorithm theory : proceedings / SWAT '98, 6th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, July 8 - 10, 1998, Lecture notes in computer science. 1432 Springer 1998, pp. 210-221.


We prove that the problem to get an inclusion minimal elimination ordering can be solved in linear time for planar graphs. The basic structure of the linear time algorithm is as follows. We select a vertex r as maximum and get a first approximation of a minimal elimination ordering considering a vertex x as smaller than y if x has a larger distance than y from r. Using planarity, one can determine the fill-in edges joining two vertices of the same distance from r almost immediately. The algorithm determines an O(n)-representation of these fill-in edges. To determine the final fill-in ordering, we use similar techniques as in the general parallel minimal elimination algorithm of Elias Dahlhaus, Marek Karpinski [An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph, Theoretical Computer Science 134, 493-528 (1994)]. An extended abstract of this paper appeared in SWAT '98.

Download: [img] Postscript - Preprinted Version
Download (523kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr98-335
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45