Finding small simple cycle separators for 2-connected planar graphs
Journal of Computer and System SciencesPublished 1 June 1986
Gary L. Miller
Citations252
SJR quartileQ1
SJR score1.03
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that every 2-connected triangulated planar graph with n vertices has a simple cycle C of length at most 2√2 · n which separates the interior vertices A from the exterior vertices B such that neither A nor B contain more than 2 3n vertices.
Abstract
We show that every 2-connected triangulated planar graph with n vertices has a simple cycle C of length at most 2√2 · n which separates the interior vertices A from the exterior vertices B such that neither A nor B contain more than 23n vertices. The method also gives a linear time sequential algorithm for finding this simple cycle and an NC parallel algorithm. In general, if the maximum face size is d then we exhibit a cycle C as above of size at most 2√d · n.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Journal of Computer and System SciencesTesting for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
1,498 Citations1976Kellogg S. Booth, George S. Lueker
The consecutive ones test for the consecutive ones property in matrices and for graph planarity is extended to a test for interval graphs using a recently discovered fast recognition algorithm for chordal graphs.
SIAM Journal on Applied MathematicsA Separator Theorem for Planar Graphs
1,338 Citations1979Richard J. Lipton, Robert E. Tarjan
Graph Algorithms
1,284 Citations1979Shimon Even
A thoroughly revised second edition of Shimon Even's Graph Algorithms, with a foreword by Richard M. Karp and notes by Andrew V Goldberg, explains algorithms in a formal but simple language with a direct and intuitive presentation.
Journal of the ACMEfficient Planarity Testing
1,079 Citations1974John E. Hopcroft, Robert E. Tarjan
An efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane is described, which used depth-first search and has time and space bounds.
Journal of the ACMThe Parallel Evaluation of General Arithmetic Expressions
818 Citations1974Richard P. Brent
It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log 2 + 10(n - 1) using processors which can independently perform arithmetic operations in unit time.
Journal of AlgorithmsAn O(logn) parallel connectivity algorithm
598 Citations1982Yossi Shiloach, Uzi Vishkin
It is conjectured that the barrier of O(log n) cannot be surpassed by any polynomial number of processors and that this performance cannot be achieved in the weaker model.
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
Parallel tree contraction and its application
409 Citations1985Gary L. Miller, John H. Reif
A bottom-up algorithm to handle trees which has two major advantages over the top-down approach: the control structure is straight forward and easier to implement facilitating new algorithms using fewer processors and less time; and problems for which it was too difficult or too complicated to find polylog parallel algorithms are now easy.
IEEE Transactions on ComputersUniversality considerations in VLSI circuits
389 Citations1981Leslie G. Valiant
The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed and restricted classes of graphs have to be considered in order to achieve compact embeddings.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Area-Efficient Graph Layouts (for VLSI).
254 Citations1980Charles E. Leiserson
An algorithm is given that produces VLSI layouts for classes of graphs that have good separator theorems and shows in particular that any planar graph of n vertices has an O(n lg-square(n) area layout and that any tree of n Vertices can be laid out in linear area.
Finding biconnected componemts and computing tree functions in logarithmic parallel time
186 Citations1984Robert E. Tarjan, Uzi Vishkin
A general algorithmic technique which simplifies and improve computation of various functions on tress is introduced, which typically requires 0(log n) time using 0(n) space on an exclusive-read exclusive-write parallel RAM.
SIAM Journal on Algebraic and Discrete MethodsOn the Problem of Partitioning Planar Graphs
99 Citations1982Hristo Djidjev
It is shown that every planar graph can be partitioned into two or more components of roughly equal size by deleting only $O ( \sqrt{n} )$ vertices, and such a partitioning can be found in time.
SIAM Journal on ComputingParallel Algorithms in Graph Theory: Planarity Testing
89 Citations1982Joseph F. JáJá, Janoš Šimon
This work presents efficient $(O(\log ^2 n)$ parallel algorithms for two classical graph problems: planarity testing and finding triconnected components, using only a polynomial number of processors.
Partition of planar flow networks
17 Citations1983D. Barton Johnson, Shankar M. Venkatesan
An O(n √n logn) maximum flow algorithm for directed planar networks (hence for any planar network) is developed.