Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Planar_separator_theorem> ?p ?o }
- Planar_separator_theorem abstract "In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(√n) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.A weaker form of the separator theorem with O(√n log n) vertices in the separator instead of O(√n) was originally proven by Ungar (1951), and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan (1979). Since their work, the separator theorem has been reproven in several different ways, the constant in the O(√n) term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithms for planar graphs, and dynamic programming on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard optimization problems on these graphs. Separator hierarchies may also be used in nested dissection, an efficient variant of Gaussian elimination for solving sparse systems of linear equations arising from finite element methods.".
- Planar_separator_theorem thumbnail Grid_separator.svg?width=300.
- Planar_separator_theorem wikiPageExternalLink mincut.ps.
- Planar_separator_theorem wikiPageExternalLink citation.cfm?id=314613.314632.
- Planar_separator_theorem wikiPageExternalLink citation.cfm?id=314625.
- Planar_separator_theorem wikiPageExternalLink 1982-12.pdf.
- Planar_separator_theorem wikiPageExternalLink purl?GDZPPN002153998.
- Planar_separator_theorem wikiPageExternalLink BBK03.pdf.
- Planar_separator_theorem wikiPageExternalLink EppMilTen-FI-95.ps.gz.
- Planar_separator_theorem wikiPageExternalLink 0427-11.pdf.
- Planar_separator_theorem wikiPageExternalLink 117separatorthms.pdf.
- Planar_separator_theorem wikiPageExternalLink 1976-26.pdf.
- Planar_separator_theorem wikiPageExternalLink 20.
- Planar_separator_theorem wikiPageExternalLink planar.pdf.
- Planar_separator_theorem wikiPageExternalLink GaMi90.pdf.
- Planar_separator_theorem wikiPageExternalLink GrMiTe94.pdf.
- Planar_separator_theorem wikiPageExternalLink Mi87.pdf.
- Planar_separator_theorem wikiPageExternalLink planarSep.pdf.
- Planar_separator_theorem wikiPageExternalLink sep.pdf.
- Planar_separator_theorem wikiPageExternalLink 116universal.pdf.
- Planar_separator_theorem wikiPageID "18978005".
- Planar_separator_theorem wikiPageLength "68178".
- Planar_separator_theorem wikiPageOutDegree "162".
- Planar_separator_theorem wikiPageRevisionID "681743725".
- Planar_separator_theorem wikiPageWikiLink Ackermann_function.
- Planar_separator_theorem wikiPageWikiLink Approximation_algorithm.
- Planar_separator_theorem wikiPageWikiLink Approximation_ratio.
- Planar_separator_theorem wikiPageWikiLink Big_O_notation.
- Planar_separator_theorem wikiPageWikiLink Binary_tree.
- Planar_separator_theorem wikiPageWikiLink Boundary_(topology).
- Planar_separator_theorem wikiPageWikiLink Branch-decomposition.
- Planar_separator_theorem wikiPageWikiLink Branchwidth.
- Planar_separator_theorem wikiPageWikiLink Breadth-first_search.
- Planar_separator_theorem wikiPageWikiLink Category:Planar_graphs.
- Planar_separator_theorem wikiPageWikiLink Category:Theorems_in_graph_theory.
- Planar_separator_theorem wikiPageWikiLink Centerpoint_(geometry).
- Planar_separator_theorem wikiPageWikiLink Cholesky_decomposition.
- Planar_separator_theorem wikiPageWikiLink Circle_packing.
- Planar_separator_theorem wikiPageWikiLink Circle_packing_theorem.
- Planar_separator_theorem wikiPageWikiLink Connected_graph.
- Planar_separator_theorem wikiPageWikiLink Connectivity_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Convex_polyhedron.
- Planar_separator_theorem wikiPageWikiLink Convex_polytope.
- Planar_separator_theorem wikiPageWikiLink Crelles_Journal.
- Planar_separator_theorem wikiPageWikiLink Cut_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Cycle_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Data_compression.
- Planar_separator_theorem wikiPageWikiLink Data_structure.
- Planar_separator_theorem wikiPageWikiLink Degree_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Dense_graph.
- Planar_separator_theorem wikiPageWikiLink Deterministic_algorithm.
- Planar_separator_theorem wikiPageWikiLink Dijkstras_algorithm.
- Planar_separator_theorem wikiPageWikiLink Divide_and_conquer_algorithm.
- Planar_separator_theorem wikiPageWikiLink Divide_and_conquer_algorithms.
- Planar_separator_theorem wikiPageWikiLink Dominating_set.
- Planar_separator_theorem wikiPageWikiLink Dual_graph.
- Planar_separator_theorem wikiPageWikiLink Dynamic_problem_(algorithms).
- Planar_separator_theorem wikiPageWikiLink Dynamic_programming.
- Planar_separator_theorem wikiPageWikiLink Eigenvalues_and_eigenvectors.
- Planar_separator_theorem wikiPageWikiLink Eigenvector.
- Planar_separator_theorem wikiPageWikiLink Euclidean_norm.
- Planar_separator_theorem wikiPageWikiLink Euler.
- Planar_separator_theorem wikiPageWikiLink Expander_graph.
- Planar_separator_theorem wikiPageWikiLink Exponential_time.
- Planar_separator_theorem wikiPageWikiLink Finite_element_method.
- Planar_separator_theorem wikiPageWikiLink Fixed-parameter_tractability.
- Planar_separator_theorem wikiPageWikiLink Forbidden_graph_characterization.
- Planar_separator_theorem wikiPageWikiLink Forbidden_minor.
- Planar_separator_theorem wikiPageWikiLink Four-color_theorem.
- Planar_separator_theorem wikiPageWikiLink Four_color_theorem.
- Planar_separator_theorem wikiPageWikiLink Gaussian_elimination.
- Planar_separator_theorem wikiPageWikiLink Genus_(mathematics).
- Planar_separator_theorem wikiPageWikiLink Geometric_separator.
- Planar_separator_theorem wikiPageWikiLink Geometric_series.
- Planar_separator_theorem wikiPageWikiLink Girth_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Glossary_of_graph_theory.
- Planar_separator_theorem wikiPageWikiLink Graph_embedding.
- Planar_separator_theorem wikiPageWikiLink Graph_isomorphism.
- Planar_separator_theorem wikiPageWikiLink Graph_minor.
- Planar_separator_theorem wikiPageWikiLink Graph_partition.
- Planar_separator_theorem wikiPageWikiLink Graph_partitioning.
- Planar_separator_theorem wikiPageWikiLink Graph_theory.
- Planar_separator_theorem wikiPageWikiLink Great_circle.
- Planar_separator_theorem wikiPageWikiLink Grid_graph.
- Planar_separator_theorem wikiPageWikiLink Hamiltonian_cycle.
- Planar_separator_theorem wikiPageWikiLink Hamiltonian_path.
- Planar_separator_theorem wikiPageWikiLink Independent_set_(graph_theory).
- Planar_separator_theorem wikiPageWikiLink Induced_subgraph.
- Planar_separator_theorem wikiPageWikiLink Information_theory.
- Planar_separator_theorem wikiPageWikiLink Interval_(mathematics).
- Planar_separator_theorem wikiPageWikiLink Isoperimetric_inequality.
- Planar_separator_theorem wikiPageWikiLink Isoperimetric_theorem.
- Planar_separator_theorem wikiPageWikiLink Iteration.
- Planar_separator_theorem wikiPageWikiLink Iterative.
- Planar_separator_theorem wikiPageWikiLink Iterative_method.
- Planar_separator_theorem wikiPageWikiLink Iterative_methods.
- Planar_separator_theorem wikiPageWikiLink Jensens_inequality.
- Planar_separator_theorem wikiPageWikiLink Jordan_curve.
- Planar_separator_theorem wikiPageWikiLink Jordan_curve_theorem.
- Planar_separator_theorem wikiPageWikiLink Journal_of_the_ACM.