Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Konvex planarer Graph
Autor
Universität/Hochschule Konvex planarer Graph
Noskar
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.01.2022
Mitteilungen: 3
  Themenstart: 2022-02-03

Auf https://en.wikipedia.org/wiki/Planar_graph findet man folgenden Satz: A plane graph is said to be convex if all of its faces (including the outer face) are convex polygons. A planar graph may be drawn convexly if and only if it is a subdivision of a 3-vertex-connected planar graph. Ich bin der Meinung, das ist falsch. Ich habe einen konvex einbettbaren Graphen, der die Unterteilung von keinem anderen Graphen sein kann (hat keinen Vertex mit Grad <=2) und definitiv nicht 2-verbunden ist: https://matheplanet.com/matheplanet/nuke/html/uploads/b/55336_convex_graph.png Liege ich richtig?


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8014
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2022-02-03

Hallo Noskar, erst einmal willkommen auf dem Matheplaneten! \quoteon(2022-02-03 15:53 - Noskar im Themenstart) A plane graph is said to be convex if all of its faces (including the outer face) are convex polygons. A planar graph may be drawn convexly if and only if it is a subdivision of a 3-vertex-connected planar graph. \quoteoff Das hört sich tatsächlich merkwürdig an. Aber vielleicht habe ich die Definition für einen konvexen planaren Graphen noch nicht ganz verstanden. Könntest du vielleicht mal eine Beispiel für einen planaren Graphen geben, der nicht konvex ist?


   Profil
Noskar
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.01.2022
Mitteilungen: 3
  Beitrag No.2, vom Themenstarter, eingetragen 2022-02-04

Ich habe überall die gleiche Definition gefunden: A plane graph is said to be convex if all of its faces (including the outer face) are convex polygons. In einem Paper habe ich nun endlich auch einen planaren Graphen gefunden, der nicht konvex ist. Ich hatte es irgendwie nicht geschafft...: $K_{2,4}$: https://matheplanet.com/matheplanet/nuke/html/uploads/b/55336_K_2_4.png Aber zurück zu meinem Beispiel vom ersten Post: Da es keinen Vertex mit Grad 2 besitzt, ist der Graph keine Unterteilung eines anderen Graphen. Das Löschen der beiden linken Verices im Quadrat lässt ihn in zwei Zusammenhangskomponenten zerfallen. Also ist der Graph nicht 3-verbunden. Also ist der planar, aber nicht die Unterteilung eines 3-verbundenen Graphen. Ich denke, falls niemand einen Fehler in dieser Logik entdeckt, werde ich den Abschnitt auf en.wikipedia.org/wiki/Planar_graph löschen... Bzw. nicht löschen, sondern das 'if and only if' durch ein 'if' ersetzen. Diese Implikation stimmt nämlich, dieses Resultat findet man überall in der Literatur.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8014
Wohnort: Milchstraße
  Beitrag No.3, eingetragen 2022-02-04

Danke fürs Beispiel. War ja doch nicht so kompliziert 🙃 Ich sehe nichts, was gegen deine Logik spricht. Zudem im Lemma Convex drawing dieses Kriterium nicht erwähnt wird.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8014
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2022-02-04

Ich habe gesehen, dass du den Wikipedia-Artikel nun (bisher widerspruchslos) korrigiert hast. 👍 Du könntest ja noch 1. das Beispiel \(K_{2,4}\) sowie 2. deine geänderte Formulierung im Lemma "Convex Drawing" unterbringen.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8997
Wohnort: Westerburg
  Beitrag No.5, eingetragen 2022-02-04

\quoteon(2022-02-04 22:48 - StrgAltEntf in Beitrag No. 4) Ich habe gesehen, dass du den Wikipedia-Artikel nun (bisher widerspruchslos) korrigiert hast. 👍 \quoteoff David Eppstein wird sich schon melden, wenn es da etwas zu bemängeln gibt. Ihn könnte man auch direkt fragen.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8014
Wohnort: Milchstraße
  Beitrag No.6, eingetragen 2022-02-05

\quoteon(2022-02-04 22:52 - Slash in Beitrag No. 5) David Eppstein wird sich schon melden, wenn es da etwas zu bemängeln gibt. Ihn könnte man auch direkt fragen. \quoteoff @Slash: Hat David Eppstein diesen Satz in Wikipedia eingebracht?


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8997
Wohnort: Westerburg
  Beitrag No.7, eingetragen 2022-02-05

\quoteon(2022-02-05 10:53 - StrgAltEntf in Beitrag No. 6) \quoteon(2022-02-04 22:52 - Slash in Beitrag No. 5) David Eppstein wird sich schon melden, wenn es da etwas zu bemängeln gibt. Ihn könnte man auch direkt fragen. \quoteoff @Slash: Hat David Eppstein diesen Satz in Wikipedia eingebracht? \quoteoff Eppstein ist einfach ein sehr guter Mathematiker, der an vielen Wiki-Artikeln mitwirkt, auch an diesem. Diskrete Geometrie und Graphentheorie gehören zu seinen Spezialgebieten. Er wird die neue Änderung sichten und für richtig oder falsch befinden.


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 8014
Wohnort: Milchstraße
  Beitrag No.8, eingetragen 2022-02-05

Habe mal die History durchforscht. Tatsächlich war es Eppstein, der am 15.09.09 01:43 den Satz ergänzt hat.


   Profil
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 8997
Wohnort: Westerburg
  Beitrag No.9, eingetragen 2022-02-05

Eppstein wird auch bestimmt s(eine) genaue Erklärung liefern, wenn man (ihn) auf der entsprechenden Diskussionsseite danach fragt. Man kann auch allgemein fragen, aber er wird dann darauf antworten, da er den Satz ergänzt hat.


   Profil
Noskar hat die Antworten auf ihre/seine Frage gesehen.
Noskar wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]