1
$\begingroup$

Problem: I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the exterior region /face).

Attempt: Using the planarity check algorithm, an algorithm can be constructed with polynomial bound.

Questions: My questions are-

  1. Are there any literature /algorithms regarding the problem?

  2. Can the problem have a log-space time algorithm (without using planarity check algorithm)?

Motivation: Trying to find the outer cycle of a planar graph quickly to reduce the complexity of Hamiltonian circuit problem.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ What do you mean by "the outer cycle of a planar graph"? A planar graph can have many planar embeddings and any face of any of these embeddings can be made into the outer face of a different embedding. Is your input something more than the abstract graph, and if so what? $\endgroup$
    – David Eppstein
    Commented Nov 19, 2015 at 5:32
  • $\begingroup$ @DavidEppstein , you are correct . No, it's not more than the abstract graph. Do you consider the problem trivial ? Thanks for your response. $\endgroup$
    – Michael
    Commented Nov 19, 2015 at 6:17
  • $\begingroup$ @Jim You still have to define "outer cycle of a planar graph", as David Eppstein points out any face can be made the outer face. Are you looking for a particular face? If so, what characterizes such face? $\endgroup$
    – fidbc
    Commented Nov 19, 2015 at 21:40
  • $\begingroup$ @fidbc , I agreed with DE and .......... now with u, any face can be treated as outer face=region=cycle. not looking for a particular face. thanks for ur response. $\endgroup$
    – Michael
    Commented Nov 20, 2015 at 0:02
  • 1
    $\begingroup$ Sorry! Didn't remember that part of the question. You may still try using the cycle space of the graph and find a facial cycle. However, the log-space time constraint might not be satisfied. Is it even possible to get log-space time given that the only faces could have O(n) size? $\endgroup$
    – fidbc
    Commented Nov 20, 2015 at 13:35

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.