Isometric subgraphs of hypercubes, or partial cubes as they are also called, are a rich class of graphs that include median graphs, subdivision graphs of complete graphs, and classes of graphs arising in mathematical chemistry and biology. In general one can recognize whether a graph on n vertices and m edges is a partial cube in O(mn) steps, faster recognition algorithms are only known for median graphs. This paper exhibits classes of partial cubes that are not median graphs but can be recognized in O(m log n) steps. On the way relevant decomposition theorems for partial cubes are derived, one of them correcting an error in a previous paper 13].
• Brešar et al. REF discuss several other classes of partial cubes that are closely related to the median graphs and may be recognized in O(m log n) time.
Fast recognition algorithms for classes of partial cubes
Discrete Applied Mathematics
Computer Science Mathematics