<p><strong>optimization problem</strong></p>

<p><strong>Input</strong>: a 3-connected cubic planar graph</p>

<p><strong>feasible solution</strong>: A simple path</p>

<p><strong>measure to optimize</strong>: length of the simple path</p>

<p>Is there a constant approximation algorithm for this problem?</p>

<p>The Hamiltonian circuit problem on 3-connected cubic planar graphs is NP-Complete <a href="http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf" rel="nofollow noreferrer">in this paper</a>.</p>

<p>A <a href="https://cstheory.stackexchange.com/questions/674/best-bounds-for-the-longest-path-optimization-problem-in-cubic-hamiltonian-graph">relevant question about for cubic Hamiltonian graph</a> shows that there is no constant approximation algorithm for longest path on cubic graphs.</p>

<p>I'm also interested in the version where the input is a maximal planar graph.</p>

CC BY-SA 3.0
2011-10-23T21:46:22.723Z
Out of curiosity, what is the motivation for this particular problem for this particular class of graphs?  As a wild guess, is there any connection to the [Hirsch conjecture](http://en.wikipedia.org/wiki/Hirsch_conjecture)?
Tsuyoshi Ito
CC BY-SA 3.0
2011-10-23T22:35:36.200Z
I did not have Hirsch conjecture in mind. Consider the following problem: There is a planar embedding of a graph. One want to find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice. If there is a constant approximation for this problem, then there will be a constant approximation for the problem in the question.
Chao Xu
CC BY-SA 3.0
2011-10-24T13:00:58.627Z
Hmm, I have trouble understanding the motivation for your other problem (“find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice”), but thanks for the reply!
Tsuyoshi Ito
<graph-algorithms><approximation-hardness>
Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?
Chao Xu
# Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?

(Asked by: username_0 on 2011-10-21)

**optimization problem**

**Input**: a 3-connected cubic planar graph

**feasible solution**: A simple path

**measure to optimize**: length of the simple path

Is there a constant approximation algorithm for this problem?

The Hamiltonian circuit problem on 3-connected cubic planar graphs is NP-Complete [in this paper](http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf).

A [relevant question about for cubic Hamiltonian graph](https://cstheory.stackexchange.com/questions/674/best-bounds-for-the-longest-path-optimization-problem-in-cubic-hamiltonian-graph) shows that there is no constant approximation algorithm for longest path on cubic graphs.

I'm also interested in the version where the input is a maximal planar graph.

**Tags:** graph-algorithms, approximation-hardness
> **Comments:**
> **username_1**: Out of curiosity, what is the motivation for this particular problem for this particular class of graphs?  As a wild guess, is there any connection to the [Hirsch conjecture](http://en.wikipedia.org/wiki/Hirsch_conjecture)?  
> **username_0**: I did not have Hirsch conjecture in mind. Consider the following problem: There is a planar embedding of a graph. One want to find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice. If there is a constant approximation for this problem, then there will be a constant approximation for the problem in the question.  
> **username_1**: Hmm, I have trouble understanding the motivation for your other problem (“find a simple curve on the plane that maximizes the number of vertices visited without cross any edge twice”), but thanks for the reply!  

---

## 0 answers

