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. 210221.
Abstract
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 fillin edges joining two vertices of the same distance from r almost immediately. The algorithm determines an O(n)representation of these fillin edges. To determine the final fillin 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, 493528 (1994)]. An extended abstract of this paper appeared in SWAT '98.
Download: 
Postscript
 Preprinted Version
Download (523kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  chordal graphs graph algorithms planar graphs sparse Gauss elimination 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr98335 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  19 Dec 2011 09:45 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/335 