Graph Theory

Graph objects and methods

• Generic graphs (common to directed/undirected)
• Undirected graphs
• Directed graphs
• Bipartite graphs

Constructors and databases

• Common Graphs
• Common Digraphs
• Common graphs and digraphs generators (Cython)
• Graph database
• Database of strongly regular graphs
• ISGCI: Information System on Graph Classes and their Inclusions

Low-level implementation

• Overview of (di)graph data structures
• Fast compiled graphs
• Fast sparse graphs
• Fast dense graphs
• Static dense graphs
• Static Sparse Graphs
• Static sparse graph backend
• Backends for Sage (di)graphs.
• Interface to run Boost algorithms

Hypergraphs

• Hypergraph generators
• Incidence structures (i.e. hypergraphs, i.e. set systems)

Libraries of algorithms

• Graph coloring
• Interface with Cliquer (clique-related problems)
• Centrality
• Asteroidal triples
• Independent sets
• Comparability and permutation graphs
• Line graphs
• Spanning trees
• PQ-Trees
• Generation of trees
• Matching Polynomial
• Genus
• Lovász theta-function of graphs
• Linear Extensions of Directed Acyclic Graphs.
• Schnyder’s Algorithm for straight-line planar embeddings
• Wrapper for Boyer’s (C) planarity algorithm.
• Graph traversals.
• Graph Plotting
• Graph plotting in Javascript with d3.js
• Vertex separation
• Rank Decompositions of graphs
• Bandwidth of undirected graphs
• Cutwidth
• Products of graphs
• Convexity properties of graphs
• Weakly chordal graphs
• Distances/shortest paths between all pairs of vertices
• LaTeX options for graphs
• Graph editor
• Lists of graphs
• Functions for reading/building graphs/digraphs.
• Hyperbolicity
• Tutte polynomial
• Partial cubes
• Path Enumeration
• GenericGraph Cython functions
• Orientations
• Connectivity related functions

Indices and Tables

• Index
• Module Index
• Search Page