Encoding graphs as text prompts enables LLM-based graph reasoning. However, effective graph-to-text encodings depend on the downstream task, graph structure, and target LLM, making manual format design time-consuming and brittle. We propose EvoFormat, a black-box evolutionary search framework that automatically discovers interpretable graph-to-text formats represented as human-readable formatting rules over node naming, relation expression, and global arrangement. Using only task-level feedback from LLM outputs, EvoFormat iteratively mutates and selects rules without gradients or internal model access. Across synthetic GraphQA and IMDB-MULTI-derived structural QA tasks over unattributed graphs, EvoFormat outperforms strong hand-crafted encodings in most settings.