2008/01/01 by Hans‐Jürgen Bandelt, Victor Chepoi · 133 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Engineering #Geometry #Graph #Graph Labeling and Dimension Problems #Mathematics #Metric (unit)
paper · doi:10.1090/conm/453/08795
published in Contemporary mathematics - American Mathematical Society, 49-86 (American Mathematical Society)
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