<p><strong>Problem:</strong>
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).</p>

<p><strong>Attempt:</strong>
Using the planarity check algorithm, an algorithm can be constructed with polynomial bound.</p>

<p><strong>Questions:</strong>
My questions are-</p>

<ol>
<li><p>Are there any literature /algorithms regarding the problem?</p></li>
<li><p>Can the problem have a log-space time algorithm (without using planarity check algorithm)? </p></li>
</ol>

<p><strong>Motivation:</strong> Trying to find the outer cycle of a  planar graph quickly to reduce the complexity of Hamiltonian circuit problem.</p>

CC BY-SA 3.0
2015-11-19T05:32:40.020Z
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?
David Eppstein
CC BY-SA 3.0
2015-11-19T06:17:05.763Z
@DavidEppstein , you are correct . No, it's not more than the abstract graph. Do you consider the problem trivial ? Thanks for your response.
Michael
CC BY-SA 3.0
2015-11-19T21:40:05.857Z
@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?
fidbc
CC BY-SA 3.0
2015-11-20T00:02:42.240Z
@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.
Michael
CC BY-SA 3.0
2015-11-20T04:05:06.687Z
If you are looking for any face, then this does not seem like a research-level question. You can easily obtain such face by using the clockwise ordering of neighbors around each vertex, such ordering is usually output by planarity testing algorithms.
fidbc
CC BY-SA 3.0
2015-11-20T07:12:15.663Z
@fidbc , yes I am aware of planarity testing algorithms , I was looking for a different solution than that.
Michael
CC BY-SA 3.0
2015-11-20T13:35:19.767Z
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?
fidbc
CC BY-SA 3.0
2015-11-20T14:33:08.007Z
@fidbc, yes, the log space didn't seem to be trivial to me, because planarity check will use all n vertices for 'complete solution', that is why I was looking for alternative. Would u please explain a little why u did't consider the problem 'research level' problem? also, it appears to me that u  know how to solve it in log sapce ( otherwise it would also be a research level prb to  u ), please, share and enlighten me.
Michael
CC BY-SA 3.0
2015-11-20T14:38:36.750Z
@fidbc , eulers formula informs u in advance whether the graph has more than 2 region or not , so .......
Michael
<ds.algorithms><reference-request><graph-theory><graph-algorithms><planar-graphs>
Vertices adjacent to Exterior region of a Planar Graph(Algorithm)
Michael
# Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

(Asked by: username_0 on 2015-11-18)

**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.

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: 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?  
> **username_0**: @DavidEppstein , you are correct . No, it's not more than the abstract graph. Do you consider the problem trivial ? Thanks for your response.  
> **username_2**: @Jim You still have to define "outer cycle of a planar graph", as username_1 points out any face can be made the outer face. Are you looking for a particular face? If so, what characterizes such face?  
> **username_0**: @username_2 , 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.  
> **username_2**: If you are looking for any face, then this does not seem like a research-level question. You can easily obtain such face by using the clockwise ordering of neighbors around each vertex, such ordering is usually output by planarity testing algorithms.  
> **username_0**: @username_2 , yes I am aware of planarity testing algorithms , I was looking for a different solution than that.  
> **username_2**: 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?  
> **username_0**: @username_2, yes, the log space didn't seem to be trivial to me, because planarity check will use all n vertices for 'complete solution', that is why I was looking for alternative. Would u please explain a little why u did't consider the problem 'research level' problem? also, it appears to me that u  know how to solve it in log sapce ( otherwise it would also be a research level prb to  u ), please, share and enlighten me.  
> **username_0**: @username_2 , eulers formula informs u in advance whether the graph has more than 2 region or not , so .......  

---

## 0 answers

