|
Graph Drawing
edit- Introduction
- Graph drawing – Visualization of node-link graphs
- Graph theory – Area of discrete mathematics
- Data and information visualization – Visual representation of data
- Undirected graph layouts
- Undirected graph – Vertices connected in pairs by edges
- Arc diagram – Graph drawing with vertices on a line
- Circular layout – Graph drawing with vertices on a circle
- Force-directed graph drawing – Physical simulation to visualize graphs
- Spectral layout – Graph drawing using eigenvector coordinates
- Stress majorization – Geometric placement based on ideal distances
- Directed graph layouts
- Directed graph – Graph with oriented edges
- Directed acyclic graph – Directed graph with no directed cycles
- Dominance drawing – Graph where coordinates show reachability
- Layered graph drawing – Graph drawing with vertices in horizontal layers
- Upward planar drawing – Graph with edges non-crossing and upward
- Tree layouts
- Tree – Undirected, connected and acyclic graph
- H tree – Right-angled fractal canopy
- Hyperbolic tree – Mathematical tree in the hyperbolic plane
- Radial tree – Mathematical tree on concentric circles
- Treemapping – Visualisation method for hierchical data
- Application-specific graph drawings
- Cartogram – Map distorting size to show another value
- Concept map – Diagram showing relationships among concepts
- Dendrogram – Diagram with a treelike structure
- Dessin d'enfant – Graph drawing used to study Riemann surfaces
- Hasse diagram – Visual depiction of a partially ordered set
- Sociogram – Graphic representation of social links
- State diagram – Diagram of behavior of finite state systems
- Syntax diagram – Visual description of context-free grammar
- Quality criteria
- Angular resolution – Sharpest angle between edges at a vertex
- Area – Size of bounding box of graph drawing
- Bend minimization – Graph drawing with few edge bends
- Crossing number – Fewest edge crossings in drawing of a graph
- Slope number – Number of edge slopes in graph drawing
- Planar graphs
- Planar graph – Graph that can be embedded in the plane
- Dual graph – Graph representing faces of another graph
- Fáry's theorem – Planar graphs have straight drawings
- Harborth's conjecture – On graph drawing with integer edge lengths
- Medial graph – Edge-face adjacencies in another graph
- Tutte embedding – Planar graph drawn by relaxing springs
- Convex drawing – Planar graph with convex polygon faces
- Universal point set – Points usable to draw any planar graph
- Planarity testing
- Planarity testing – Algorithmic problem of finding non-crossing drawings
- Left-right planarity test – Depth-first characterization of planar graphs
- Hanani–Tutte theorem – On parity of crossings in graph drawings
- Kuratowski's theorem – On forbidden subgraphs in planar graphs
- Mac Lane's planarity criterion – On cycle bases of planar graphs
- Schnyder's theorem – Order dimension of incidences in planar graphs
- Wagner's theorem – On forbidden minors in planar graphs
- Whitney's planarity criterion – Characterization of planar graphs by matroids
- Classes of planar graphs
- Apollonian network – Graph formed by subdivision of triangles
- Cactus graph – Mathematical tree of cycles
- Halin graph – Mathematical tree with cycle through leaves
- Outerplanar graph – Non-crossing graph with vertices on outer face
- Nested triangles graph – Planar graph used as counterexample
- Series–parallel graph – Recursively-formed graph with two terminal vertices
- Squaregraph – Planar graph with quadrilateral faces
- st-planar graph – Planar directed acyclic graph
- Subhamiltonian graph – Subgraph of planar graph with Hamiltonian cycle
- Wheel graph – Cycle graph plus universal vertex
- Beyond planarity
- Planarization – Technique for drawing non-planar graphs
- 1-planar graph – graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point with a single additional edge
- Apex graph – Graph which can be made planar by removing a single node
- Book embedding – Graph layout on multiple half-planes
- Clustered planarity
- Graph embedding – Embedding a graph in a topological space, often Euclidean
- Greedy embedding
- Linkless embedding – Embedding a graph in 3D space with no cycles interlinked
- RAC drawing – Graph theory representation
- Simultaneous embedding – technique in graph drawing
- Strangulated graph – Graph whose peripheral cycles are all triangles
- Thickness (graph theory) – the minimum number of planar graphs into which the edges of a graph can be partitioned
- Topological graph theory – Branch of the mathematical field of graph theory
- Toroidal graph – Graph able to be embedded on a torus
- Contact and intersection representations
- Intersection graph – Graph representing intersections between given sets
- Boxicity – Smallest dimension where a graph can be represented as an intersection graph of boxes
- Circle graph – Intersection graph of a chord diagram
- Circle packing theorem – Describes the possible tangency relations between circles with disjoint interiors
- Interval graph – Intersection graph for intervals on the real number line
- Scheinerman's conjecture – Mathematics theorem
- String graph – Intersection graph for curves in the plane
- Unit disk graph – Intersection graph of unit disks in the plane
- Other geometric representations of graphs
- Geometric graph theory – Subfield of graph theory
- Matchstick graph – Graph with edges of length one, able to be drawn without crossings
- Polyhedral graph – Graph made from vertices and edges of a convex polyhedron
- Steinitz's theorem – Graph-theoretic description of polyhedra
- Unit distance graph – Geometric graph with unit edge lengths
- Visibility graph
- Computer representations of graphs and drawings
- Graph (abstract data type) – Abstract data type in computer science
- Adjacency list – Data structure representing a graph
- Adjacency matrix – Square matrix used to represent a graph or network
- DOT (graph description language) – File format
- Doubly connected edge list – data structure to represent an embedding of a planar graph in the plane, and polytopes in 3D
- GraphML
- LCF notation – Representation of cubic graphs
- Rotation system
- Algorithmic components
- Biconnected components and BC trees – Maximal biconnected subgraph
- Bipolar orientation
- Coffman–Graham algorithm – Method for partitioning partial orders into levels
- Existential theory of the reals – Quantified formulas with real-number variables
- Heavy path decomposition
- PQ tree – data structure for representing families of permutations
- SPQR tree – Representation of a graph's triconnected components
- Trémaux tree – Generalization of depth-first search trees
- Graph drawing software
- Gephi – Network analysis and visualization software package
- Graphviz – Software package for graph visualization
- JUNG – open-source graph modeling and visualization framework written in Java
- Meurs Challenger – maa
- Microsoft Automatic Graph Layout – Software library
- yEd – Diagramming program