On the order dimension of outerplanar maps (Q651434): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    0 references
    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

    Identifiers