  Universal cycles, such as De Bruijn cycles, are cyclic sequences of symbols
that represent every combinatorial object from some family exactly once as a
consecutive subsequence. Graph universal cycles are a graph analogue of
universal cycles introduced in 2010. We introduce graph universal partial
cycles, a more compact representation of graph classes, which use "do not know"
edges. We show how to construct graph universal partial cycles for labeled
graphs, threshold graphs, and permutation graphs. For threshold graphs and
permutation graphs, we demonstrate that the graph universal cycles and graph
universal partial cycles are closely related to universal cycles and compressed
universal cycles, respectively. Using the same connection, for permutation
graphs, we define and prove the existence of an $s$-overlap form of graph
universal cycles. We also prove the existence of a generalized form of graph
universal cycles for unlabeled graphs.
