Planar graphs and poset dimension |
| |
Authors: | Walter Schnyder |
| |
Affiliation: | (1) Department of Mathematics, Louisiana State University, 70803-4918 Baton Rouge, LA, USA |
| |
Abstract: | We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<Gb if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning. |
| |
Keywords: | Primary 06A10 secondary 05C10, 05C75 |
本文献已被 SpringerLink 等数据库收录! |
|