Bipolar orientations revisited

DOI10.1016/0166-218X(94)00085-RzbMath0830.05023OpenAlexW2026139239WikidataQ61772231 ScholiaQ61772231MaRDI QIDQ1842650

Pierre Rosenstiehl, Patrice Ossona de Mendez, Hubert de Fraysseix

Publication date: 28 January 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00085-r

zbMATH Keywords

circuitsgraph algorithmsplanargraph drawingcocircuitsbipolar orientations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (38)

A left-first search algorithm for planar graphs ⋮ Criterion for a graph to admit a good orientation in terms of leaf blocks ⋮ A generalized greedy routing algorithm for 2-connected graphs ⋮ Enumeration of corner polyhedra and 3-connected Schnyder labelings ⋮ Bijective counting of plane bipolar orientations ⋮ Bipolar orientations on planar maps and \(\mathrm{SLE}_{12}\) ⋮ On the stability of a switched affine system for a class of switching signals ⋮ Enumeration of corner polyhedra and 3-connected Schnyder labelings ⋮ On the Number of α-Orientations ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ On the enumeration of plane bipolar posets and transversal structures ⋮ Bitonic st-orderings for Upward Planar Graphs ⋮ Bijections for generalized Tamari intervals via orientations ⋮ Realization of a graph as the Reeb graph of a height function on an embedded surface ⋮ Bijections for Baxter families and related objects ⋮ 4-connected triangulations on few lines ⋮ Flips on homologous orientations of surface graphs with prescribed forbidden facial cycles ⋮ Nonlinear Sturm global attractors: unstable manifold decompositions as regular CW-complexes ⋮ A generic method for bijections between blossoming trees and planar maps ⋮ Fixed-energy harmonic functions ⋮ Connectivity and design of planar global attractors of Sturm type. II: Connection graphs ⋮ On the number of upward planar orientations of maximal planar graphs ⋮ Algorithms for computing a parameterized \(st\)-orientation ⋮ Baxter permutations and plane bipolar orientations ⋮ Balanced vertex-orderings of graphs ⋮ Sturm 3-ball global attractors. 1: Thom-Smale complexes and meanders ⋮ A bijection for essentially 3-connected toroidal maps ⋮ Connectivity and design of planar global attractors of Sturm type. III: Small and platonic examples ⋮ Transversal structures on triangulations: A combinatorial study and straight-line drawings ⋮ A finite graph is homeomorphic to the Reeb graph of a Morse-Bott function ⋮ Connectivity and design of planar global attractors of Sturm type, I: Bipolar orientations and Hamiltonian paths ⋮ Optimal \(st\)-orientations for plane triangulations ⋮ Bijective counting of plane bipolar orientations and Schnyder woods ⋮ New bijective links on planar maps via orientations ⋮ Electrical networks and hyperplane arrangements ⋮ Activity preserving bijections between spanning trees and orientations in graphs ⋮ A mating-of-trees approach for graph distances in random planar maps ⋮ Labeled \(K_{2,t}\) minors in plane graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inseparability graphs of oriented matroids
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Algorithms for plane representations of acyclic digraphs
• Area requirement and symmetry display of planar upward drawings
• Planar lattices and planar graphs
• Computing an st-numbering
• Orientability of matroids
• Acyclic and totally cyclic orientations of combinatorial geometries
• Parallel concepts in graph theory
• Algorithms for drawing graphs: An annotated bibliography
• Drawing planar graphs using the canonical ordering
• Planarity and edge poset dimension
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Parallel Transitive Closure and Point Location in Planar Structures
• Planar Lattices
• Ordres "C.A.C."
• Maximal chains and antichains
• Partial orders of dimension 2
• Partially Ordered Sets

This page was built for publication: Bipolar orientations revisited