2013/12/10 by Jean Cardinal, Cardinal, Jean, Stefan Felsner +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1312.2819
arxiv created 2013/12/10 · openalex publication_date 2013/12/10 · arxiv updated 2013/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A partial cube is a graph having an isometric embedding in a hypercube. Partial cubes are characterized by a natural equivalence relation on the edges, whose classes are called zones. The number of zones determines the minimal dimension of a hypercube in which the graph can be embedded. We consider the problem of covering the vertices of a partial cube with the minimum number of zones. The problem admits several special cases, among which are the problem of covering the cells of a line arrangement with a minimum number of lines, and the problem of finding a minimum-size fibre in a bipartite poset. For several such special cases, we give upper and lower bounds on the minimum size of a covering by zones. We also consider the computational complexity of those problems, and establish some hardness results.