Planarity of planar finite automata intersection It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. &quot;Planar finite automata.&quot;). Is it possible to provide a planar automata intersection algorithm which instantly preserves planarity? Namely, suppose I have two planar automata $M_1$ and $M_2$. Is there exist an algorithm to construct an intersection of $M_1$ and $M_2$ which acts better (in terms of complexity or in terms of the size of the final automaton) than planarization (using results of Ivona and Martin) after the classical intersection? Also, is it possible to define a respective product of automata (and respective product of adjacency matrices)?
As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: for two languages $L_1$ and $L_2$, let $L_1 Ш L_2$ denote their shuffle (aka interleaving). Let $L_d = (a_1b_1)^* Ш \ldots Ш  (a_db_d)^*$. This language can be expressed as the intersection of the $d$ languages $L_i = (\Sigma\setminus\{a_i,b_i\})^*(a_ib_i)^*(\Sigma\setminus\{a_i,b_i\})^*$. The minimum DFA for $L_d$ is isomorphic to the $d$-dimensional hypercube and has $n=2^d$ states. On the one hand, in (Gruber/Holzer, DLT '09) a lower bound of $2^{\Omega(n/\sqrt{\log\log n})}$ on required regular expression size for $L_d$ is shown. On the other hand, it is proved in (Ellul/Krawetz/Shallit/Wang, JALC '05) that an $s$-state planar  NFA can be converted into an equivalent regular expression of size at most $2^{O(\sqrt s)}$. This shows that $s$ must be in$\Omega(\frac{n^2}{\log\log n})$, as desired.
References:

Keith Ellul, Bryan Krawetz, Jeffrey O. Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. J. Autom. Lang. Comb. 10(4): 407-437 (2005)
Hermann Gruber, Markus Holzer: Tight Bounds on the Descriptional Complexity of Regular Expressions. Developments in Language Theory 2009: 276-287