Grafikzeichnung

Grafische Darstellung eines winzigen Bruchteils der Www, Demonstration Hyperlinks.

Grafikzeichnung ist ein Bereich von Mathematik und Informatik Kombinieren von Methoden von Geometrische Graphentheorie und Informationsvisualisierung zweidimensionale Darstellungen von abzuleiten Grafiken aus Anwendungen wie z. Analyse des sozialen Netzwerks, Kartographie, Linguistik, und Bioinformatik.[1]

Eine Zeichnung einer Grafik oder netzwerkdiagramm ist eine bildliche Darstellung der Eckpunkte und Kanten einer Grafik. Diese Zeichnung sollte nicht mit dem Diagramm selbst verwechselt werden: Sehr unterschiedliche Layouts können demselben Diagramm entsprechen.[2] In der Zusammenfassung ist alles, was zählt, welche Eckpaare durch Kanten verbunden sind. Im Beton wirkt sich jedoch die Anordnung dieser Eckpunkte und Kanten innerhalb einer Zeichnung auf die Verständlichkeit, die Benutzerfreundlichkeit, die Herstellungskosten und beeinflusst Ästhetik.[3] Das Problem wird schlechter, wenn sich das Diagramm im Laufe der Zeit ändert, indem Kanten hinzugefügt und gelöscht (dynamisches Diagrammzeichnung), und das Ziel ist es, die mentale Karte des Benutzers zu erhalten.[4]

Grafische Konventionen

Gerichteter Graph Mit Pfeilspitzen, die Kantenrichtungen zeigen

Diagramme werden häufig als Knoten -Link -Diagramme gezeichnet, in denen die Scheitelpunkte als Scheiben, Kästchen oder Textbezeichnungen dargestellt werden, und die Kanten werden als dargestellt als Liniensegmente, Polylines, oder Kurven in der Euklidische Ebene.[3] Node-Link-Diagramme können auf die Werke von Pseudo-Lull aus dem 14. bis 16. Jahrhundert zurückgeführt werden, die unter dem Namen von veröffentlicht wurden Ramon Llull, ein Polymath des 13. Jahrhunderts. Pseudo-Lull zog Diagramme dieser Art für Komplette Diagramme um alle paarweisen Kombinationen zwischen Metaphysischen -Konzepten zu analysieren.[5]

Im Falle des Regie Graphen, Pfeilspitzen bilden eine häufig verwendete grafische Konvention, um ihre zu zeigen Orientierung;[2] Benutzerstudien haben jedoch gezeigt, dass andere Konventionen wie das Verjüngen diese Informationen effektiver liefern.[6] Aufwärts planare Zeichnung Verwendet die Konvention, dass jede Kante von einem unteren Scheitelpunkt bis zu einem höheren Scheitelpunkt ausgerichtet ist, was Pfeilspitzen unnötig macht.[7]

Alternative Konventionen zu Node -Link -Diagrammen umfassen Adjazenzdarstellungen wie z. Kreispackungen, in denen Scheitelpunkte durch disjunkte Regionen in der Ebene und die Kanten durch Angrenzungen zwischen Regionen dargestellt werden; Kreuzungsdarstellungen in denen Scheitelpunkte durch nicht disjunkte geometrische Objekte und Kanten durch ihre Schnittpunkte dargestellt werden; Sichtbarkeitsdarstellungen, in denen Scheitelpunkte durch Regionen in der Ebene und Kanten dargestellt werden, werden durch Regionen dargestellt, die eine ungehinderte Sichtlinie zueinander haben; Konfluente Zeichnungen, in denen die Kanten als glatte Kurven in mathematischer Darstellung dargestellt werden Schienen; Stoffe, in denen Knoten als horizontale Linien und Kanten als vertikale Linien dargestellt werden;[8] und Visualisierungen der Adjazenzmatrix der Grafik.

Qualitätsmaßnahmen

Für Grafikzeichnungen wurden viele verschiedene Qualitätsmaßnahmen definiert, um objektive Mittel zur Bewertung ihrer Ästhetik und Benutzerfreundlichkeit zu finden.[9] Einige Layout -Methoden versuchen nicht nur, die Auswahl zwischen verschiedenen Layoutmethoden für dasselbe Diagramm zu leiten, sondern auch diese Maßnahmen direkt optimieren.

