Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes |
| |
Authors: | Stefan Felsner |
| |
Institution: | (1) Fachbereich Mathematik und Informatik, Freie Universität Berlin, Takustr. 9, 14195 Berlin, Germany |
| |
Abstract: | We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof. |
| |
Keywords: | graph drawing order dimension Schnyder labeling |
本文献已被 SpringerLink 等数据库收录! |
|