The basic problem is the inductive spikes from the starter motor armature. If ALL accessory circuits, including your Arduino are turned off while the starter motor is active, you are ok. That is why all light and accessory circuits on modern automobiles are off while the starter motor is operating.
The circuit I posted was one that I used many years ago when I built an all TTL digital clock for my car. In spite of capacitors, resistors and all kinds of filtering, starting the car crashed the clock every time.
Since at that time I didn't have an oscilloscope, I had no idea what the problem was.
I was talking about the problem with a buddy of mine and he took a sheet of paper and said "let's try to figure out what happens on the 12 volt line when the car is started".
The "graph" had a straight 12 volt line, a very short dip down to around 6 volts that rose up to about 8 volts and went up and down as the starter motor drew more and less current with each compression stroke, followed by a quick positive spike when the starter was disengaged.
I looked at and thought "I figured all of that EXCEPT the quick downward spike" and decided to try using a series diode to keep the negative spike from "draining" the input filter cap. It worked... the clock never crashed again.
If there's ANYTHING that's vitally important when connecting digital stuff to a car 12 volt system, it's that diode and a capacitor large enough to provide power for the duration of the spike.
With an oscilloscope (or a bit more thinking) I could have solved that problem a lot earlier....