Unique circular ordering of edges around a vertex - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T20:05:20Z http://mathoverflow.net/feeds/question/119047 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119047/unique-circular-ordering-of-edges-around-a-vertex Unique circular ordering of edges around a vertex Hans Stricker 2013-01-16T09:50:48Z 2013-01-18T01:53:30Z <p>Consider the property of a vertex $v$ of a planar graph $G$ that the <a href="http://en.wikipedia.org/wiki/Rotation_system" rel="nofollow">circular ordering</a> of its edges is the same (upto orientation) for every <a href="http://en.wikipedia.org/wiki/Graph_embedding" rel="nofollow">graph embedding</a> $\pi$ of $G$ into the plane $\mathbb{R}^2$.</p> <blockquote> <ol> <li><p>Does this property have an official name?</p></li> <li><p>(How) can it be defined purely combinatorially?</p></li> <li><p>(How) can planar graphs be characterized in which every vertex has this property?</p></li> </ol> </blockquote> http://mathoverflow.net/questions/119047/unique-circular-ordering-of-edges-around-a-vertex/119086#119086 Answer by Hans Stricker for Unique circular ordering of edges around a vertex Hans Stricker 2013-01-16T17:07:12Z 2013-01-17T06:52:13Z <p>It might be simpler than I believed:</p> <blockquote> <p>ad 2. The <em>circular</em> ordering of the edges (= neighbours) of a vertex $v$ of a planar graph $G$ is unique (upto orientation) when the neighbours of $v$ lie on a <em>cycle</em> that does not contain $v$.</p> </blockquote> <p>If they happen to lie on more than one cycle their circular ordering doesn't depend on which.</p> http://mathoverflow.net/questions/119047/unique-circular-ordering-of-edges-around-a-vertex/119109#119109 Answer by Michael Biro for Unique circular ordering of edges around a vertex Michael Biro 2013-01-16T19:40:14Z 2013-01-16T19:40:14Z <p>The converse to the cycle statement doesn't hold. Take a wheel graph, and split each spoke with a new vertex. Then, the center has the fixed circular ordering property, but there is no such cycle. </p> <p>Intuitively, I suspect the full condition for $v$ to have the property is that there exists in the planar graph a (spoke-divided) wheel graph with $v$ at its center with each of $v$'s neighbors dividing a distinct spoke (where the case of the neighbors being on a cycle is with degenerate spoke-dividing).</p> http://mathoverflow.net/questions/119047/unique-circular-ordering-of-edges-around-a-vertex/119154#119154 Answer by Brendan McKay for Unique circular ordering of edges around a vertex Brendan McKay 2013-01-17T09:45:31Z 2013-01-18T01:53:30Z <p>I'm assuming that the reverse of a cyclic ordering counts as the same ordering. I'm also assuming the graph is simple (otherwise subdivide edges with extra vertices to make it simple).</p> <p>There is only one cyclic order for vertices of degree 1,2,3, so the interesting vertices have degree 4 or more.</p> <p>3-connected graphs have only one planar embedding. Given any planar embedding of a connected graph, you can get all the other planar embeddings by reordering and flipping over the parts separated by a 1-cut or a 2-cut.</p> <p>So, without thinking about it too much, I think the answer is:</p> <p>A vertex has consistent ordering if it has degree 1,2,3, or if it is not a cut-vertex or part of a 2-vertex cut.</p> <p>A cut-vertex of degree at least 4 does not have consistent ordering.</p> <p>The remaining case is a vertex $v$ of degree at least 4 that is part of a 2-vertex cut. Separate the graph at the cut so that $v$ and the other vertex in the cut are replicated in each piece (I hope this is clear enough without a formal definition). FIXED: Then $v$ has consistent ordering iff there are exactly two pieces and in one of them $v$ has degree 1.</p>