most recent 30 from http://mathoverflow.net 2013-05-25T10:04:50Z http://mathoverflow.net/feeds/user/17827 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75501/hamiltonian-paths-in-subgraphs-of-rectangular-lattice-graphs Grzegorz Jaśkiewicz 2011-09-15T10:52:57Z 2011-09-15T14:20:47Z

<p>Is following decision problem NP-hard / NP-complete:</p> <ol> <li>Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists</li> <li>Having vertex-induced subgraph of rectangular lattice graph determine if exists Hamiltonian path starting at given point (path end can be anywhere)</li> </ol> <p>Please give me some references.</p>

http://mathoverflow.net/questions/75501/hamiltonian-paths-in-subgraphs-of-rectangular-lattice-graphs Grzegorz Jaśkiewicz 2011-09-15T20:59:57Z 2011-09-15T20:59:57Z

I have some funny idea: 1. Draw cubic planar graph on white piece of paper with black pen, so that there are no edge intersections. 2. Take a photo with digital camera. Now all pixels in photo form square lattice, black pixels are verteices of lattice subgraph. With correct lens scaling this would produce good embedding ;)

http://mathoverflow.net/questions/75501/hamiltonian-paths-in-subgraphs-of-rectangular-lattice-graphs Grzegorz Jaśkiewicz 2011-09-15T12:41:50Z 2011-09-15T12:41:50Z

1. NP-complete, answer is here: <a href="http://research.cs.queensu.ca/home/daver/Pubs/MyPDF/superThin.pdf" rel="nofollow">research.cs.queensu.ca/home/daver/Pubs/MyPDF/&hellip;</a> 2. NP-complete by polyminal reduction to problem 1 - just check Hamiltonian path for every vertex

http://mathoverflow.net/questions/75501/hamiltonian-paths-in-subgraphs-of-rectangular-lattice-graphs Grzegorz Jaśkiewicz 2011-09-15T12:24:26Z 2011-09-15T12:24:26Z

Is it obvious that cublic planar graph is a vertex-induced subgraph of rectangular lattice graph?