On the number of upward planar orientations of maximal planar graphs

DOI10.1016/j.tcs.2014.04.024zbMath1419.05055OpenAlexW2084829398WikidataQ54308573 ScholiaQ54308573MaRDI QIDQ2250457

Fabrizio Frati, Joachim Gudmundsson, Ermo Welzl

Publication date: 7 July 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.024

zbMATH Keywords

planar graphsacyclic orientationsupward planaritycounting combinatorial structures

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (3)

Trapezoidal diagrams, upward triangulations, and prime Catalan numbers ⋮ Upward planar morphs ⋮ On the upward book thickness problem: combinatorial and complexity results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to draw a planar graph on a grid
• Upward drawings of triconnected digraphs.
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Fundamentals of planar ordered sets
• Algorithms for plane representations of acyclic digraphs
• Simultaneous embedding of a planar graph and its dual on the grid
• Bipolar orientations revisited
• Acyclic orientations of graphs
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Classification of Planar Upward Embedding
• The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem
• Bijective counting of plane bipolar orientations
• Hard Enumeration Problems in Geometry and Combinatorics
• Information Bounds Are Weak in the Shortest Distance Problem
• Upward Planar Drawing of Single-Source Acyclic Digraphs
• Digraph embedding

This page was built for publication: On the number of upward planar orientations of maximal planar graphs