About: Planar separator theorem   Goto Sponge  NotDistinct  Permalink

An Entity of Type : yago:Graph107000195, within Data Space : wasabi.inria.fr associated with source document(s)

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 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 vertices.

AttributesValues
type
label
  • Planar separator theorem
  • Теорема про планарне розбиття
  • Теорема о планарном разбиении
  • Théorème du séparateur planaire
  • Θεώρημα διαχωρισμού του επιπέδου
comment
  • Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами (здесь O обозначает «O» большое) можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
  • У теорії графів, теорема про планарне розбиття є формою ізопериметричної нерівності для планарних графів, що стверджує, що будь-який планарний граф можна розділити на дрібніші шматки, видаляючи невелику кількість вершин. Зокрема, видалення вершин з -вершинного графа (де О використано по аналогії з O великим ) може розділити граф на непересічні підграфи, кожен з яких має не більше вершин.
  • Στη θεωρία γραφημάτων, το θεώρημα διαχωριστικού επιπέδου είναι μια μορφή για επίπεδες γραφικές παραστάσεις, που αναφέρει ότι οποιαδήποτε επίπεδη γραφική παράσταση μπορεί να χωριστεί σε μικρότερα κομμάτια αφαιρώντας ένα μικρό αριθμό κορυφών. Συγκεκριμένα, η απομάκρυνση της O(√n) κορυφής από ένα γράφημα με n-κορυφές (όπου το O επικαλείται επικαλείται μεγάλο Ο συμβολισμό) μπορεί να χωρίσει το γράφημα σε ασυνεχείς υπογράφους καθένα από τα οποία έχει το πολύ 2n / 3 κορυφές.
  • 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 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 vertices.
  • En théorie des graphes, le théorème du séparateur planaire, stipule que tout graphe planaire peut être divisé en parties plus petites en supprimant un petit nombre de sommets. Plus précisément, le théorème affirme qu'il existe un ensemble de sommets d'un graphe à sommets dont la suppression partitionne le graphe en sous-graphes disjoints dont chacun a au plus sommets.
sameAs
topic
depiction
  • External Image
  • External Image
  • External Image
described by
subject
dbo:wikiPageID
Wikipage revision ID
dbo:wikiPageWikiLink
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software