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

From MaRDI portal
Added link to MaRDI item.
Normalize DOI.
 
(5 intermediate revisions by 5 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s11083-010-9181-1 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2019109095 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 0906.0515 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Order Dimension of Convex Polytopes / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Order Dimension of Planar Maps / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partially Ordered Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the order dimension of outerplanar maps / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the number of planar orientations with prescribed degrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear algorithms to recognize outerplanar and maximal outerplanar graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4918387 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Planar graphs and poset dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4004146 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Complexity of the Partial Order Dimension Problem / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S11083-010-9181-1 / rank
 
Normal rank

Latest revision as of 23:49, 9 December 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