Check out Puka Dog,
http://www.pukadog.com/. I love their hot dogs and ate there a couple of times when I visited Kauai. It is the best dog I have ever had.
It seems they started small at a hut and grew from there because they had an excellent hook of a custom premium dog, unique sauce, tropical relish, and a inner toasted bun.