Planare Graph gezeichnet ohne überlappende Kanten
  • Das Kreuzungsnummer einer Zeichnung ist die Anzahl der Kantenpaare, die sich gegenseitig überqueren. Wenn die Grafik ist Planardann ist es oft bequem, es ohne Kantenkreuzungen zu zeichnen. Das heißt in diesem Fall eine Diagrammzeichnung darstellt a Grafikeinbettung. In Anwendungen entstehen jedoch häufig nicht planare Graphen, sodass Diagrammzeichnungsalgorithmen im Allgemeinen Kantenübergänge ermöglichen.[10]
  • Das Bereich einer Zeichnung ist die Größe ihrer kleinsten Begrenzungsbox, relativ zum engsten Abstand zwischen zwei beliebigen Eckpunkten. Zeichnungen mit kleineren Flächen sind im Allgemeinen denen mit größerem Bereich vorzuziehen, da sie ermöglichen, dass die Merkmale der Zeichnung in größerer Größe und damit lesbarer angezeigt werden. Das Seitenverhältnis des Begrenzungsboxs kann auch wichtig sein.
  • Die Symmetrieanzeige ist das Problem des Findens Symmetriegruppen Innerhalb eines bestimmten Diagramms und das Finden einer Zeichnung, die so viel von der Symmetrie wie möglich anzeigt. Einige Layoutmethoden führen automatisch zu symmetrischen Zeichnungen. Alternativ werden einige Zeichnungsmethoden zunächst Symmetrien im Eingangsdiagramm gefunden und sie verwenden, um eine Zeichnung zu konstruieren.[11]
  • Es ist wichtig, dass Kanten Formen haben, die so einfach wie möglich sind, um es dem Auge zu erleichtern, ihnen zu folgen. In Polyline -Zeichnungen kann die Komplexität einer Kante anhand seiner gemessen werden Anzahl der Biegungenund viele Methoden zielen darauf ab, Zeichnungen mit nur wenigen Biegungen oder nur wenigen Biegungen pro Kante bereitzustellen. In ähnlicher Weise kann für Spline -Kurven die Komplexität einer Kante anhand der Anzahl der Kontrollpunkte am Rand gemessen werden.
  • Mehrere häufig verwendete Qualitätsmessungen betreffen die Längen der Kanten: Es ist im Allgemeinen wünschenswert, die Gesamtlänge der Kanten sowie die maximale Länge einer beliebigen Kante zu minimieren. Darüber hinaus kann es vorzuziehen sein, dass die Längen der Kanten eher einheitlich als sehr unterschiedlich sein.
  • Winkelauflösung ist ein Maß für die schärfsten Winkel in einer Diagrammzeichnung. Wenn ein Diagramm Scheitelpunkte mit hoher hat Grad Dann wird es notwendigerweise eine geringe Winkelauflösung haben, aber die Winkelauflösung kann durch eine Funktion des Grades unten begrenzt werden.[12]
  • Das Hangnummer Von einem Diagramm ist die minimale Anzahl unterschiedlicher Kantenhänge, die in einer Zeichnung mit geraden Segmentkanten benötigt werden (Kreuzungen). Kubikdiagramme Die Neigungsnummer höchstens vier haben, aber Diagramme von Grad Fünf haben möglicherweise eine unbegrenzte Neigungszahl; Es bleibt offen, ob die Steigungszahl der Grad-4-Diagramme begrenzt ist.[12]

Layoutmethoden

Eine Kraft-basierte Netzwerkvisualisierung.[13]

