  For the first time we provide a succinct pattern matching index for arbitrary
graphs that can be built in polynomial time, which requires less space and
answers queries more efficiently than the one in [SODA 2021]. We show that,
given an edge-labeled graph $ G = (V, E) $, there exists a data structures of
$|E /_{\le_G}|(\lceil \log|\Sigma|\rceil + \lceil\log q\rceil + 2)\cdot
(1+o(1)) + |V /_{\le_G}|\cdot (1+o(1))$ bits which can be built in $ O(|E|^2 +
|V /_{\le_G}|^{5 / 2}) $ time and supports pattern matching on $ G $ in $O(|P|
\cdot q^2 \cdot \log(q\cdot |\Sigma|))$ time, where $ G /_{\le_G} = (V
/_{\le_G}, E /_{\le_G}) $ is a quotient graph obtained by collapsing some nodes
in $ G $ (so $ |V /_{\le_G}| \le |V| $ and $ |E /_{\le_G}| \le |E| $) and $ q $
is the width of the maximum co-lex relation on $ G $.
  Our results have relevant applications in automata theory. First, we can
build a succinct data structure to decide whether a string is accepted by a
given automaton. Second, starting from an automaton $ \mathcal{A} $, one can
define a relation $ \preceq_\mathcal{A} $ and a quotient automaton that capture
the nondeterminism of $ \mathcal{A} $, improving the results in [SODA 2021].
