For the first time we provide a \emph{succinct} pattern matching index for \emph{arbitrary} graphs that can be built \emph{in polynomial time}, while improving both space and query time bounds from [SODA 2021]. We show that, given an edge-labeled graph $ G = (V, E) $, there exists a data structure 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 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 $ and $ q $ is the width of the \emph{maximum} co-lex relation on $ G $.
Our results have relevant applications in automata theory: we can use our data structure to decide whether a string belongs to the language recognized by a given automaton, and we can capture the degree of nondeterminism of an NFA.