# Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

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.

• 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? Commented Nov 19, 2015 at 5:32
• @DavidEppstein , you are correct . No, it's not more than the abstract graph. Do you consider the problem trivial ? Thanks for your response. Commented Nov 19, 2015 at 6:17
• @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? Commented Nov 19, 2015 at 21:40
• @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. Commented Nov 20, 2015 at 0:02
• 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? Commented Nov 20, 2015 at 13:35