On the Order Dimension of Outerplanar Maps

Details On the Order Dimension of Outerplanar Maps On the Order Dimension of Outerplanar Maps

2009-06-02

arxiv.org/abs/0906.0515v1

Mathematics

Combinatorics

Contains full details for the final section {Concluding remarks}

Scientific paper

Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset $\Pvef{M}$ of a planar map $M$ is at most four. In this paper we investigate cases where $\dim(\Pvef{M}) \leq 3$ and also where $\dim(\Qvf{M}) \leq 3$; here $\Qvf{M}$ denotes the vertex-face poset of $M$. We show: - If $M$ contains a $K_4$-subdivision, then $\dim(\Pvef{M}) = \dim(\Qvf{M}) = 4$. - If $M$ or the dual $M^*$ contains a $K_{2,3}$-subdivision, then $\dim(\Pvef{M}) = 4$. Hence, a map $M$ with $\dim(\Pvef{M}) \leq 3$ must be outerplanar and have an outerplanar dual. We concentrate on the simplest class of such maps and prove that within this class $\dim(\Pvef{M}) \leq 3$ is equivalent to the existence of a certain oriented coloring of edges. This condition is easily checked and can be turned into a linear time algorithm returning a 3-realizer. Additionally, we prove that if $M$ is 2-connected and $M$ and $M^*$ are outerplanar, then $\dim(\Qvf{M}) \leq 3$. There are, however, outerplanar maps with $\dim(\Qvf{M}) = 4$. We construct the first such example.

Affiliated with

Also associated with

No associations

Rating

On the Order Dimension of Outerplanar Maps 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 On the Order Dimension of Outerplanar Maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Order Dimension of Outerplanar Maps will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-235560