DOSEN PROFIL LENGKAP

Graph Drawing

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 with at most one crossing per 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; Strangulated graph – Graph whose peripheral cycles are all triangles; Thickness (graph theory) – Number of planar subgraphs to cover a graph; 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 – On tangency patterns of circles; Interval graph – Intersection graph for intervals on the real number line; Scheinerman's conjecture – On line segment intersection graphs; 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 – Study of graphs defined by geometric means; 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 – Graph of intervisible locations in computational geometry

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 – Graph data structure; GraphML – File format for graphs; LCF notation – Representation of cubic graphs; Rotation system – Combinatorial representation of a graph on an orientable surface

Algorithmic components: Biconnected components and BC trees – Maximal biconnected subgraph; Bipolar orientation – Graph orientation with one source and sink; Coffman–Graham algorithm – Method for partitioning partial orders into levels; Existential theory of the reals – Quantified formulas with real-number variables; Heavy path decomposition – Path structure in mathematical trees; PQ tree – Data structure for 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; Meurs Challenger; Microsoft Automatic Graph Layout – Software library; yEd – Diagramming program