0
$\begingroup$

(I asked this on mathse. May be it suits better here)

How to find the cyclic ordering of edges incident on a vertex in a plane graph? (ie, in a plane embedding) Of coure we are looking for a polynomial time algorithm.

The algorithm i settled on uses dual graph. The idea was to take the set $E$ of edges incident on $v$. Take the set $F$ of faces that contains vertex $v$. Let the dual graph be $G^*$. Take the induced subgraph $G^*[F]$. It will be a cylcle and hence we have a cyclic ordering. From this, we can obtain a cylcic ordering of the edges incident on $v$ in the original graph.

In "Planar Formulae and Their Uses", Lichtenstein says

There is a choice of cyclic orderings of (neighbors of $v$ aruond $v$) ... for which NC(B) is planar if and only if G(B) is planar. Since any (polynomial) planarity algorithm can find such an ordering if it exists, ....

I understand that it is common not to be concerned with specific details of simle things in such papers.

But it seems i am missing something. Is there anything easier? Sorry; i know this must be a simple thing. But i don't see any better way.

Thank you

$\endgroup$
  • 1
    $\begingroup$ How is your embedding of your plane graph represented, if not in a way that already directly gives you the cyclic order you want? $\endgroup$ – David Eppstein Jun 4 '18 at 7:30
  • $\begingroup$ Lichtenstein says (almost) any planarity algorithm can find a cyclic permutation of edges incident of a vertex. Doesn't that mean (almost) every plane embedding algorithm is a combinatorial embedding as well? $\endgroup$ – Cyriac Antony Jun 4 '18 at 11:03
  • $\begingroup$ @DavidEppstein The algorithm of Hopcroft and Tarjan gives a cyclic permutation of edges incident on a vertex. May be, other algorithms can do this as well easily. But how can we directly get that info from our representation? $\endgroup$ – Cyriac Antony Jun 4 '18 at 11:09
  • 3
    $\begingroup$ The planarity algorithm finds an embedding of a (planar) graph that does not already have an embedding chosen. But you are asking about embedded (plane) graphs. When a graph is already embedded, that embedding has to be represented somehow as part of what you are storing in your computer. See e.g. en.wikipedia.org/wiki/Graph-encoded_map en.wikipedia.org/wiki/Doubly_connected_edge_list etc. Most of these representations make it very easy to return the information you ask for and we cannot answer your question without knowing how you are representing the embedding. $\endgroup$ – David Eppstein Jun 5 '18 at 3:41
  • $\begingroup$ I agree with David: could you give us a precise formal specification of the input to the algorithm? Something like the following (only an example): "Input: a graph $G = (V, E)$ with $V$ a set of vertices, $E$ a set of edges that are pairs of elements of $V$, and an embedding function $f : V \to \mathbb{R}^2$ mapping every $v \in V$ to coordinates $f(v)$ such that there is no edge crossing, i.e., there are no $\{u, v\}, \{u', v'\} \in E$ such that the segments $[f(u), f(v)]$ and $[f(u'), f(v')]$ intersect." $\endgroup$ – a3nm Jun 5 '18 at 9:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.