Diagramme mit wenigen „scharfen“ Scheitelpunkten zeichnen?

Definieren Sie für eine planare Einbettung eines planaren Graphen in eine Ebene mit geraden Kanten einen Scheitelpunkt als scharfen Scheitelpunkt, wenn der maximale Winkel zwischen zwei aufeinander folgenden Kanten um ihn herum mehr als 180 beträgt Scheitelpunkt in der Einbettung so, dass alle Kanten, die auf diesen Scheitelpunkt fallen, auf einer Seite der Linie liegen, dann ist der Scheitelpunkt "scharf", andernfalls nicht. Sorgen wir uns auch nur um Scheitelpunkte mit einem Grad von mindestens 3.

Ich möchte ebene Graphen mit wenigen scharfen Scheitelpunkten zeichnen. Hat jemand solche Zeichnungen schon einmal studiert?

Insbesondere möchte ich ebene Graphen mit maximalem Grad 3 zeichnen, so dass die Anzahl der scharfen Scheitelpunkte mit Grad 3 in der Einbettung und die Koordinaten der Scheitelpunkte mit einer polynomiellen Anzahl von Bits notiert werden können.$O(\log n)$

Folgendes kann ich nach einiger Zeit bei Google Scholar finden:

Mein Maß für die Schärfe eines Scheitelpunkts hängt mit einem bereits untersuchten Konzept zusammen, das als Winkelauflösung bezeichnet wird . Aus Wikipedia:

Die Winkelauflösung einer Zeichnung eines Graphen bezieht sich auf den schärfsten Winkel, der von zwei Kanten gebildet wird, die sich an einem gemeinsamen Scheitelpunkt der Zeichnung treffen.

Daher ist eine ebene Zeichnung mit einer Winkelauflösung von um Scheitelpunkte des Grades 3 für meinen Zweck gut.$\pi/2$

Für einen Scheitelpunkt mit dem Grad in der Zeichnung kann die Winkelauflösung um ihn herum höchstens 2 & pgr; / d betragen .$d$$2\pi/d$

Die Frage, ob dies eng ist, wurde in der Vergangenheit untersucht, aber ich kann nur asymptotische Ergebnisse finden. Malitz und Papakostas beweisen beispielsweise, dass jeder ebene Graph mit maximalem Grad mit einer Winkelauflösung von α d gezeichnet werden kann . Aber dieses Ergebnis gibt keine guten Grenzen für den Fall, wenn d = 3 ist .$d$$\alpha^d$$d=3$

$\Theta(n)$

Wenn Sie dagegen eine höhere Konnektivitätsebene benötigen, können Sie viele scharfe Scheitelpunkte vermeiden. Insbesondere wenn Sie einen planaren Graphen mit drei Verknüpfungen haben, kann dieser so gezeichnet werden (z. B. durch Verwendung des Steinitz-Theorems, um eine polyedrische Darstellung zu finden und dann eine perspektivische Projektion zu bilden), dass alle Flächen konvex sind, was nur das bewirkt Außenfläche scharf zu sein. Jeder dreifach zusammenhängende planare Graph kann jedoch so eingebettet werden, dass die Außenfläche höchstens fünf Eckpunkte aufweist (der schlimmste Fall ist ein Dodekaeder), sodass Sie jeden dreifach zusammenhängenden planaren Graphen (dreifach regelmäßig oder nicht) mit at zeichnen können die meisten fünf scharfen Ecken.