Skip to main content
Grzegorz Jaśkiewicz's user avatar
Grzegorz Jaśkiewicz's user avatar
Grzegorz Jaśkiewicz's user avatar
Grzegorz Jaśkiewicz
  • Member for 13 years, 3 months
awarded
comment
Hamiltonian paths in subgraphs of rectangular lattice graphs
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 ;)
awarded
comment
Hamiltonian paths in subgraphs of rectangular lattice graphs
1. NP-complete, answer is here: research.cs.queensu.ca/home/daver/Pubs/MyPDF/superThin.pdf 2. NP-complete by polyminal reduction to problem 1 - just check Hamiltonian path for every vertex
comment
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is it obvious that cublic planar graph is a vertex-induced subgraph of rectangular lattice graph?
Loading…