Graph-Zeichnung ist ein Gebiet von Mathematik- und Informatik-Kombinieren-Methoden aus der geometrischen Graph-Theorie und Informationsvergegenwärtigung, um zweidimensionale Bilder von Graphen abzuleiten, die aus Anwendungen wie soziale Netzanalyse, Kartenzeichnen und bioinformatics entstehen.

Eine Zeichnung eines Graphen oder Netzwerkdiagramm sind eine bildliche Darstellung der Scheitelpunkte und Ränder eines Graphen. Diese Zeichnung sollte mit dem Graphen selbst nicht verwirrt sein: Sehr verschiedene Lay-Outs können demselben Graphen entsprechen. Im Auszug, alles, was Sachen sind, welche Paar-Scheitelpunkte durch Ränder verbunden werden. Im Beton, jedoch, betrifft die Einordnung dieser Scheitelpunkte und Ränder innerhalb einer Zeichnung seine Verständlichkeit, Brauchbarkeit, Herstellungskosten und Ästhetik. Das Problem wird schlechter, wenn sich der Graph mit der Zeit durch das Hinzufügen und das Löschen von Rändern ändert (dynamische Graph-Zeichnung) und die Absicht ist, die geistige Karte des Benutzers zu bewahren.

Grafische Vereinbarung

Graphen werden oft als Knotenverbindungsdiagramme gezogen, in denen die Scheitelpunkte als Platten oder Kästen vertreten werden und die Ränder als Liniensegmente, Polylinien oder Kurven im Euklidischen Flugzeug vertreten werden.

Im Fall von geleiteten Graphen bilden Pfeilspitzen eine allgemein verwendete grafische Tagung, ihre Orientierung zu zeigen; jedoch haben Benutzerstudien gezeigt, dass andere Vereinbarung wie das Zuspitzen diese Auskunft effektiver gibt.

Die alternative Vereinbarung zu Knotenverbindungsdiagrammen schließt Angrenzen-Darstellungen wie Kreisverpackung ein, in der Scheitelpunkte durch zusammenhanglose Gebiete im Flugzeug vertreten werden und Ränder durch das Angrenzen zwischen Gebieten vertreten werden; Kreuzungsdarstellungen, in denen Scheitelpunkte durch nichtzusammenhanglose geometrische Gegenstände und Ränder vertreten werden, werden durch ihre Kreuzungen vertreten; Sichtbarkeitsdarstellungen, in denen Scheitelpunkte durch Gebiete im Flugzeug und den Rändern vertreten werden, werden durch Gebiete vertreten, die eine unversperrte Gesichtslinie zu einander haben; zusammenfließende Zeichnungen, in denen Ränder als glatte Kurven innerhalb von mathematischen Zugspuren vertreten werden; und Vergegenwärtigungen der Angrenzen-Matrix des Graphen.

Qualitätsmaßnahmen

Viele verschiedene Qualitätsmaßnahmen sind für Graph-Zeichnungen in einem Versuch definiert worden, objektive Mittel zu finden, ihre Ästhetik und Brauchbarkeit zu bewerten. Zusätzlich zum Führen der Wahl zwischen verschiedenen Lay-Out-Methoden für denselben Graphen versuchen einige Lay-Out-Methoden, diese Maßnahmen direkt zu optimieren.

