No, it is not linear in the genus; it is at least exponential in $g$. See for example this answer by David Eppstein.
Tony Huynh
- 32.1k
- 11
- 112
- 187