Algorithms for Sampling 3-Orientations of Planar Triangulations

Details Algorithms for Sampling 3-Orientations of Planar Triangulations Algorithms for Sampling 3-Orientations of Planar Triangulations

2012-02-22

arxiv.org/abs/1202.4945v1

Computer Science

Data Structures and Algorithms

Scientific paper

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a Schnyder wood that has proven powerful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a "triangle-reversing" chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. It was shown previously that this chain connects the state space and we show that (i) when restricted to planar triangulations of maximum degree six, the Markov chain is rapidly mixing, and (ii) there exists a triangulation with high degree on which this Markov chain mixes slowly. Next, we consider an "edge-flipping" chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. It was also shown previously that this chain connects the state space and we prove that the chain is always rapidly mixing. The triangle-reversing and edge-flipping Markov chains both arise in the context of sampling other combinatorial structures, such as Eulerian orientations and triangulations of planar point sets, so our results here may shed light on the mixing rate of these related chains as well.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Sampling 3-Orientations of Planar Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Sampling 3-Orientations of Planar Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Sampling 3-Orientations of Planar Triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-415348