• Die sich treffende Zahl einer Zeichnung ist die Zahl von Paaren von Rändern, die einander durchqueren. Wenn der Graph planar ist, dann ist es häufig günstig, es ohne irgendwelche Rand-Kreuzungen zu ziehen; d. h. in diesem Fall vertritt eine Graph-Zeichnung ein Graph-Einbetten. Jedoch entstehen nichtplanare Graphen oft in Anwendungen, so müssen Graph-Zeichnungsalgorithmen allgemein Rand-Überfahrten berücksichtigen.
• Das Gebiet einer Zeichnung ist die Größe seines kleinsten begrenzenden Kastens hinsichtlich der nächsten Entfernung zwischen irgendwelchen zwei Scheitelpunkten. Zeichnungen mit dem kleineren Gebiet sind denjenigen mit dem größeren Gebiet allgemein vorzuziehend, weil sie den Eigenschaften der Zeichnung erlauben, an der größeren Größe und deshalb mehr leserlich gezeigt zu werden. Das Aspekt-Verhältnis des begrenzenden Kastens kann auch wichtig sein.
• Symmetrie-Anzeige ist das Problem, Symmetrie-Gruppen innerhalb eines gegebenen Graphen zu finden, und eine Zeichnung zu finden, die so viel der Symmetrie wie möglich zeigt. Einige Lay-Out-Methoden führen automatisch zu symmetrischen Zeichnungen; wechselweise fangen einige Zeichnungsmethoden durch die Entdeckung symmetries im Eingangsgraphen und das Verwenden von ihnen an, um eine Zeichnung zu bauen.
• Es ist wichtig, dass Ränder Gestalten haben, die so einfach sind wie möglich, es leichter für das Auge zu machen, ihnen zu folgen. In Polylinienzeichnungen kann die Kompliziertheit eines Randes durch seine Zahl von Kurven gemessen werden, und viele Methoden haben zum Ziel, Zeichnungen mit wenigen Gesamtkurven oder wenigen Kurven pro Rand zu versorgen. Ähnlich für Spline-Kurven kann die Kompliziertheit eines Randes durch die Zahl von Kontrollpunkten am Rand gemessen werden.
• Mehrere allgemein verwendete Qualität misst Sorge-Längen von Rändern: Es ist allgemein wünschenswert, die Gesamtlänge der Ränder sowie die maximale Länge jedes Randes zu minimieren. Zusätzlich kann es für die Längen von Rändern vorzuziehend sein, gleichförmig aber nicht hoch verschieden zu sein.
• Winkelige Entschlossenheit ist ein Maß der schärfsten Winkel in einer Graph-Zeichnung. Wenn ein Graph Scheitelpunkte mit dem hohen Grad dann hat, wird es notwendigerweise kleine winkelige Entschlossenheit haben, aber die winkelige Entschlossenheit kann unten durch eine Funktion des Grads begrenzt werden.

Lay-Out-Methoden

Es gibt viele verschiedene Graph-Lay-Out-Strategien:

• In Kraft-basierten Lay-Out-Systemen modifiziert die Graph-Zeichnungssoftware ein anfängliches Scheitelpunkt-Stellen durch das dauernde Bewegen der Scheitelpunkte gemäß einem System von Kräften, die auf physischen Metaphern gestützt sind, die mit Systemen von Frühlingen oder molekularer Mechanik verbunden sind. Gewöhnlich verbinden diese Systeme attraktive Kräfte zwischen angrenzenden Scheitelpunkten mit abstoßenden Kräften zwischen allen Paaren von Scheitelpunkten, um ein Lay-Out zu suchen, in dem Rand-Längen klein sind, während Scheitelpunkte gut getrennt werden. Diese Systeme können leisten Anstieg-Abstieg hat Minimierung einer Energiefunktion gestützt, oder sie können die Kräfte direkt in Geschwindigkeiten oder Beschleunigungen für die bewegenden Scheitelpunkte übersetzen.
• Der geisterhafte Lay-Out-Methode-Gebrauch als Koordinaten die Eigenvektoren einer Matrix wie Laplacian ist auf die Angrenzen-Matrix des Graphen zurückzuführen gewesen.
• Orthogonale Lay-Out-Methoden, die den Rändern des Graphen erlauben, horizontal oder vertikal zu laufen, passen zu den Koordinatenäxten des Lay-Outs an. Diese Methoden wurden für VLSI und PCB Lay-Out-Probleme ursprünglich entworfen, aber sie sind auch an die Graph-Zeichnung angepasst worden. Sie schließen normalerweise eine mehrphasige Annäherung ein, in der ein Eingangsgraph planarized durch das Ersetzen von sich treffenden Punkten durch Scheitelpunkte ist, wird ein topologisches Einbetten des planarized Graphen gefunden, Rand-Orientierungen werden gewählt, um Kurven zu minimieren, Scheitelpunkte werden im Einklang stehend diese Orientierungen gelegt, und schließlich reduziert ein Lay-Out compaction Bühne das Gebiet der Zeichnung.
• Baumlay-Out-Algorithmen zeigen diese eine eingewurzelte baumähnliche Bildung, die für Bäume passend ist. Häufig, in einer Technik genannt "Ballon-Lay-Out", werden die Kinder jedes Knotens im Baum ein Kreis angezogen, der den Knoten mit den Radien dieser Kreise umgibt, die sich an niedrigeren Ebenen im Baum vermindern, so dass diese Kreise nicht überlappen.
• Graph-Zeichnungsmethoden von Layered (hat häufig Sugiyama-artige Zeichnung genannt), wird am besten für geleitete acyclic Graphen oder Graphen angepasst, die fast acyclic, wie die Graphen von Abhängigkeiten zwischen Modulen oder Funktionen in einem Softwaresystem sind. In diesen Methoden werden die Knoten des Graphen in horizontale Schicht-Verwenden-Methoden wie der Algorithmus von Coffman-Graham auf solche Art und Weise eingeordnet, dass die meisten Ränder abwärts von einer Schicht bis das folgende gehen; nach diesem Schritt werden die Knoten innerhalb jeder Schicht eingeordnet, um Überfahrten zu minimieren.
• Kreisförmige Lay-Out-Methoden legen die Scheitelpunkte des Graphen auf einem Kreis, sorgfältig die Einrichtung der Scheitelpunkte um den Kreis wählend, um Überfahrten zu reduzieren und angrenzende Scheitelpunkte in der Nähe von einander zu legen. Ränder können entweder als Akkorde des Kreises oder als Kreisbogen innerhalb oder außerhalb des Kreises gezogen werden. In einigen Fällen können vielfache Kreise verwendet werden.

