Planar Separators and Parallel Polygon Triangulation

Planar Separators and Parallel Polygon Triangulation (1992) (Make Corrections) (27 citations)
Michael T. Goodrich

View or download:
jhu.edu/~goodrich/pubs/tri.ps.gz
jhu.edu/~goodrich/pubs/tri.ps
jhu.edu/~goodrich/cgc/pubs/tri.ps.gz
Cached:  PS.gz  PS  PDF  DjVu  Image  Update  Help

From:  jhu.edu/~goodrich/pubs/index (more)
From:  jhu.edu/~goodrich/pubs/
Homepages:  M.Goodrich  HPSearch  (Update Links)

Rate this article:

(best)
Comment on this article

(Enter summary)
Abstract: We show how to construct an O( p n)-separator decomposition of a planar graph G in O(n) time. Such a decomposition defines a binary tree where each node corresponds to a subgraph of G and stores an O( p n)-separator of that subgraph. We also show how to construct an O(n ffl )-way decomposition tree in parallel in O(log n) time so that each node corresponds to a subgraph of G and stores an O(n 1=2+ffl )-separator of that subgraph. We demonstrate the utility of such a separator decomposition by... (Update)

Context of citations to this paper: More

.... of linear equations [14, 9] for developing algorithms for VLSI layout design [4, 12] for shortest path problems [7] in parallel computing [10], and in computational complexity [16] A class of problems for whose solutions separator theorems are especially well suited is data...

