About: Planar separator theorem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Theorem in graph theory

Property	Value
dbo:description	gráfelméleti állítás (hu) theorem in graph theory (en)
dbo:thumbnail	wiki-commons:Special:FilePath/Grid_separator.svg?width=300
dbo:wikiPageExternalLink	http://resolver.sub.uni-goettingen.de/purl%3FGDZPPN002153998 http://chalermsook.googlepages.com/mincut.ps http://renyi.hu/~p_erdos/1982-12.pdf https://www.cs.cmu.edu/~glmiller/Publications/Papers/GaMi90.pdf https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiTe94.pdf https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi87.pdf http://www.math.cmu.edu/~af1p/Texfiles/sep.pdf http://www.math.ucsd.edu/~fan/mypaps/fanpap/116universal.pdf http://www.renyi.hu/~p_erdos/1976-26.pdf http://www.cs.yale.edu/homes/spielman/PAPERS/planarSep.pdf http://www.ics.uci.edu/~eppstein/pubs/EppMilTen-FI-95.ps.gz http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0427-11.pdf http://users.uoa.gr/~sedthilk/papers/planar.pdf http://digbib.ubka.uni-karlsruhe.de/eva/ira/2005/20 https://archive.org/details/pathsflowsvlsila0000unse/page/17 http://www.cs.cornell.edu/~kash/papers/BBK03.pdf http://portal.acm.org/citation.cfm%3Fid=314613.314632 http://portal.acm.org/citation.cfm%3Fid=314625
dbo:wikiPageWikiLink	dbr:Parameterized_complexity dbr:SIAM_Journal_on_Applied_Mathematics dbr:Geometric_series dbr:File:Unit_disk_graph.svg dbr:Hamiltonian_cycle dbr:Rooted_tree dbr:Tree_(graph_theory) dbr:Glossary_of_graph_theory dbr:Great_circle dbr:Tree_decomposition dbr:Wheel_graph dbr:Data_compression dbr:Gaussian_elimination dbr:Cycle_(graph_theory) dbr:Sparse_matrix dbr:Iterated_logarithm dbr:Dual_graph dbr:Journal_of_the_American_Mathematical_Society dbr:Logarithm dbr:Real_number dbr:Sphere dbr:System_of_linear_equations dbc:Theorems_in_graph_theory dbr:Leaf dbr:Acta_Informatica dbr:Metric_space dbr:Spectral_clustering dbr:Graph_isomorphism dbr:Menger's_theorem dbr:Graph_partition dbr:Cholesky_decomposition dbr:Jensen's_inequality dbr:Stereographic_projection dbr:Vertex_cover dbr:Deterministic_algorithm dbr:Maximum_independent_set dbr:Boundary_(topology) dbr:Crelle's_Journal dbr:Cut_(graph_theory) dbr:Fundamenta_Informaticae dbr:Big_O_notation dbr:Circle_packing dbr:Nearest_neighbor_graph dbr:Eigenvector dbr:Kernelization dbr:Isoperimetric_inequality dbr:Vertex_(graph_theory) dbr:Graph_embedding dbr:Dijkstra's_algorithm dbr:Graph_theory dbr:Data_structure dbr:Girth_(graph_theory) dbr:Sparse_graph dbr:Induced_subgraph dbr:Euclidean_norm dbr:Information_theory dbr:Matrix_(mathematics) dbr:Ackermann_function dbr:Symmetric_matrix dbr:Graph_minor dbr:Dominating_set dbr:Polygon_triangulation dbr:Point_location dbr:Numerische_Mathematik dbr:Shallow_minor dbr:Approximation_algorithm dbr:Finite_element_method dbr:Median dbr:Journal_of_the_ACM dbr:Branch-decomposition dbr:Branchwidth dbr:Genus_(mathematics) dbr:Convex_polyhedron dbr:Open_interval dbr:Expander_graph dbr:Laplacian_matrix dbr:Treewidth dbr:Minimum_cut dbr:Nested_dissection dbr:Binary_tree dbr:Degree_(graph_theory) dbr:Dynamic_problem_(algorithms) dbr:Dynamic_programming dbr:Four-color_theorem dbr:Connected_graph dbr:Breadth-first_search dbr:Travelling_salesman_problem dbc:Planar_graphs dbr:Planar_graph dbr:Randomized_algorithm dbr:Combinatorica dbr:Centerpoint_(geometry) dbr:Circle_packing_theorem dbr:Trivially_perfect_graph dbr:Biconnected_graph dbr:Symposium_on_Foundations_of_Computer_Science dbr:Symposium_on_Theory_of_Computing dbr:Minor_(graph_theory) dbr:Star_(graph_theory) dbr:Hereditary_property dbr:Bounded_expansion dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_Graph_Theory dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:SIAM_Journal_on_Numerical_Analysis dbr:SIAM_Journal_on_Scientific_Computing dbr:Universal_graph dbr:Vertex_separator dbr:ACM_Transactions_on_Algorithms dbr:Theory_of_Computing_Systems dbr:NP-complete dbr:NP-hard dbr:Graph_partitioning dbr:Exponential_time dbr:Fixed-parameter_tractability dbr:Jordan_curve dbr:Linear_time dbr:Geometric_separator dbr:Iterative dbr:Isoperimetric_theorem dbr:Iterative_methods dbr:Steiner_tree dbr:Grid_graph dbr:O_notation dbr:Packing_problem dbr:Euler dbr:Shortest_path dbr:Forbidden_minor dbr:Nearest-neighbor_graph dbr:Recursive dbr:Divide_and_conquer_algorithm dbr:Approximation_ratio dbr:Polynomial_time_approximation_scheme dbr:SIAM_Journal_on_Algebraic_and_Discrete_Methods dbr:File:Geode10.png dbr:File:Grid_separator.svg
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Citation dbt:Refend dbt:Sfnp dbt:Refbegin dbt:Mvar dbt:Harvtxt dbt:Tmath dbt:Short_description
dct:subject	dbc:Statements_about_planar_graphs
gold:hypernym	dbr:Form
rdfs:label	Planar separator theorem (en) Θεώρημα διαχωρισμού του επιπέδου (el) Théorème du séparateur planaire (fr) Теорема о планарном разбиении (ru) Теорема про планарне розбиття (uk)
owl:sameAs	freebase:Planar separator theorem yago-res:Planar separator theorem wikidata:Planar separator theorem dbpedia-fr:Planar separator theorem dbpedia-hu:Planar separator theorem dbpedia-fa:Planar separator theorem dbpedia-ru:Planar separator theorem dbpedia-el:Planar separator theorem dbpedia-uk:Planar separator theorem dbpedia-global:Planar separator theorem
prov:wasDerivedFrom	wikipedia-en:Planar_separator_theorem?oldid=1290008173&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Unit_disk_graph.svg wiki-commons:Special:FilePath/Geode10.png wiki-commons:Special:FilePath/Grid_separator.svg
foaf:isPrimaryTopicOf	wikipedia-en:Planar_separator_theorem
is dbo:knownFor of	dbr:Richard_Lipton
is dbo:wikiPageDisambiguates of	dbr:Separator dbr:PST
is dbo:wikiPageRedirects of	dbr:Planar_Separator_Theorem
is dbo:wikiPageWikiLink of	dbr:NP-completeness dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Pankaj_K._Agarwal dbr:Graph_partition dbr:Paul_Seymour_(mathematician) dbr:Pathwidth dbr:Nearest_neighbor_graph dbr:Isoperimetric_inequality dbr:Separation_theorem dbr:Separator dbr:Level_structure dbr:Graph_minor dbr:Haven_(graph_theory) dbr:Shallow_minor dbr:PST dbr:Minimum-weight_triangulation dbr:Nested_dissection dbr:Planar_graph dbr:List_of_theorems dbr:Circle_packing_theorem dbr:Richard_Lipton dbr:1-planar_graph dbr:Pebble_game dbr:Book_embedding dbr:Joan_Hutchinson dbr:Bounded_expansion dbr:Chordal_completion dbr:Universal_graph dbr:Vertex_separator dbr:Geometric_separator dbr:Polygonalization dbr:Planar_Separator_Theorem
is foaf:primaryTopic of	wikipedia-en:Planar_separator_theorem