×

Lattices contained in planar orders are planar. (English) Zbl 0778.05031

The following is the main result of the paper. Let \(P\) be a finite ordered set with planar covering graph and let \(\text{cov}(P)\) be its planar representation. Let \(L\) be a truncated lattice contained in \(P\). Then the covering graph of \(L\) has a representation \(\text{cov}(L)\) in which, whenever \(b\) covers \(a\) in \(L\), the edge joining \(a\) to \(b\) may be taken as a curve following some covering chain in \(P\) from \(a\) to \(b\). Moreover, this representation \(\text{cov}(L)\) is planar, too.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Duffus, D. andRival, I.,Path length in the covering graph of a lattice. Discrete Math.19 (1977), 139-158. · Zbl 0372.06005 · doi:10.1016/0012-365X(77)90029-2
[2] Fáry, I.,On straight line representation of planar graphs. Acta Sci. Math. Szeged11 (1948), 229-233.
[3] Jégou, R., Nowakowski, R. andRival, I.,The diagram invariant problem for planar lattices. Acta Sci. Math.51 (1987), 103-121. · Zbl 0628.06005
[4] Kelly, D.,Fundamentals of planar ordered sets. Discrete Math.63 (1987), 197-216. · Zbl 0609.06002 · doi:10.1016/0012-365X(87)90008-2
[5] Kelly, D. andRival, I.,Planar lattices. Canad. J. Math.27 (1975), 626-665. · Zbl 0312.06003 · doi:10.4153/CJM-1975-074-0
[6] Ne?et?il, J. andRödl, V.,Complexity of diagrams. Order3 (1987), 321-330. · Zbl 0808.06004 · doi:10.1007/BF00340774
[7] Nowakowski, R. andRival, I.,Embedding orders along three channels, to appear.
[8] Pouzet, M. andRival, I.,Is there a diagram invariant? Discrete Math.73 (1988), 181-188. · Zbl 0665.06001 · doi:10.1016/0012-365X(88)90146-X
[9] Rival, I.,The diagram. Order2 (1985), 101-104. · Zbl 0558.05059 · doi:10.1007/BF00337928
[10] Rival, I.,The diagram, inGraphs-and Order (I. Rival, ed.). D. Reidel Publ., pp. 103-133.
[11] Rival, I.,Graphical data structures for ordered sets, inAlgorithms and Order (I. Rival, ed.) D. Reidel Publ., 1989, pp. 3-31. · Zbl 1261.68047
[12] Wagner, K.,Bemerkungen zum Vierfarbenproblem. Jber. Deutsch. Math. Verein.46 (1936), 26-32. · Zbl 0014.18102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.