.... that can report the k intersections of a chain of n segments in time O(n k) Can our linear time algorithm be parallelized (Goodrich [13] has given a fast and work optimal implementation of Chazelle s algorithm in a parallel computation model. Can the approach of...

Cited by: More
Optimal Cooperative Search In Fractional Cascaded Data.. - Tamassia, Vitter (1995) (Correct)
On External Memory MST, SSSP and Multi-way Planar Graph.. - Arge, al. (Correct)
Fully Dynamic Planarity Testing with Applications - Galil, Italiano, Sarnak (1992) (Correct)

Active bibliography (related documents): More All
0.6: Computational Geometry I - Lee (1996) (Correct)
0.4: Structural Parallel Algorithmics - Vishkin (1991) (Correct)
0.3: Linear-Time Triangulation of a Simple Polygon Made Easier .. - Amato, Goodrich, Ramos (2000) (Correct)

Similar documents based on text: More All
0.4: Generating All The Minimal Separators Of A Graph - Berry, Bordat, Cogis (1999) (Correct)
0.4: Decomposition by clique minimal separators - Berry, Bordat (1999) (Correct)
0.4: Applications of the Dulmage-Mendelsohn Decomposition and.. - Ashcraft, Liu (1998) (Correct)

Related documents from co-citation: More All
17: A Separator Theorem for Planar Graphs (context) - Lipton, Tarjan - 1979
7: Data structures for on-line updating of minimum spanning trees (context) - Frederickson - 1985
7: Fast algorithms for shortest paths in planar graphs (context) - Frederickson - 1987

BibTeX entry: (Update)

M. Goodrich, "Planar separators and parallel polygon triangulation," Proc. 24th Annual ACM Symposium on Theory of Computing (1992), 507--516. http://citeseer.nj.nec.com/goodrich92planar.html More

@inproceedings{ goodrich92planar,
    author = "Michael T. Goodrich",
    title = "Planar separators and parallel polygon triangulation (preliminary version)",
    pages = "507--516",
    year = "1992",
    url = "citeseer.nj.nec.com/goodrich92planar.html" }

Citations (may not include all citations):
2998 Introduction to Algorithms (context) - Cormen, Leiserson et al. - 1990
1114 Computational Geometry: An Introduction (context) - Preparata, Shamos - 1985
465 Graph Theory with Applications (context) - Bondy, Murty - 1976
397 Data Structures and Algorithms (context) - Aho, Hopcroft et al. - 1983
299 An Introduction to Parallel Algorithms (context) - J'aJ'a - 1992
254 Parallel Algorithms for Shared-Memory Machines (context) - Karp, Ramachandran - 1990
223 Primitives for the Manipulation of General Subdivisions and .. (context) - Guibas, Stolfi - 1985
220 Data Structures and Network Algorithms (context) - Tarjan - 1983
187 Parallel Merge Sort (context) - Cole - 1988
176 A Separator Theorem for Planar Graphs (context) - Lipton, Tarjan - 1979
175 Parallel Prefix Computation (context) - Ladner, Fischer - 1980
155 A Data Structure for Dynamic Trees (context) - Sleator, Tarjan - 1983
153 Triangulating a Simple Polygon in Linear Time (context) - Chazelle - 1991
149 The Parallel Evaluation of General Arithmetic Expressions (context) - Brent - 1974
106 A Dichromatic Framework for Balanced Trees (context) - Guibas, Sedgewick - 1978
82 Applications of a Planar Separator Theorem (context) - Lipton, Tarjan - 1980
78 Linear Time Algorithms for Visibility and Shortest Path Prob.. (context) - Guibas, Hershberger et al. - 1987
73 A Framework for Solving VLSI Graph Layout Problems - Bhatt, Leighton - 1984
55 Parallel Computational Geometry (context) - Aggarwal, Chazelle et al. - 1988
47 Deterministic Parallel List Ranking (context) - Anderson, Miller - 1988
44 Maintenance of a Minimum Spanning Forest in a Dynamic Planar.. - Eppstein, Italiano et al. - 1992
44 Triangulating Simple Polygons and Equivalent Problems (context) - Fournier, Montuno - 1984
43 A Theorem on Polygon Cutting with Applications (context) - Chazelle - 1982
43 A Polyhedron Representation for Computer Vision (context) - Baumgart - 1975
40 Dynamic Trees and Dynamic Point Location - Goodrich, Tamassia - 1991
34 Finding the Intersection of Two Convex Polyhedra (context) - Muller, Preparata - 1978
32 Highly Parallelizable Problems (context) - Berman, Breslauer et al. - 1989
30 Finding Biconnected Components and Computing Tree Functions .. (context) - Tarjan, Vishkin - 1985
25 Separator Based Sparsification for Dynamic Planar Graph Algo.. (context) - Eppstein, Galil et al. - 1993
24 Triangulating a Simple Polygon (context) - Garey, Johnson et al. - 1978
23 The Accelerated Centroid Decomposition Technique for Optimal.. - Cole, Vishkin - 1988
22 The Power of Parallel Prefix (context) - Kruskal, Rudolph et al. - 1985
20 Randomized Parallel Algorithms for Trapezoidal Diagrams - Clarkson, Cole et al. - 1992
19 An Optimal Worst Case Algorithm for Reporting Intersections .. (context) - Bentley, Wood - 1980
19 Fast Algorithms for Shortest Paths in Planar Graphs, with Ap.. (context) - Frederickson - 1987
15 Area-Efficient Graph Layouts (for VLSI (context) - Leiserson - 1980
14 Triangulating a Polygon in Parallel (context) - Goodrich - 1989
13 Parallel Methods for Visibility and Shortest Path Problems i.. (context) - Goodrich, Shauck et al. - 1990
11 Parallel Triangulation of a Polygon in Two Calls to the Trap.. (context) - Yap - 1988
11 A Parallel Algorithm for Finding a Separator in Planar Graph.. (context) - Gazit, Miller - 1987
8 Approximate Parallel Scheduling, Part I: The Basic Technique.. (context) - Cole, Vishkin - 1988
8 Optimal Parallel Algorithms for Triangulated Simple Polygons (context) - Hershberger - 1992
7 Finding Small Simple Cycle Separators for 2-Connected Planar.. (context) - Miller - 1986
6 An O(n log log n)-time Algorithm for Triangulating a Simple .. (context) - Tarjan, Van Wyk - 1988
3 An Optimal Parallel Algorithm for Building a Data Structure .. (context) - Cole, Zajicek - 1990
2 Polygon Triangulation in O(n log log n) time with Simple Dat.. (context) - Kirkpatrick, Klawe et al. - 1990

The graph only includes citing articles where the year of publication is known.

Documents on the same site (http://www.cgc.cs.jhu.edu/~goodrich/pubs/index.html): More
Optimizing Area and Aspect Ratio in Straight-Line.. - Chan, Goodrich, al. (1997) (Correct)
Parallel Algorithms for Higher-Dimensional Convex Hulls - Amato, Goodrich, Ramos (1994) (Correct)
Planar Upward Tree Drawings with Optimal Area - Garg, Goodrich, Tamassia (1996) (Correct)

Online articles have much greater impact More about CiteSeer Add search form to your site Submit documents Feedback