2024/05/13 by Victor Chepoi, Chepoi, Victor · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.2405.07512
openalex publication_date 2024/05/13 · openalex created_date 2024/05/15 · openalex updated_date 2026/08/01
Semispaces of a convexity space (X,C) are maximal convex sets missing a point. The separation axiom S3 asserts that any point x0∈ X and any convex set A not containing x0 can be separated by complementary halfspaces (convex sets with convex complements) or, equivalently, that all semispaces are halfspaces. In this paper, we study S3 for geodesic convexity in graphs and the structure of semispaces in S3-graphs. We characterize S3-graphs and their semispaces in terms of separation by halfspaces of vertices x0 and special sets, called maximal x0-proximal sets and in terms of convexity of their mutual shadows x0/K and K/x0. In S3-graphs G satisfying the triangle condition (TC), maximal proximal sets are the pre-maximal cliques of G (i.e., cliques K such that K∪\ x0\ are maximal cliques). This allows to characterize the S3-graphs satisfying (TC) in a structural way and to enumerate their semispaces efficiently. In case of meshed graphs (an important subclass of graphs satisfying (TC)), the S3-graphs have been characterized by excluding five forbidden subgraphs. On the way of proving this result, we also establish some properties of meshed graphs, which maybe of independent interest. In particular, we show that any connected, locally-convex set of a meshed graph is convex. We also provide several examples of S3-graphs, including the basis graphs of matroids. Finally, we consider the (NP-complete) halfspace separation problem, describe two methods of its solution, and apply them to particular classes of graphs and graph-convexities.