# Tag Info

31

It isn't true that every DFA for this language is non-planar: Here is a language that is truly non-planar: $$\left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}.$$ Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six ...

23

The concept has been researched before. (Once you know the answer, google for it ...) First there is old work by Book and Chandra, with the following abstract. Summary. It is shown that for every finite-state automaton there exists an equivalent nondeterministic automaton with a planar state graph. However there exist finite-state automata with no ...

2

An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.

1

Regarding the proof of the statement you quoted (to complement Juho's answer): Let $G$ be a connected planar graph with $V > 2$ vertices, $E$ edges and $F$ faces. We know from Euler's formula that $V-E+F=2$. Now let us count the number $q$ of $(e,f)$ pairs where $e$ is an edge and $f$ is a face incident to $e$. Because every edge is incident to at most ...

1

The idea is that in a planar graph, there are no cliques of size 5 or more (see Kuratowski's theorem). So suppose the problem is "is there a clique of size $k$ in a given planar graph $G$?" Now, if $k \geq 5$, we immediately answer NO. If $k \leq 4$, we can simply check every subset of the vertices of size $k$ (note that there are $\Theta(n^k)$ such ...

Only top voted, non community-wiki answers of a minimum length are eligible