Linearity is strictly more powerful than contiguity for encoding graphs

摘要: Linearity and contiguity are two parameters devoted to graph encoding. is a generalization of in the sense that every encoding achieving k induces an linearity , both having size ? ( . n ) where number vertices G In this paper, we prove strictly more powerful than contiguity, i.e. there exists some family such asymptotically negligible front contiguity. We by answering open question asking for worst case cograph on vertices: provide O log / upper bound which matches previously known lower bound.