Planar graphs and poset dimension
type: Item
instance of: scholarly article
title: Planar graphs and poset dimension
zbMATH Open document ID: 0675.06001
DOI: 10.1007/BF00353652
author: Walter Schnyder
published in: Order
publication date: 1989-01-01T00:00:00Z
review text: If \(G=(V,E)\) is a finite simple (undirected) graph, then a poset \(G^*\) is defined on \(V\cup E\) by the relation \(a<_ Gb\) iff \(a\in V\), \(b\in E\) and \(a\in b\). dim \(G^*=(order)\)-dim G\(=(poset)\)-\(\dim G\) is the minimal number of total orders on \(V\cup E\) whose intersection is \(G^*\). The order relation \(<_ G\) provides a strong connection between graphs (as defined) and (height one) posets (such that distinct non-minimal maximal elements cover distinct doubletons). Indeed, this interesting paper is an excellent illustration of this claim. Thus, it is proven that a graph G has dim \(G^*\leq 3\) iff G is a planar graph. On the way to proving this important result in two distinct ways, other information of a more general nature is obtained as well. Using the characterization it then becomes possible to provide ``natural'' proofs of properties of planar graphs such as the property that each planar graph has arboricity at most three and that each planar graph has an embedding whose edges are straight line segments. In particular, the labeling of the vertices which results illustrates the ``naturality'' of the arguments and constructions. A short last section is concerned with the extension of general observations and some other results to hypergraphs.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4105025
zbMATH Keywords: triangular graphs
zbMATH Keywords: poset dimension
zbMATH Keywords: straight line embedding
zbMATH Keywords: normal labeling
zbMATH Keywords: planar graph
zbMATH Keywords: hypergraphs
Wikidata QID: Q29037030
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Dimension and automorphism groups of lattices
cites work: Concerning a Certain Set of Arrangements
cites work: Partially Ordered Sets
cites work: Q5786239
cites work: Transitiv orientierbare Graphen
cites work: The complexity of comparability graph recognition and coloring
cites work: Dimension transitiv orientierbarer graphen
cites work: Q5598258
cites work: Orienting planar graphs
cites work: The 3-Irreducible Partially Ordered Sets
cites work: On the Dimension of Partially Ordered Sets
cites work: Edge-Disjoint Spanning Trees of Finite Graphs
cites work: Minimal scrambling sets of simple orders
cites work: Q5832136
cites work: Convex Maps
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: The Dimension of a Comparability Graph
cites work: Bemerkungen zum Vierfarbenproblem
cites work: Q3684157
cites work: The Complexity of the Partial Order Dimension Problem
description: scientific article; zbMATH DE number 4105025