Anwendungsspezifische Graph-Zeichnungen

Graphen und Graph-Zeichnungen, die in anderen Gebieten der Anwendung entstehen, schließen ein

• Sociograms, Zeichnungen eines sozialen Netzes, wie häufig angeboten, durch die soziale Netzanalyse-Software
• Diagramme von Hasse, ein Typ der Graph-Zeichnung hat sich zu teilweisen Ordnungen spezialisiert
• Dessin d'enfants, ein Typ der Graph-Zeichnung, die in der algebraischen Geometrie verwendet ist
• Zustandsdiagramme, grafische Darstellungen von Zustandsmaschinen
• Computernetzwerkdiagramme, Bilder der Knoten und Verbindungen in einem Computernetz.
• Fluss-Karten, Zeichnungen, in denen die Knoten die Schritte eines Algorithmus und der Ränder vertreten, vertreten Kontrollfluss zwischen Schritten.
• Datenflussschemen, Zeichnungen, in denen die Knoten die Bestandteile eines Informationssystems und der Ränder vertreten, vertreten die Bewegung der Information von einem Bestandteil bis einen anderen.

Außerdem sind das Stellen und die Routenplanungsschritte der elektronischen Designautomation auf viele Weisen zur Graph-Zeichnung ähnlich, und die Graph-Zeichnungsliteratur schließt mehrere von der EDA Literatur geliehene Ergebnisse ein. Jedoch unterscheiden sich diese Probleme auch auf mehrere wichtige Weisen: Zum Beispiel, in EDA, sind Bereichsminimierung und Signallänge wichtiger als Ästhetik, und das Routenplanungsproblem in EDA kann mehr als zwei Terminals pro Netz haben, während das analoge Problem im Graphen, der allgemein nur zieht, Paare von Scheitelpunkten für jeden Rand einbezieht.

Software

Software, Systeme und Versorger von Systemen, um Graphen zu ziehen, schließen ein:

• Graphviz, ein Graph-Zeichnungssystem der offenen Quelle von

AT&T

• yEd, ein weit verbreiteter Graph-Redakteur mit der Graph-Lay-Out-Funktionalität
• Microsoft Automatic Graph Layout, eine.NET Bibliothek (früher genannte HEITERKEIT), um Graphen anzulegen
• Software von Tom Sawyer
• Tulpe (Software)
• Gephi, eine Netzanalyse- und Vergegenwärtigungssoftware der offenen Quelle

Referenzen

....................

• .

Außenverbindungen

• Graph, der E-Druckarchiv anzieht: einschließlich der Information über Papiere von allen Graph-Zeichnungssymposien.

• für viele zusätzliche mit der Graph-Zeichnung verbundene Verbindungen.