On the order dimension of outerplanar maps (Q651434): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2019109095 / rank | |||
Normal rank |
Revision as of 19:51, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the order dimension of outerplanar maps |
scientific article |
Statements
On the order dimension of outerplanar maps (English)
0 references
13 December 2011
0 references
This paper examines the relation between a planar map \(M\) and the order dimension of some related posets. The dimension \(\dim(P)\) of a poset \(P\) is the minimum \(t\) such that \(P\) is the intersection of \(t\) linear orders. The posets considered are the vertex-edge-face poset \(P_M\) where the elements are ordered by inclusion, and the vertex-face poset \(Q_M\) defined similarly. The authors show that if \(M\) contains a subdivision of \(K_4\), then \(\dim(P_M) = \dim(Q_M)=4\), and that if either \(M\) or its dual \(M^*\) contains a subdivision of \(K_{2,3}\), then \(\dim(P_M)= 4\). Hence if \(\dim(P_M) \leq 3\), then both \(M\) and \(M^*\) is outerplanar. They examine this case and show that \(\dim(P_M) \leq 3\) is equivalent to the existence of a certain oriented coloring of the edges, yielding a linear-time algorithm for verification. Finally, they show if if \(M\) is 2-connected and both \(M,M^*\) are outerplanar, then \(\dim(Q_M)\leq 3\). They also give an outerplanar map with \(\dim(Q_M) = 4\).
0 references
dimension
0 references
outerplanar map
0 references
vertex-edge-face poset
0 references
vertex-face poset
0 references