Planar graphs and poset dimension

DOI10.1007/BF00353652zbMath0675.06001WikidataQ29037030 ScholiaQ29037030MaRDI QIDQ1121926

Walter Schnyder

Publication date: 1989

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

hypergraphsplanar graphposet dimensiontriangular graphsstraight line embeddingnormal labeling

Mathematics Subject Classification ID

Partial orders, general (06A06) Hypergraphs (05C65) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items (90)

Incidence posets of trees in posets of large dimension ⋮ Watermelon uniform random generation with applications ⋮ Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ The space complexity of sum labelling ⋮ On simultaneous straight-line grid embedding of a planar graph and its dual ⋮ Planar polyline drawings via graph transformations ⋮ Schnyder woods for higher genus triangulated surfaces (abstract) ⋮ Grid embedding of 4-connected plane graphs ⋮ On the tree number of regular graphs ⋮ On simultaneous planar graph embeddings ⋮ Decomposition of some planar graphs into trees ⋮ Coloring planar homothets and three-dimensional hypergraphs ⋮ Adjacency posets of outerplanar graphs ⋮ The non-planarity of \(K_{5}\) and \(K_{3,3}\) as axioms for plane ordered geometry ⋮ A simple routing algorithm based on Schnyder coordinates ⋮ Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems ⋮ Bijections for Weyl chamber walks ending on an axis, using arc diagrams and Schnyder woods ⋮ Dushnik-Miller dimension of TD-Delaunay complexes ⋮ Dushnik-Miller dimension of contact systems of \(d\)-dimensional boxes ⋮ Planar maps, circle patterns and 2D gravity ⋮ Improved floor-planning of graphs via adjacency-preserving transformations ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ On the Number of α-Orientations ⋮ Separability, boxicity, and partial orders ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Random cubic planar graphs converge to the Brownian sphere ⋮ Schnyder decompositions for regular plane graphs and application to drawing ⋮ Bijections for Baxter families and related objects ⋮ A note on Schnyder's theorem ⋮ Triangle contact representations and duality ⋮ Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations ⋮ A bijection for triangulations, quadrangulations, pentagulations, etc. ⋮ Orthogonal drawings based on the stratification of planar graphs ⋮ Succinct strictly convex greedy drawing of 3-connected plane graphs ⋮ On the order dimension of outerplanar maps ⋮ Orthogonal surfaces and their CP-orders ⋮ On succinct greedy drawings of plane triangulations and 3-connected plane graphs ⋮ Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz ⋮ A generic method for bijections between blossoming trees and planar maps ⋮ Morphing Schnyder drawings of planar triangulations ⋮ Schnyder woods and orthogonal surfaces ⋮ Monotone drawings of graphs with few directions ⋮ Secure Authenticated Comparisons ⋮ Precision measurements of Hausdorff dimensions in two-dimensional quantum gravity ⋮ Straight line triangle representations ⋮ Simultaneous graph embedding with bends and circular arcs ⋮ Representing orders by moving figures in space ⋮ Encoding toroidal triangulations ⋮ Topological graph dimension ⋮ Adjacency posets of planar graphs ⋮ Unnamed Item ⋮ Improved visibility representation of plane graphs ⋮ The space complexity of sum labelling ⋮ Scaling limit of triangulations of polygons ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ Grid intersection graphs and order dimension ⋮ On symmetric quadrangulations and triangulations ⋮ Dimension and height for posets with planar cover graphs. ⋮ Incidence posets and cover graphs ⋮ A bijection for essentially 3-connected toroidal maps ⋮ Representation of Planar Hypergraphs by Contacts of Triangles ⋮ On Planar Polyline Drawings ⋮ Every Schnyder drawing is a greedy embedding ⋮ Geographic routing on virtual raw anchor coordinate systems ⋮ Intervals in Catalan lattices and realizers of triangulations ⋮ Sampling and Counting 3-Orientations of Planar Triangulations ⋮ Fractional dimension of partial orders ⋮ Fully dynamic arboricity maintenance ⋮ Transversal structures on triangulations: A combinatorial study and straight-line drawings ⋮ Dimensions of hypergraphs ⋮ Localized and compact data-structure for comparability graphs ⋮ Optimal \(st\)-orientations for plane triangulations ⋮ A note on isosceles planar graph drawing ⋮ Orienting Triangulations ⋮ A poset-based approach to embedding median graphs in hypercubes and lattices ⋮ Dimension preserving contractions and a finite list of 3-irreducible posets ⋮ Unnamed Item ⋮ AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING ⋮ Homothetic triangle representations of planar graphs ⋮ Clustering analysis of a dissimilarity: a review of algebraic and geometric representation ⋮ Untangling a planar graph ⋮ Visibility representation of plane graphs via canonical ordering tree ⋮ A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths ⋮ A mating-of-trees approach for graph distances in random planar maps ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ CONGRUENCE LIFTING OF SEMILATTICE DIAGRAMS ⋮ The maximum number of edges in a graph of bounded dimension, with applications to ring theory ⋮ The order dimension of the complete graph ⋮ How to draw a planar graph on a grid ⋮ Definability in the substructure ordering of simple graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dimension and automorphism groups of lattices
• Orienting planar graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• The complexity of comparability graph recognition and coloring
• Bemerkungen zum Vierfarbenproblem
• Edge-Disjoint Spanning Trees of Finite Graphs
• The Complexity of the Partial Order Dimension Problem
• Dimension transitiv orientierbarer graphen
• The Dimension of a Comparability Graph
• The 3-Irreducible Partially Ordered Sets
• Transitiv orientierbare Graphen
• Minimal scrambling sets of simple orders
• Partially Ordered Sets
• On the Dimension of Partially Ordered Sets
• Concerning a Certain Set of Arrangements
• Convex Maps

This page was built for publication: Planar graphs and poset dimension