Drawing planar graphs using the canonical ordering

DOI10.1007/BF02086606zbMath0851.68086OpenAlexW2045870980MaRDI QIDQ1920418

Publication date: 17 November 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02086606

zbMATH Keywords

visibility representations graph-drawing problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Schnyder woods for higher genus triangulated surfaces, with applications to encoding ⋮ Relating bends and size in orthogonal graph drawings ⋮ Minimum-segment convex drawings of 3-connected cubic plane graphs ⋮ Drawing Planar Graphs on Area ⋮ Schnyder woods for higher genus triangulated surfaces (abstract) ⋮ Drawings of planar graphs with few slopes and segments ⋮ Quasi-upward planar drawings with minimum curve complexity ⋮ Drawing graphs on rectangular grids ⋮ Orthogeodesic point-set embedding of trees ⋮ Triangulating planar graphs while minimizing the maximum degree ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ Convex grid drawings of planar graphs with constant edge-vertex resolution ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ New results on drawing angle graphs ⋮ A better heuristic for orthogonal graph drawings ⋮ Orthogonal cartograms with at most 12 corners per face ⋮ Universal slope sets for 1-bend planar drawings ⋮ Orthogonal drawing of high degree graphs with small area and few bends ⋮ Planar and Poly-arc Lombardi Drawings ⋮ Straight-line drawings of 1-planar graphs ⋮ Bitonic \(st\)-orderings for upward planar graphs: splits and bends in the variable embedding scenario ⋮ An efficient orthogonal grid drawing algorithm for cubic graphs ⋮ Unit-length rectangular drawings of graphs ⋮ Strictly-convex drawings of 3-connected planar graphs ⋮ Drawing subcubic planar graphs with four slopes and optimal angular resolution ⋮ An annotated review on graph drawing and its applications ⋮ Bitonic st-orderings for Upward Planar Graphs ⋮ Unnamed Item ⋮ Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs ⋮ Sliding column model for t-unit bar visibility representations of graphs ⋮ Schnyder decompositions for regular plane graphs and application to drawing ⋮ Optimal polygonal representation of planar graphs ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ How to Draw a Planarization ⋮ Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations ⋮ THE THREE-PHASE METHOD: A UNIFIED APPROACH TO ORTHOGONAL GRAPH DRAWING ⋮ Imbalance is fixed parameter tractable ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ A heuristic approach towards drawings of graphs with high crossing resolution ⋮ \(\beta\)-stars or on extending a drawing of a connected subgraph ⋮ Bend-minimum orthogonal drawings in quadratic time ⋮ On the fairness and complexity of generalized \(k\)-in-a-row games ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ A linear-time algorithm for drawing a planar graph on a grid ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ Schnyder woods and orthogonal surfaces ⋮ Encoding toroidal triangulations ⋮ How to Draw a Planarization ⋮ Curve-constrained drawings of planar graphs ⋮ The DFS-heuristic for orthogonal graph drawing ⋮ Drawing planar graphs with circular arcs ⋮ CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS ⋮ Balanced vertex-orderings of graphs ⋮ Convex grid drawings of planar graphs with constant edge-vertex resolution ⋮ Clean the graph before you draw it! ⋮ Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints ⋮ Drawing graphs as spanners ⋮ Imbalance parameterized by twin cover revisited ⋮ Minimum-width grid drawings of plane graphs ⋮ On the two-dimensional orthogonal drawing of series-parallel graphs ⋮ Algorithms for Drawing Planar p-petal Graphs ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ Universal Systems of Oblivious Mobile Robots ⋮ Three-dimensional orthogonal graph drawing algorithms ⋮ Advances in the theory and practice of graph drawing ⋮ CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS ⋮ AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING ⋮ A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths ⋮ Bipolar orientations revisited ⋮ Geodesic obstacle representation of graphs ⋮ Incremental convex planarity testing ⋮ On Covering Segments with Unit Intervals ⋮ Point matching under non-uniform distortions.

Cites Work