# Tag Info

34

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 ...

25

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 ...

12

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid $$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$ ...

9

For some graph classes $C$, the question "is there a fast algorithm for deciding whether a graph $G$ belongs to class $C$?" is perhaps only of theoretical curiosity. But it can also be argued otherwise: suppose a problem you care about is hard in general, but efficiently solvable for graphs of class $C$. Wouldn't it be nice if you could quickly test if you ...

7

These problems usually appear under the name "X edge deletion" and "X vertex deletion", where X is the graph class of interest, e.g., X could be "planar". There are also different variants where you allow for say edge addition and deletion (these are "editing problems"), or the operation could be edge contraction and so on. In other words, you seem to be ...

6

I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions. For subgraph isomorphism in general (i.e. not planar), the practical state of ...

3

Use a Voronoi diagram of the line segments As @D.W. noted, a Voronoi diagram of line segments1 is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of Computational Geometry by de Berg et al. ...

3

Quoting directly from the Wikipedia article linked in the question: De Fraysseix, Pach and Pollack showed how to find in linear time a straight-line drawing in a grid with dimensions linear in the size of the graph As I commented earlier, this answers all three questions.

3

One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones. This might work acceptably if you only want very small graphs. Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are ...

3

You probably smack your head against the wall for this but: One face "inside" the triangle, the other one is "outside".

3

Yes, there's a nice algorithm for this. Compute the transitive reduction, then check whether the result is planar. Why does this work? The transitive reduction is the graph with the smallest number of edges, that has the same reachability relationships as the original graph. It is also unique. Moreover, any other graph with the same reachability ...

3

It is $NP$-complete. Consider a graph $G$ which is modified by duplicating every vertex, and connecting every duplicate vertex to its original. Then if we constrain all the duplicate vertices to a fixed color, then the thus obtained graph is 4-colorable (with constraints) if and only if the original graph is 3-colorable.

2

To add to the other answer, the name of the problem you are interested in is precoloring extension: given a graph $G$ with some precolored vertices and a color bound $\ell$, can the precoloring of $G$ be extended to a proper coloring of all vertices of $G$ using not more than $\ell$ colors? This problem is NP-complete for planar bipartite graphs with fixed $\... 2 One general method is to perturb the node weights slightly, find a good partition, and repeat that$n$times with$n$different perturbations. The basic algorithm is something like this: Repeat until you have$n$distinct balanced partitions of$G$: Copy$G$to$G'$. Randomly perturb the weight of each node in$G'$by a tiny amount (a different random ... 2 Contract edges$(C,D)$and$(G,H)$- and you'll get$K_{3,3}$. 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. 2 I haven't tried to work out the details, but it seems plausible to me that it might be possible to solve this with a sweepline algorithm, with ideas from the Bentley-Ottman algorithm. In particular, one approach would be to build the Voronoi diagram of the line segments (rather than a Voronoi diagram of points, as we usually do), then store it in a data ... 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 ... 1 No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the$4$-cycle) that have non-triangular interior faces. 1 Since all the degrees of regions are said to be 3, we can say$2e=3r$. I substituted this value into the Euler equation,$v-e+r=2$and got my final answer as$2(v+2)$. The final answer should be$2(v-2)$. Since I derived the value$r=2(v-2)$which would always remaining even while incrementing$v$. You are right that$r$, the number of regions will ... 1 You might try using the spring model: https://en.wikipedia.org/wiki/Force-directed_graph_drawing. Or, you could use optimization methods. Build an objective function$\Psi$that is a sum of penalty terms. For each pair of mapped points$a^*,b^*$that you are hoping will be at distance$c_{a^*,b^*}$, you have a penalty term$(d(a^*,b^*) - c_{a^*,b^*})^2$. ... 1 The edges examined never intersect because all points are first sorted in terms of angle from the starting point, and then traversed counterclockwise sequentially. By examining edges to each point sorted by their angle counterclockwise and never traversing clockwise (because you stop when you reach the starting node), you ensure that the edges won't interest.... 1 The answer turns out to be no. A counterexample, kindly suggested to me by Balász Gerencsér, is a$\sqrt{N}$by$\sqrt{N}$grid, with a path of length$\sqrt{N}$glued to it. One can show that the mixing time of a simple random walk on this graph is$O(N\log N)\$ (by combining Cheeger's inequality and the Spielman-Teng [1] bound on the spectral gap) the ...

1

This was meant to be a comment but it was a bit too long, sorry! There is a well known algorithm to draw a planar graph, namely Tutte's drawing algorithm. The input graph is assumed to be 3-connected and planar. The idea of the algorithm is to fix the position of vertices of a face in convex position and from those coordinates deduce the positions for the ...

1

As it turns out, this puzzle was solved in a competition at Oxford University in 2012. The winning implementation used backtrack search with several heuristics and pruning, and it can solve instances of the puzzle much larger than the maximum 14x14 in milliseconds. Apparently, the problem I was trying to solve is equivalent to another game called Numberlink. ...

1

It depends. If you have a planar embedding, and you want to find faces on it, just pick an edge, and keep walking on the face that's on the 'left' side of the edge when looked at in the direction you were walking. If you want to find a cycle of nodes for which there exists a planar embedding in which those cycles are a face, that's even easier, because in ...

1

First let me mention that the definition of being uniquely embeddable requires ANY graph isomorphism (e.g. just renaming symmetric vertices or any other automorphism permutation) to be (not necessary uniquely) extendable to topological (or combinatorial) one (see Diestel Graph Theory chapter about planar graphs for these definitions) in contrast to usual ...

1

Presumably you have to show that if you triangulate an arbitrary planar graph then you get an Apollonian network. Then you have to show that the triangulated graph contains more triangles than the original one. This will complete the proof.

1

This is known as "graph layout" or "graph drawing" (practical methods) or "graph embedding" (theoretical interest). The relevant techniques are more closely associated with computational geometry and mathematical optimization, not machine learning. See this Wikipedia article and Recovering a point embedding from a graph with edges weighted by point ...

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