Es gibt viele verschiedene Grafiklayoutstrategien:

  • Im Force-basierte Layout Systeme, die Diagrammzeichnungssoftware verändert eine anfängliche Vertex -Platzierung, indem die Scheitelpunkte kontinuierlich verschoben werden Federn oder Molekulare Mechanik. Typischerweise kombinieren diese Systeme attraktive Kräfte zwischen benachbarten Scheitelpunkten mit abstoßenden Kräften zwischen allen Eckpaaren, um ein Layout zu suchen, in dem die Kantenlängen klein sind, während die Scheitelpunkte gut getrennt sind. Diese Systeme können durchführen Gradientenabstieg basierende Minimierung von a Energiefunktionoder sie können die Kräfte direkt in Geschwindigkeiten oder Beschleunigungen für die sich bewegenden Eckpunkte übersetzen.[14]
  • Spektrallayout Methoden verwenden als Koordinaten die Eigenvektoren von a Matrix so wie die Laplace abgeleitet von der Adjazenzmatrix der Grafik.[15]
  • Orthogonale Layoutmethoden, mit denen die Kanten des Diagramms horizontal oder vertikal ausführen können, parallel zu den Koordinatenachsen des Layouts. Diese Methoden wurden ursprünglich für für VLSI und PCB Layoutprobleme, aber sie wurden auch für die Grafikzeichnung angepasst. Sie beinhalten typischerweise einen Mehrphasenansatz, bei dem ein Eingangsdiagramm planarisiert wird, indem Kreuzungspunkte durch Scheitelpunkte ersetzt werden, eine topologische Einbettung des planarisierten Diagramms, Kantenorientierungen ausgewählt werden Die Verdichtungsstufe reduziert den Bereich der Zeichnung.[16]
  • Baumlayoutalgorithmen Diese zeigen eine verwurzelte Baum-ähnliche Formation, geeignet für Bäume. In einer Technik namens "Ballonlayout" werden die Kinder jedes Knotens im Baum häufig auf einem Kreis gezeichnet, der den Knoten umgibt, wobei die Radien dieser Kreise in niedrigeren Ebenen im Baum abnehmen, so dass sich diese Kreise nicht überlappen.[17]
  • Layered Graph Drawing Methoden (oft als Zeichnung im Sugiyama-Stil bezeichnet) eignen sich am besten für Regie acyclische Graphen oder Grafiken, die nahezu acyclisch sind, wie z. In diesen Methoden werden die Knoten des Diagramms unter Verwendung von Methoden wie dem in horizontale Schichten angeordnet Coffman -Graham -Algorithmusso, dass die meisten Kanten von einer Schicht zur nächsten nach unten gehen; Nach diesem Schritt werden die Knoten in jeder Schicht angeordnet, um Kreuzungen zu minimieren.[18]
ARC -Diagramm
  • Bogendiagramme, ein Layoutstil aus den 1960er Jahren,[19] Scheitelpunkte auf eine Linie legen; Kanten können als Halbkreise über oder unter der Linie oder als glatte Kurven aus mehreren Halbkreisen gezeichnet werden.
  • Rundlayout Methoden platzieren die Eckpunkte des Graphen in einem Kreis und wählen sorgfältig die Reihenfolge der Eckpunkte um den Kreis, um Kreuzungen zu reduzieren und benachbarte Scheitelpunkte nahe beieinander zu platzieren. Kanten können entweder als Akkorde des Kreises oder als Bögen innerhalb oder außerhalb des Kreises gezeichnet werden. In einigen Fällen können mehrere Kreise verwendet werden.[20]
  • Dominanzzeichnung platziert Scheitelpunkte so, dass ein Scheitelpunkt nach oben, rechts oder beides von einem anderen ist, wenn es nur dann ist, wenn es sich erreichbar von dem anderen Scheitelpunkt. Auf diese Weise macht der Layoutstil die Erreichbarkeitsbeziehung des Diagramms visuell erkennbar.[21]

Anwendungsspezifische Grafikzeichnungen

Grafiken und Diagrammzeichnungen, die in anderen Anwendungsbereichen entstehen

zusätzlich Platzierung und Routing Schritte von elektronische Designautomatisierung (EDA) sind in vielerlei Hinsicht wie das Problem der Grafik ähnlich, ebenso wie das Problem von gierige Einbettung in verteiltes Computerund die Graph -Zeichnungsliteratur enthält mehrere Ergebnisse, die aus der EDA -Literatur entlehnt wurden. Diese Probleme unterscheiden sich jedoch auch auf verschiedene wichtige Weise: Beispielsweise sind in der EDA die Flächenminimierung und die Signallänge wichtiger als die Ästhetik, und das Routing -Problem in EDA kann mehr als zwei Klemmen pro Netz haben, während das analoge Problem in der Grafikzeichnung im Allgemeinen allgemein ist Beinhaltet nur Paare von Eckpunkten für jede Kante.

Software

Eine Grafikzeichnungsschnittstelle (Gephi 0.9.1)

Software, Systeme und Anbieter von Systemen zum Zeichnen von Grafiken umfassen:

  • Biofabric Open-Source-Software zur Visualisierung großer Netzwerke durch Zeichnen von Knoten als horizontale Linien.
  • Zytoscape, Open-Source-Software zur Visualisierung molekularer Interaktionsnetzwerke
  • Gephi, Open-Source-Netzwerkanalyse- und Visualisierungssoftware
  • Graph-Tool, a kostenlos/libre Python Bibliothek zur Analyse von Graphen.
  • Graphviz, ein Open-Source-Graph-Zeichnungssystem von AT&T Corporation[28]
  • Linkurious, eine kommerzielle Netzwerkanalyse- und Visualisierungssoftware für Grafikdatenbanken
  • Mathematica, ein Allzweck -Berechnungstool, das 2D- und 3D -Graph -Visualisierungs- und Graphenanalyse -Tools enthält.[29][30]
  • Microsoft Automatic Graph Layout, Open-Source .NET-Bibliothek (früher Glee genannt) zum Auslegen von Diagramme[31]
  • NetworkX ist eine Python -Bibliothek zum Studium von Grafiken und Netzwerken.
  • Tulip (Software),[32] Ein Tool zur Visualisierung von Open -Source -Daten zur Visualisierung
  • yed, ein Graph -Editor mit Graph -Layout -Funktionalität[33]
  • PGF/Tikz 3.0 mit dem Graphdrawing Paket (erfordert Luatex).[34]
  • Lanet-vi, eine Open-Source-Software für große Netzwerkvisualisierungssoftware
  • EDRAW MAX 2D Business Technical Diagramming Software

