{"id":1059,"date":"2013-11-01T23:58:06","date_gmt":"2013-11-01T23:58:06","guid":{"rendered":"http:\/\/blogs.oregonstate.edu\/glencora\/?p=1059"},"modified":"2013-11-01T23:58:17","modified_gmt":"2013-11-01T23:58:17","slug":"tsp-1-planar-graphs","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2013\/11\/01\/tsp-1-planar-graphs\/","title":{"rendered":"TSP in 1-planar graphs"},"content":{"rendered":"

I recently came back from a Dagstuhl I organized with Phil, Claire and Daniel on optimization algorithms for planar graphs.\u00a0 I think I finally caught up for the week away and sat down this afternoon to think about research.\u00a0 A problem suggested at the workshop was TSP in 1-planar graphs<\/strong>.\u00a0 1-planar graphs are those graphs that can be drawn in the plane such that any edge has at most one other edge crossing it.<\/p>\n

We have PTASes for TSP in bounded-genus graphs and in particular, these PTASes solve the subset <\/em>TSP problem wherein you want to find the shortest tour that visits an input subset of vertices.\u00a0 In general graphs, we would just take the metric completion (create the complete graph on that input subset of vertices where the weight of each edge is the length of the shortest path in the original graph) and solve the problem in that completion.\u00a0 In planar graphs you could do this, but you would lose planarity.\u00a0 The subset version is inherently interesting: if you are designing a delivery route, you definitely don’t want to visit every intersection<\/em> in your region.<\/p>\n

One would suppose that for 1-planar graphs, one would also want to give a PTAS for the subset version of the problem.\u00a0 However, we can argue that isn’t the case.\u00a0 Take a general graph G and consider any drawing of that graph in the plane.\u00a0 An edge in this drawing will have any number of other edges crossing it, creating a sequence of crossing points along the edge.\u00a0 Subdivide this edge by introducing a vertex between every consecutive crossing point and distribute the weight of the original edge among these new edges.\u00a0 Now you have a 1-planar graph H.\u00a0 If you could find a (1+eps)-approximate tour that visits the subset of vertices that correspond to the vertices of G, this ordering of vertices would correspond to a (1+eps)-approximate tour in G.\u00a0 However, metric TSP is APX-hard.\u00a0 So, there can’t be a PTAS for subset TSP in 1-planar graphs.<\/p>\n

There might still be a PTAS for TSP (visiting all the vertices) in 1-planar graphs.\u00a0 This doesn’t seem as interesting a problem though.<\/p>\n","protected":false},"excerpt":{"rendered":"

I recently came back from a Dagstuhl I organized with Phil, Claire and Daniel on optimization algorithms for planar graphs.\u00a0 I think I finally caught up for the week away and sat down this afternoon to think about research.\u00a0 A problem suggested at the workshop was TSP in 1-planar graphs.\u00a0 1-planar graphs are those graphs […]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[106178,106190,117603],"class_list":["post-1059","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-planar-graphs","tag-tcs","tag-tsp"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/1059","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=1059"}],"version-history":[{"count":2,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/1059\/revisions"}],"predecessor-version":[{"id":1061,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/1059\/revisions\/1061"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=1059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=1059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=1059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}