2008/01/01 by Hans‐Jürgen Bandelt, Victor Chepoi · 3 citations
Computer Science · Mathematics · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Metric (unit) #Graph #Geometry #Mathematics #Computer science #Combinatorics #Engineering
paper · doi:10.1090/conm/453/08795
openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
The article surveys structural characterizations of several graph classes defined by distance properties, which have in part a general algebraic flavor and can be interpreted as subdirect decomposition. The graphs we feature in the first place are the median graphs and their various kinds of generalizations, e.g., weakly modular graphs, or fiber-complemented graphs, or l1-graphs. Several kinds of l1-graphs admit natural geometric realizations as polyhedral complexes. Particular instances of these graphs also occur in other geometric contexts, for example, as dual polar graphs, basis graphs of (even ∆-)matroids, tope graphs, lopsided sets, or plane graphs with vertex degrees and face sizes bounded from below. Several other classes of graphs, e.g., Helly graphs (as injective objects), or bridged graphs (generalizing chordal graphs), or tree-like graphs such as distance-hereditary graphs occur in the investigation of graphs satisfying some basic properties of the distance function, such as the Helly property for balls, or the convexity of balls or of the neighborhoods of convex sets, etc. Operators between graphs or complexes relate some of the