Siehe auch

Verweise

Fußnoten
  1. ^ Di Battista et al. (1994), S. vii -viii; Herman, Melançon & Marshall (2000), Abschnitt 1.1, "Typische Anwendungsbereiche".
  2. ^ a b Di Battista et al. (1994), p. 6.
  3. ^ a b Di Battista et al. (1994), p. viii.
  4. ^ MISEE et al. (1995)
  5. ^ Knuth, Donald E. (2013), "zweitausend Jahre Kombinatorik", in Wilson, Robin; Watkins, John J. (Hrsg.), Kombinatorik: Alt und modern, Oxford University Press, S. 7–37.
  6. ^ Holten & Van Wijk (2009); Holten et al. (2011).
  7. ^ Garg & Tamassia (1995).
  8. ^ Longabaugh (2012).
  9. ^ Di Battista et al. (1994), Abschnitt 2.1.2, Ästhetik, S. 14–16; Kauf, Cohen & James (1997).
  10. ^ Di Battista et al. (1994), S. 14.
  11. ^ Di Battista et al. (1994), p. 16.
  12. ^ a b Pach & Sharir (2009).
  13. ^ Veröffentlicht in Grandjean, Martin (2014). "La Connaissance Est un réseau". Les Cahiers du Numérique. 10 (3): 37–54. doi:10.3166/lcn.10.3.37-54. Abgerufen 2014-10-15.
  14. ^ Di Battista et al. (1994), Abschnitt 2.7, "Der Kraft-gerichtete Ansatz", S. 29–30, und Kapitel 10, "Force Directed Methods", S. 303–326.
  15. ^ Beckman (1994); Koren (2005).
  16. ^ Di Battista et al. (1994), Kapitel 5, "Flow und orthogonale Zeichnungen", S. 137–170; (Eiglsperger, Fekete & Klau 2001).
  17. ^ Herman, Melançon & Marshall (2000), Abschnitt 2.2, "Traditionelles Layout - eine Übersicht".
  18. ^ Sugiyama, Tagawa & Toda (1981); Bastert & Matuszewski (2001); Di Battista et al. (1994), Kapitel 9, "Schichtzeichnungen von Digraphen", S. 265–302.
  19. ^ Saaty (1964).
  20. ^ Doğrusöz, Madden & Madden (1997).
  21. ^ Di Battista et al. (1994), Abschnitt 4.7, "Dominanzzeichnungen", S. 112–127.
  22. ^ Scott (2000); Brandes, Freeman & Wagner (2014).
  23. ^ Di Battista et al. (1994), S. 15–16, und Kapitel 6, "Flow and Upward Planarity", S. 171–214; Freese (2004).
  24. ^ Zapponi (2003).
  25. ^ Anderson & Head (2006).
  26. ^ Di Battista & Rimondini (2014).
  27. ^ Bachmaier, Brandes & Schreiber (2014).
  28. ^ "Graphviz und Dynagraph - Statische und dynamische Diagramm -Zeichnungswerkzeuge", von John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North und Gordon Woodhull, IN Jünger & Mühlen (2004).
  29. ^ Graphplot Mathematica -Dokumentation
  30. ^ Grafikzeichnung Tutorial
  31. ^ Nachmanson, Robertson & Lee (2008).
  32. ^ "Tulip - ein riesiges Graph Visualisierungsrahmen", von David Auber, in Jünger & Mühlen (2004).
  33. ^ "YFILES - Visualisierung und automatisches Layout von Graphen", von Roland Wiese, Markus Eiglsperger und Michael Kaufmann, in Jünger & Mühlen (2004).
  34. ^ Tantau (2013); Siehe auch das ältere GD 2012 Präsentation
Allgemeine Referenzen
Spezialisierte Unterthemen

Externe Links